03. CPU Scheduling

CPU-I/O Burst Cycle

1. 프로세스는 CPU execution + I/O wait의 cycle로 구성됨

2. CPU burst: CPU에 의해 직접 수행되는 작업의 부분(CPU execution)

3. I/O burts: CPU에 의하지 않고 일어나는 작업의 부분(I/O execution)

4. 일반적으로 프로세스는 많은 수의 짧은 CPU burst들, 혹은 적은 수의 긴 CPU burst들로 구성되며, 이들의 편중에 따라 I/O-bound 프로그램과 CPU-bound 프로그램으로 나눌 수 있음

5. I/O-bound 프로그램: 작업의 대부분이 I/O로 구성, CPU burst는 짧게 들어가 있음

6. CPU-bound 프로그램: 작업의 대부분이 CPU burst로 구성

7. CPU burst들과 I/O burst들의 분포는 적절한 CPU scheduling algorithm을 선정하는데 매우 중요한 요소로 작용함

---

CPU Scheduler (Shor-term scheduler)

1. 가장 빈도수가 높은 스케줄러

2. 현재 메모리에서 수행이 준비되어 있는(레디 큐에서 기다리고 있는) 프로세스 중 하나를 선택하여 CPU에게 할당해 주는 일을 함

3. dispatcher:  이런 CPU scheduler 갖고 있는 운영체제의 모듈

4. dispatcher모듈이 하는 일

     ①  CPU 제어를 선택된 프로세스에게 할당해 줌

     ②  Context Switching

     ③  Switching to user mode

     ④  jumping to the proper location in the user program to restart that program(새로 시작할 사용할 프로그램에 적당한 위치로 점프함)

5. Switch가 일어날 때마다 구동되므로 가능한 빨라야 함

6. Dispatch latency: time it takes for the dispatcher to stop one process and start another running(디스패처가 한개의 프로세스를 멈추고 다른 프로세스를 실행하는데 걸리는 시간)

 

---

Preemptive and Non-preemptive Scheduling

1. Preemptive: 강제성을 띄고 있음. 해당 프로세스 스스로가 아닌 타의에 의한 강제적인 scheduling을 의미

2. Non-Preemptive: 강제성을 띄고 있지 않음. 그러므로 해당 프로세스 스스로 일을 수행하는 것을 의미

3. CPU scheduling에 있어서 결정이 필요한 4가지 경우

     ①  Running -> Blocked: I/O request에 의해 일어남. Non-Preemptive

     ②  Running -> Ready: timer interrupt에 의해 일어남. Preemptive (외부 이벤트 발생)

     ③  Waiting -> Ready: I/O request에 의해 일어남. Preemptive (외부 이벤트 발생)

     ④  Process termination: Process 스스로 종료

4. Preemptive한 스케줄링의 경우 발생할 수 있는 문제

     ①  2개 이상의 프로세스들이 공유 데이터를 사용하는 경우 문제가 발생할 수 있음

     ②  어떤 프로세스가 kernel mode에서 중요한 데이터, 예를 들어 프로세스 테이블의 수정, 프로세스의 생성 등과 같은 중요 업무 수행 중에 Preemption될 경우 문제가 발생할 수 있음 (e.g. System call)

     ③  이러한 문제를 해결하기 위해 Process Synchronization이 요

 

---

Scheduling Criteria (스케줄링 알고리즘의 평가 기준)

1. CPU utilization: 최대화 되어야 함. 0 < u < 1.0

2. Throughput: 최대화 되어야 함. 단위 시간당 완료되는 프로세스의 수

3. Turnaround time: 최소화 되어야 함. 작업이 시작된 시점부터 완료된 시점까지 걸리는 시간. CPU burst + I/O burst + waiting + ready queue

4. Waiting time: 최소화 되어야 함. ready queue, I/O wait 등 기다리는 시간의 총합

5. Response time: 최소화 되어야 함. 실시간 처리에서 중요. 어떤 요구사항이 들어왔을 때부터 첫번째 response가 출력된 시간까지(Responding을 start하는 데까지 걸리는 시간)

 

