[운영체제] 5. CPU Scheduling (1)

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. 프로세스 특성 분류

• I/O-bound process
  • cpu를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  • Interactive job -> 적절한 response 제공이 필요
  • many short CPU bursts
• CPU-bound process
  • 계산 위주의 job - 중간에 I/O가 거의 끼어들지 않음
  • few very long CPU bursts

 

2. CPU Scheduler & Dispatcher

CPU Scheduler : Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다. (하드웨어가 아닌 운영체제 안 특정 코드를 의미함)

Dispatcher : CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다. 이 과정을 context switch(문맥교환)이라고 한다.

 

- Nonpreemptive : 비선점형. 강제로 빼앗지 않고 자진 반납 

- Preemptive : 선점형. 강제로 빼앗음

 

CPU Scheduling이 필요한 경우

1) Running -> Blocked (예: I/O 요청하는 시스템콜) : nonpreemptive

2) Running -> Ready (예: 할당시간만료로 timer interrupt) : preemptive

3) Blocked -> Ready (예: I/O 완료 후 인터럽트) : preemptive

4) Terminate : nonpreemptive

3. Scheduling Criteria (=Performance Index, Performance Measure, 성능 척도)

• System 측면
  • CPU utilization (이용률) : keep the CPU as busy as possible
  • Throughput (처리량): # of processes that complete their execution per time unit
• Process 측면
  • Turnaround time (소요시간) : amount of time to execute a particular process
  • Waiting time (대기 시간) : amount of time a process has been waiting in the ready queue
  • Response Time (응답 시간) : amount of time it takes from when a request was submitted until the first response is produced, not output

4. Scheduling Algorithms

FCFS (First-Come First-Service)

프로세스가 도착한 순서대로 CPU를 잡고 수행한다.

만약 위와 같은 프로세스에 대해서 도착 순서가 P4 -> P2 -> P3 -> P1 과 같다고 하면, average waiting time = (0 + 2 + 5 + 11)/4 = 4.5 ms 가 된다. 프로세스의 도착 순서에 따라 ATT가 달라지는 것을 확인할 수 있다. -> Convoy effect 발생

 

- Convoy effect : short process behind long process. 긴 프로세스가 먼저 도착해서 짧은 프로세스들이 오래 기다려야 하는 경우를 의미.

SJF (Shortest-Job-First)

각 프로세스의 다음번 CPU Burst time을 가지고 스케줄링에 활용

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄한다.

SJF is optimal - SJF 방식은 주어진 프로세스들에 대해 minimum average waiting time을 보장한다.

- Non-Preemptive SJF

• 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

- Preemptive SJF

• 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
• 이 방법은 Shortest-Remaining-Time-First (SRTF) 라고도 부름

Problem

• 다음 CPU burst time을 어떻게 알 수 있는가?
  • estimation(추정)만이 가능. 과거의 CPU burst time을 이용해서 추정함 
  • exponential averaging : 예측값과 실제 과거의 CPU burst time에 대해 특정 a, (1-a)를 곱해 계산할 수 있음. 이때 후속 term은 선행 term보다 더 적은 가중치 값을 가지게 됨. 
• Starvation : 낮은 우선순위를 가진 프로세스가 CPU를 잡지 못하게 됨. SJF에서는 적은 실행시간을 가지는 프로세스가 계속해서 들어오면 실행시간이 긴 프로세스가 실행되지 못하게 되는 starvation 문제가 발생할 수 있음.

Priority Scheduling

highest priority를 가진 프로세스에게 CPU를 할당한다.

• Problem - Starvation : low priority processes may never execute.
• Solution - Aging : as time progresses increase the priority of the process.

Round Robin (RR)

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐 (일반적으로 10-100 milliseconds)

• 할당 시간이 지나면 프로세스는 preempted 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
• n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. -> 어떤 프로세스도 (n-1)*q time unit 이상 기다리지 않는다.
• 대기 시간이 본인이 CPU를 사용하려는 시간에 비례한다. (CPU 사용 시간이 길다면 q 이내에 프로세스가 끝나지 않아 다시 ready queue에서 기다려야 함)
• CPU 사용시간이 짧은 프로세스와 긴 프로세스가 섞여있을 경우 유리하다. 만약 모든 프로세스의 사용시간이 동일하다면 일정시간 돌아가며 CPU를 차지하다가 결국 같은 시간에 수행을 완료 후 나가게 된다. 이 경우 프로세스가 빨리 빠져나가지 못하고 계속 ready queue에서 기다리며 대기 시간만 늘어나게 되므로 RR을 사용하기 적절치 않다.
• Performance
  • q large -> FCFS
  • q small -> context switch 오버헤드가 커져 전체 성능이 떨어진다.