기술 면접 대비 CS 핵심 요약 - 스케줄링

2023.09.08 - [CS] - 기술 면접 대비 CS 핵심 요약 - 프로세스 상태, 멀티 프로세스 vs 멀티 스레드

기술 면접 대비 CS 핵심 요약 - 프로세스 상태, 멀티 프로세스 vs 멀티 스레드

2023.09.09 - [CS] - 기술 면접 대비 CS 핵심 요약 - 프로세스 동기화, 교착 상태

기술 면접 대비 CS 핵심 요약 - 프로세스 동기화, 교착 상태

2023.09.10 - [CS] - 기술 면접 대비 CS 핵심 요약 - 스레드 안전, IPC, 좀비&고아 프로세스

기술 면접 대비 CS 핵심 요약 - 스레드 안전, IPC, 좀비&고아 프로세스

 

📕본 포스팅은 "기술면접 대비 CS 전공 핵심 요약집" 책을 공부하면서 정리한 내용입니다.

---

 

 

1.3 스케줄링

 

• 멀티 프로세스 환경에서는 여러 프로세스가 모두 실행되어야 하지만, CPU 자원은 한정적
• 스케줄링을 통해 모든 프로세스를 공평하게 실행해 한정된 자원을 효율적으로 활용하는것이 OS의 주요 목적

 

1.3.1 스케줄링의 목적 ( 중요도 ★☆☆  )

멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행

 

• 공평성 : 모든 프로세스가 공평하게 실행되어야 한다. 특정 프로세스가 실행되지 않는 경우가 없도록 스케줄링 해야한다
• 효율성 : 자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링 해야 한다
• 안정성 : 우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링 해야 한다
• 반응 시간 보장 : 프로세스가 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 보기 때문에 일정 시간 내에 응답할 수 있도록 스케줄링 해야 한다
• 무한 연기 방지 : 특정 프로세스에 대한 처리가 무한히 연기 되지 않도록 스케줄링 해야한다.

 

1.3.2 스케줄링 단계 ( 중요도 ★★★  )

 

1.2.4 프로세스 상태도에서 스케줄링이 일어나는 시점을 보면 다음과 같다.

 

• 장기 스케줄링(long-term scheduling) : 준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절

• 잡 스케줄링 또는 승인 스케줄링이라고도 불림
• 현재 운영체제에서는 시분할 시스템을 사용하기에 대부분 사용하지 않음

 

• 중기 스케줄링(mid-term scheduling) : 메모리에 로드된 프로세스 수를 동적으로 조절

• 메모리에 프로세스가 많이 로드되면 스왑 아웃(swap out)해서 일부 프로세스를 통째로 저장
• 스왑 아웃된 프로세스는 중단 상태(suspended)가 된다
• 중단 상태는 준비 상태에서 스왑 아웃된 '중단된 준비 상태'와 대기 상태에서 스왑 아웃된 '중단된 대기 상태'로 구분된다.

 

• 단기 스케줄링(short-term scheduling) : 준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정. 즉, 어떤 프로세스를 디스패치할지 결정하는데 CPU스케줄링이라고도 한다.

스케줄링의 단계

 

스케줄러 관점의 프로세스 스케줄링

스케줄러 관점에서 프로세스 스케줄링

1. 스케줄러가 준비 큐에 있는 프로세스 중 하나를 선택해 CPU에 디스패치 한다. 이때 스케줄링 알고리즘 이용
2. CPU에서 프로세스를 실행한다. 이때 프로세스는 실행 상태이다.
   1. A 프로세스 수행이 완료되면 프로세스를 종료한다.
   2. B 일정시간을 초과하면 인터럽트가 발생해 프로세스가 준비 큐로 들어가고 준비 상태가 된다
   3. C 입출력 요청이 들어오면 인터럽트가 발생한다. 이때 프로세스는 대기 큐로 들어가서 대기 상태가 왼다. 입출력이 완료되면 준비 큐로 들어간다.
3. fork()가 호출되면 자식 프로세스가 생성되고, 자식 프로세스는 준비 큐로 들어간다.

 

하나 더 알기!

스왑 아웃과 스왑 인

• 스왑 아웃(swap out) : 프로세스가 실행되려면 메모리에 로드되어야 한다. 그런데 메모리 공간보다 많은 프로세스가 로드되는 경우가 있을 수 있다. 이럴 때 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장 공간(SSD와 같은 영역)으로 옮겨 저장하는 것
• 스왑 인(swap in) : 스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통째로 다시 메모리에 로드하는 것
• 스와핑(swapping) : 스왑 아웃과 스왑 인처럼 프로세스를 통째로 메모리 영역과 저장공간으로 옮기는 것
  • 스와핑하면 메모리 공간보다 많은 프로세스를 실행할 수 있다

 

1.3.3 스케줄링 알고리즘 ( 중요도 ★★★  )

 