---

Scheduling Algorithms

1. First-Come-First-Serve(FCFS) Scheduling

     ①  가장 단순한 기법

     ②  Non-preemptive. 시분할 시스템에 있어서 많은 문제 내포.

     ③  Ready queue로 FIFO를 사용하면 용이하게 관리됨

     ④  평균 대기시간이 매우 커질 수 있음

     ⑤  예시

     ⑥  Convoy effect: CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상. 이로 인해 대기시간이 길어지게 됨

     ⑦  문제점 : Convoy effect때문에 CPU와 I/O장치들의 idle time이 커지게 됨으로써 CPU와 입출력 장치 사용률(utilization)이 낮아지게 되는 단점이 있음

     ⑧  Shortest Job First를 생각하게 됨

2. Shortest Job First Scheduling(SJF)

     ①  다음에 수행해야 할 CPU burst들 중에서 가장 작은 수행 시간을 갖는 프로세스부터 선택

     ②  2개 이상의 프로세스가 모두 동일한 수행시간을 갖는 경우 FCFS로 Scheduling함

     ③  예시

     ④  문제점 : 어떤 프로세스가 가장 짧은지 알 수 없음. 프로세스를 바로 받아 놓아야 알고리즘을 수행할 수 있음

3. Shortest-Remaining-Time-First(SRTF)

     ①  들어오는 대로 프로세스를 수행하고,  수행 중 다른 프로세스가 들어왔을 때 잔여 CPU burst가 가장 작은 프로세스를 선택하여 수행함

     ②  SJF Scheduling 기법의 preemptive version임

     ③  프로세스의 ready queue에 도착시간이 명시되어 있어야 함

     ④  예시

     ⑤  문제점: 프로세스의 실행 시간이 실제로 얼마나 걸릴지 모름

4. Priority-Scheduling

     ①  각 프로세스당 우선순위가 배정되어야 함

     ②  위의 모든 스케줄링 알고리즘 모두 우선순위 기반 알고리즘

     ③  SJF: 프로세스의 수행 시간(CPU-burst)이 짧을수록 우선순위가 높아지고 길수록 우선순위가 낮아짐

     ④  SRTF: 프로세스의 잔여 CPU-burst가 짧을 수록 우선순위가 높아지고 길수록 우선순위가 낮아짐

     ⑤  FCFS: 모든 프로세스의 우선순위를 동일하게 함(먼저 들어온 프로세스가 우선순위가 높음)

     ⑥  우선순위 고려 요소

      - 내부적 우선순위: time limits, memory requirements, number of open files, ration of average I/O / average CPU burst

      - 외부적 우선순위(O.S의 외부적 요인): 프로세스의 중요도, 기부금의 유형과 액수, 스폰서의 프로세스, 기타 정책적인 요인

     ⑦  Preemptive 혹은 Non-preemptive하게 운영될 수 있음

 

---

Problems in Priority Scheduling

1. Starvation(indefinite blocking, 무한정 기다림)

     ①  생기는 이유: steady stream of higher processes can prevent a low-priority process from getting the CPU)해당 프로세스보다 우선순위가 높은 프로세스들이 계속 들어옴)

     ②  해결책: aging 기법(오랫동안 시스템에 남아있는 프로세스에 대해 점진적으로 우선순위를 올려주는 기법)

2. Priority inversion(우선순위 반전) 현상

     ①  우선순위가 높은 프로세스가 우선순위가 낮은 프로세스를 기다리는 현상

     ②  real-time 시스템인 경우 deadline을 맞추지 못하는 문제 발생

     ③  client-server O.S에서 발생하기 쉬움

     ④  해결책: Priority-inheritance(우선순위 상속) 프로토콜을 사용하여 해결

     ⑤  Priority-inheritance: 낮은 우선순위의 프로세스의 우선순위를 한시적으로 증가시키는 것 (e.g. 서버가 클라이언트의 우선순위를 상속받음 )

