[운영체제] 5. Process Scheduling 프로세스 스케줄링

기본 개념 (Basic Concept)

• 멀티 프로그램의 목적은 CPU의 이용도를 최대화시키는 것. (CPU 스케쥴링을 이용)
• 일반적인 프로세스는 IO와 CPU 사용을 번갈아 연산 (사이클 형태)

* CPU 스케쥴링 : CPU가 다음에 수행할 프로세스의 실행 순서를 정하는 것

* CPU-burst time : IO 없이 집중적으로 CPU 계산하는 시간

CPU burst 분포도

 

Alternating Sequence of CPU And I/O Bursts

CPU burst time과 IO burst time이 번갈아 발생

 

CPU Scheduler

메인메모리의 실행 준비가 완료된 프로세스 중 하나 선택해서 CPU 할당.

 

CPU 스케쥴링이 발생하는 경우 (CPU 사용을 다른 프로세스에 양도할 경우 발생)

• 프로세스 상태 running에서 waiting로 변할 때
• running -> ready (timing interrupt 발생 시)
• IO 완료 -> ready
• Terminates (프로세스 종료)

CPU Scheduling 기법

• 비선점 (non-preemptive) 스케줄링 - 위의 4가지 경우
  • 프로세스가 자율적으로 실행을 중단하고 cpu를 양도하여 다른 프로세스에게 할당하는 스케줄링
  • CPU가 현재 실행중인 프로세스가 완료될 때까지 다른 프로세스들은 대기
  • 오직 현재 실행중인 프로세스가 종료되거나 IO를 위해 대기상태(waiting state)로 들어가는 경우에만 다른 프로세스 실행 가능
• 선점 (preemptive) 스케줄링 - 그 외 나머지
  • 스케줄러에 의해 현재 실행 프로세스에서 CPU 제어권을 빼앗아, 우선권 있는 프로세스에게 할당하는 스케줄링
  • 실행중인 프로세스가 다른 프로세스에게 CPU 제어권을 선점당하면 Running 상태에서 Ready 상태로 변하고 IO를 위해 대기 중인 상태에서 다른 프로세스가 CPU를 선점하면 Ready상태로 전환

 

Dispatcher (CPU 할당 모듈)

디스패처는 CPU제어권을 CPU 스케줄러가 선택한 프로세스에게 주는 모듈

(dispatch : 한 프로세스에게 CPU 제어권을 넘겨 실행을 시작하게 함.)

 

하는 일

• Switching context (문맥 교환)
• Switching to user mode (사용자 모드로 전환)
• 프로그램을 다시 시작하기 위해 기존 실행 중이던 주소로 이동 (jump)

디스패치 지연 (Dispatch latency)

Dispatch 하는 데 필요한 delay 시간, 프로세스 정지 및 다른 프로세스 수행까지 소요되는 시간 (오버헤드 시간)

 

CPU 스케줄링 고려요소 (Scheduling Criteria)

• CPU 이용률 (CPU Utilization) : 최대한 CPU를 바쁘게 사용해야 한다.
• 처리량 (Throughput) : 단위 시간당 수행된 프로세스의 개수.
• 총처리 시간 (Turnaround Time) : 특정 프로세스를 완료하기까지 소요 시간.
• 대기 시간 (Wating Time) :  준비 큐(Ready Queue)에서 CPU를 할당받기 까지 대기하면서 보낸 시간.
• 응답 시간 (Response Time) : 명령 내린 후 첫 번째 응답이 나올 때까지의 시간.

위와 같은 기준을 통하여 CPU 이용률과 처리량을 최대화하고 총 처리 시간, 대기시간, 응답 시간을 최소화하는 것이 바람직하다.

 

CPU 스케줄링 알고리즘의 최적화 고려사항 (기준)

• CPU 이용도 최대화
• 시간단 처리량 최대화
• 작업 완료 시간 최소화
• 대기시간 최소화
• 시스템 반응/응답 시간 최소화

 

CPU 스케줄링 알고리즘

선입 선처리 스케줄링 (First-Come, First-Served Scheduling, FCFS)