• CPU스케줄러 (단기 스케줄러)가 준비 큐에 있는 프로세스중 어떤 프로세스를 실행시키질지 결정하는데 사용

 

스케줄링의 목적을 달성하기 위해 아래와 같은 기준으로 평가하지만, 모두 만족하기는 어렵기에 우선순위를 정해야 한다.

• CPU사용률 : CPU를 놀리지 않고 사용하는지 판단
• 처리량 : 단위 시간(time out)당 실행한 프로세스 수
• 응답시간 : 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
• 반환시간 : 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간
• 대기 시간 :프로세스가 대기 큐에서 대기하는 시간의 총 합

 

준비 큐에 다음과 같이 프로세스가 들어있다고 가정하고 다양한 스케쥴링에 대해 알아보자.

준비 큐에 담긴 프로세스 예

비선점형 스케줄링(non-preemptive scheduling)

• 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음을 의미
• FCFS(First Come First Served)스케줄링, SJF(Shortest Job First), HRRN(Highest Response Ration Next)스케줄링

• FCFS 스케줄링 : 준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘

FCFS 스케줄링 실행 순서

평균 대기 시간은 각 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 것과 같다.

따라서 FCFS 스케줄링의 평균 대기시간은 290이 된다.

• SJF 스케줄링 : 실행 시간이 짧은 프로세스가 우선순위를 갖는 알고리즘 = SJN(Shortest Job Next). 준비 큐에 있는 프로세스 중 CPU를 점유하는 실행 시간이 가장 짧은 프로세스부터 실행한다. 평균 대기 시간이 가장 짧지만, 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있다.

SJF 스케줄링 실행 순서

같은 방법을 계산하면 SJF 스케줄링에서 평균 대기 시간은 218로, FCFS 스케줄링 알고리즘보다 짧다.

기아 상태(starvation): 프로세스마다 우선순위(priority)가 있는데, 
                     우선순위가 높은 프로세스만 수행되어 우선순위가 낮은 특정 프로세스는 계속 실해되지 못하게 하는 것을 의미한다.

 

 

선점형 스케줄링(preemptive scheduling)

 

• 스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음을 의미한다
• RR(Round&Robin)스케줄링, SRTF(Shortest Remaining  Time First)스케줄링, 멀티 레벨(multi level)스케줄링

 

• RR 스케줄링 : 비선점형 스케줄링과 달리 프로세스 간 우선순위가 없다. 모든 프로세스를 순서대로 일정 시간 동안 실행하며, 일정 시간을 초과하면 다른 프로세스를 실행한다. 여기서 일정 시간은 '시간 단위'를 의미하며 타임 퀀텀 또는 타임 슬라이스라고도 한다.     일반적으로 시간 단위는 10~100밀리초이다. 콘텍스트 스위칭이 빈번하게 일어나서 오버헤드가 크다는 단점이 있지만, 모든 프로세스가 반복 수행되어 응답 속도가 빠르다는 장점도 있다.

RR 스케줄링 실행 순서

RR 스케줄링에서 어떤 프로세스에서 응답 요청이 들어왔을 때 기다리는 최대 시간은 (전체 프로세스 수) -1 에 (시간단위)를 곱한 값이다.

예에서는 (5-1)x50 = 200밀리초안에 응답할 수 있다. 응답 속도가 다른 스케줄링보다 빠르지만, 콘텍스트 스위칭이 빈번하므로 시간 단위를 적절하게 설정해야한다.

 

• SRTF 스케줄링 : 준비 큐에서 대기 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘. 한 프로세스가 실행 중일 때 실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 CPU를 차지하게 된다. 평균 대기 시간이 짧다는 장점이 있지만,수행 시간이 긴 프로세스는 기아 상태가 되기 쉽다.

SRTF 스케줄링 실행 순서

P1과 같이 프로세스가 중간에 중단된 경우에는 수행 완료까지의 대기 시간을 합하면 된다.

다른 스케줄링 알고리즘보다 평균 대기 시간이 짧은 것을 알 수 있다. 하지만 P3가 P4보다 준비 큐에 빨리 들어왔어도 실행 시간ㅇ ㅣ길어서 마지막 순서로 밀렸듯이 실행 시간이 긴 프로세스는 기아 상태가 되기 쉽다.

 

• 멀티 레벨 스케줄링 : 준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘이다. 분리한 큐는 각각 우선순가 있고 다른 스케줄링 알고리즘을 적용할 수 있다. 여러 개의 큐는 foreground큐와 background큐로 나뉜다. foreground큐에는 응답 속도가 중요한 프로세스가 들어가고, background큐에는 응답속도보다 성능을 중요시하는 프로세스가 들어간다.

멀티 레벨 스케줄링

그림처럼 준비큐가 목적에 맞게 여러 큐로 나뉘어져서 프로세스가 들어오면 해당 프로세스의 우선순위에 맞는 큐에 들어가서 대기하게 된다.

궁금한 점 : 성능이 응답속도 아닌가? 응답속도가 무엇일까?