: P1(클라이언트), P2(클라이언트), P3(서버). P1의 Rendezvous call에 의해 P3서버가 실행되고 있었는데 P2의 요청에 의해 우선순위가 높은 P1이 우선순위가 낮은 P2가 끝나길 기다림

 

---

Round-Robin(RR) Scheduling

1. time-sharing system(시분할 시스템)을 위해 특별히 설계됨

2. time quantum(time slice): 전체 시간을 여러 개의 단위 시간으로 나누었을 때 그 단위 시간. 보통 10~100msec

3. Ready queue로 circular FIFO queue를 사용

4. FCFS와 비슷하나 일정 시간이 되면 프로세스끼리 switch 한다는 preemption이 추가됨.

5. 한번에 한 time slice이상을 할당하지 않음

6. average waiting time이 길어질 수 있음

7. 예시

8. 특징

     ①  time slice의 크기에 따라 성능이 달라짐

      - time slice가 infinite할 때: FCFS랑 같음

      - time slice가 너무 짧을 때: Process Sharing effect(각 프로세스가 CPU가 자기만 수행하는 것 같은 착각을 일으킴)가 일어남.

     ②  Context Switch도 성능에 영향을 줌 (time slice에 영향을 받으니까)

      -  time slice는 context switch time 보다 커야 함

      -  time slice가 작아질수록 context switch하는 횟수가 증가하기 때문에 context switch overhead가 커지므로 성능 저하됨

     ③  turnaround time도 성능에 영향을 줌(time slice의 영향을 받으니까)

      - time slice가 작아지면 context switching time over head가 커지기 때문

      - 한 time slice에 CPU burst를 종료하는 것이 좋음

      - 80%의 CPU burst가 time slice보다 길이가 짧음

---

Multilevel-Queue-Scheduling-Algorithm(MQ)

1. 어떤 프로세스들을 같은 특성을 가진 프로세스 끼리 그룹핑 할 수 있을 때 적합한 알고리즘

2. 다수의 Ready-Queue를 사용하여 그룹마다 하나씩 큐를 할당함

3. 할당한 큐에 프로세스를 영구히 배정함

4, 각 큐마다 다른 알고리즘을 쓸 수 있음

5. 예시

6. 큐가 여러 개이기 때문에 큐를 스케줄링 해야함. 보통 우선순위 기반 스케줄링을 함. 각 큐는 절대적인 우선순위를 갖고 있음.

7. 문제점: 한번 큐에 할당되면 벗어날 수 없으므로 우선순위가 낮은 큐에 할당된 프로세스는 수행이 잘 안됨. 어떤 큐는 비어있고 어떤 큐는 꽉 차있음.

 

---

Multilevel-Feedback-Queue-Scheduling Algorithm(MFQ)

1. Multilevel-Queue와 비슷함

2. Queue사이의 프로세스 이동을 허락함

3. 어떤 프로세스가 너무 많은 CPU-burst를 하는  경우 우선순위가 높아서 계속 해당 프로세스만 실행되므로 low-priority-queue로 옮김. 그러면 I/O-bound process와 Interactive process가 수행될 수 있음

4. low-priority-queue에서 너무 오래 기다린 프로세스는 high-priority-queue로 옮김

5. 고려해야할 변수

     ①  큐의 개수

     ②  각 큐의 스케줄링 알고리즘

     ③  프로세스의 higher-priority-queue로의 이동 기준

     ④  프로세스의 lower-priority-queue로의 이동 기준

---

Real-Time-Scheduling

1. Hard-real-time

     ①  Guaranteed-response(최소한 이 시간에는 나온다는 것 보장)

     ②  resource(파일, 메모리, 데이터 등)를 확보하고 수행함

     ③  time critical한 특수 목적을 위한 H/W와 특수한S/W로 구성됨 e.g. 크루즈 미사일

2. Soft-real-time

     ①  Hard-real-time보다 제약을 조금 덜 받음

     ②  e.g. 멀티미디어, 인터렉티브 그래픽

     ③  response time을 길게 잡을 수 있음

     ④  대부분 priority-based-scheduling을 가짐

     ⑤  dispatch latency를 줄여야 함