• 먼저 요청하는 프로세스가 CPU를 할당받아 처리되는 스케줄링 알고리즘
• 비선점형(Non-Preemptive)이다.
  • 일단 CPU가 한 프로세스에게 할당되면 그 프로세스가 종료하든지 또는 입/출력 처리를 요구하든지 하여 CPU를 방출할 때까지 CPU를 점유

 

 

수행 시간이 짧은 순서로 온 프로세스부터 먼저 처리할 경우 평균 대기시간이 짧아진다.

 

  따라서, FCFS 스케줄링 알고리즘은 프로세스가 도착한 순서대로 평균 대기시간에 영향을 미친다.

호송대 효과 (Convoy effect) : 수행시간 긴 프로세스가 먼저 도착 시, 뒤에 짧은 프로세스가 오더라도 긴 프로세스가 끝날 때까지 대기해야 한다. (CPU 효율 저하)

 

FCFS 예시

 

최단 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF)

• 짧은 CPU burst time을 가지는 순서대로 CPU를 할당해주는 알고리즘. 만약 길이가 동일하다면 선입 선처리
• SJF는 평균 대기시간이 가장 최소값을 가지는 최적화된 알고리즘이다.

그러나, 사전에 CPU burst time을 알 수 없기 때문에 구현 불가하다. (근사치를 구하여 구현)

 

프로세스가 동일 시간에 도착할 경우의  SJF

최소의 평균 대기시간을 가진다.

 

선점형(Preemptive SJF) 스케줄링과 비선점형(Non-Preemptive SJF) 스케줄링

• SJF 스케줄링은 선점형 또는 비선점형일 수 있다.
• 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 완료 큐에 도착하면 선택이 발생

새로운 프로세스가 현재 실행 되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 경우,

• 선점형(Preemptive) SJF은 현재 실행하는 프로세스를 선점
• 비 서점형(Preemptive) SJF은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용 (문맥 교환 발생)

선점형 SJF 스케줄링은 최소 잔여 시간 우선(shortest remaining time first) 스케줄링이라고도 불린다.

 

 

비선점형(Non-Preemptive) SJF 예시

한번 프로세스가 할당될 경우, 할당된 CPU를 빼앗기지 않고 스케줄링이 된다.

 

 

 

 

선점형 (Preemptive) SJF (=최소 잔여 시간 우선 Shortest remaining time first)

P1이 먼저 도착하여 처리 중에 P2도착 후 P2가 burst time이 더 짧으므로 P2가 선점하여 문맥 교환 후 처리가 된다.

 

 

 

우선순위 스케줄링 (Priority Scheduling)

• 각 프로세스에 정수 우선순위를 두어 스케줄링
• 가장 높은 우선순위대로 CPU 권한을 할당
• 만약 우선순위가 같을 경우 선입 선처리
• SJF도 일종의 우선순위 스케줄링으로 볼 수 있음

문제점

* 기아 현상 (Starvation) : 우선순위 낮을 경우 너무 오래 대기하는 문제 발생 가능

-> 노화 (Aging) : 대기 시간이 지남에 따라 우선순위를 높이는 기법 (오래기다릴 수록 우선순위 상승)

 

 

모든 프로세스 동시에 도착 가정

 

라운드 로빈 (Round Robin, RR) 스케줄링 - 돌아가며 나눠 씀

• 각각의 프로세스는 작은 CPU 시간의 시간 유닛(time quantum)을 가진다. (10~100ms)
• 시간이 지나면 해당 프로세스의 CPU 할당을 빼앗기고 Ready Queue의 끝으로 보낸다.

만약 n개의 프로세스가 레디 큐에 있을 때, 1/n씩 cpu시간을 나눠 쓴다.

어떤 프로세스도 (n-1)*q보다 기다리지 않게 된다.

 

* Time Quantum이 너무 크면 FIFO로 작동한다.

* 너무 작으면 문맥 교환이 너무 자주 발생하므로 오버헤드가 증가한다.

따라서 적당한 Time Quantum을 설정해야 한다.

 

 

 

 

Turnaround Time Varies With the time quantum (상관관계)

 

 

다단계 큐 스케줄링 Multilevel Queue (큐가 2개 이상인 프로세스 스케줄링)

Ready 큐를 우선순위 기준으로 나눔

• foreground job queue : 우선순위 높음, 대화식 시스템
• background jab queue : 우선순위 낮음, 배치 작업

각 큐마다 다른 우선순위 알고리즘 적용 가능

• foreground - 라운드 로빈 (RR)
• background - FCFS (선착순 처리)

어떻게 큐를 구분해서 스케줄링 알고리즘을 실행하는가?

• 고정 우선순위 기법 (Fixed priority scheduling)
  • 상위 우선순위 모두 처리하고 아무 것도 남아있지 않을 때 그다음 레벨 우선순위 작업 수행 (기아 발생 가능)
• Time slice : 큐에 따라 할당하는 time slice 길이를 달리한다. (ex. foreground 80%, background 20%)

정리

 다단계 큐 스케줄링 알고리즘은 프로세스들간의 우선순위를 정의하고 각 우선순위 간의큐를 생성하여 수행하는 방식.

 높은 우선순위의 큐의 프로세스가 비어있지 않으면 낮은 우선순위 큐의 프로세스는 실행될 수 없다.

 

다단계 피드백 큐 (Multilevel Feedback Queue) 스케줄링- 다양한 레벨 간 프로세스 이동 가능

aging을 통해 프로세스가 여러 큐를 이동 가능

* 대기시간이 길어지면 우선순위가 높은 큐로 이동 가능

 

필요 parameters

• 큐의 수
• 각 큐의 스케줄링 기법 (일반적으로 라운드 로빈 (RR) 사용)
• 프로세스가 상위/하위 큐로 이동하는 방법
• 처음 시작하는 큐 선택 방법

새로운 작업 Q0에 도착. TQ=8ms 이므로 8ms 이상 걸리는 작업일 경우 Q1 큐 끝으로 이동

Q0 모두 수행 후 Q1 큐 처리 시작 (16ms 이상 걸리는 작업은 Q2 끝으로 이동

 

• IO 없이 CPU를 오래 사용하는 프로세스 : 우선순위 하락
• IO 많이 하고, CPU를 짧게 사용하는 프로세스 : 높은 우선순위
• CPU bound 프로세스 : 낮은 우선순위, IO bound 프로세스 : 높은 우선 순위

 

Solaris Scheduling

Dispatch Table

 

---

<주요 용어 정리>

1. ____ is the number of processes that are completed per time unit.

___는 시간 단위당 완료된 프로세스의 수입니다.

=> 처리량 (Throughput)

 

2. ____ scheduling algorithm is designed especially for time sharing systems.

____ 스케줄링 알고리즘은 특히 시간 공유 시스템을 위해 설계되었다.

=> 라운드 로빈 (Round Robin, RR)

 

3. ____ scheduling algorithm must be non-preemptive.

____ 스케줄링 알고리즘은 비선점형이어야 합니다.

=> FCFS

 

4. In  Solaris, what is the time quantum (in milliseconds) of an interactive thread with priority 35. ___ -> look up the Solaris dispatch table

Solaris에서 우선순위가 35인 대화형 스레드의 시간 양자(밀리초 단위)는 얼마입니까? ___ -> Solaris 디스패치 테이블 조회

=> 80

 

5. In Solaris, if an interactive thread with priority 15 uses its entire time quantum, what is its priority recalculated to? ____

Solaris에서 우선순위가 15인 대화형 스레드가 전체 시간 퀀텀을 사용할 경우 우선순위는 무엇으로 다시 계산됩니까? 

=> 5

 

6. In Solaris, if an interactive thread with priority 25 is waiting for IO, what is its priority recalculated to when it is eligible to run again?

Solaris에서 우선 순위가 25인 대화형 스레드가 IO를 기다리고 있는 경우, 다시 실행할 수 있는 시점으로 우선 순위가 다시 계산되는 것은?

=> 52

 

7. ____ is the task of selecting a waiting process from the ready queue and allocating the CPU to it.

___는 준비 대기열에서 대기 프로세스를 선택하고 CPU를 할당하는 작업입니다.

=> CPU 스케줄링(CPU scheduling)

 

 

8. both ____ and ____ scheduling may suffer from starvation.

___와 _____ 스케줄링이 모두 기아에 허덕일 수 있습니다.

 

=> 우선순위(priority), SJF

 

9. ____ is a technique to prevent starvation.

___는 기아를 예방하는 기술이다.

=> 노화(aging)