[OS] 스케쥴러와 CPU 스케쥴링

1. 프로세스 스케쥴링

정의

• 프로세스 스케쥴링이란 CPU로부터 running 중인 프로세스를 스케쥴에 맞게 동작시키기 위한 하나의 활동
• 특히 멀티프로그래밍 OS에서 필수적인 요소임

비선점형과 선점형

• 비선점형 : 쉽게 말해 round-robin , 강제로 빼앗지 않고 자진 반납 (non-preemptive)
• 선점형 : 우선순위에 따른 프로세스 switching , 강제로 빼앗음 (preemptive)

프로세스 스케쥴링 큐

• OS는 PCBs를 통해 프로세스 스케쥴링 큐를 관리하며
• OS는 프로세스의 상태에 따라 별개의 queue를 관리하고 있으며, 같은 상태의 프로세스 PCBs들은 같은 queue에 저장이 됨

1. Job Queue : 현재 시스템 내에 있는 모든 프로세스 집합 (ready queue + device queue)
2. Ready Queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
3. Device Queue : I/O 디바이스 처리를 기다리는 프로세스 집합

2. 스케쥴러 (Scheduler)

스케쥴러 (Scheduler)

• 각각의 자원 별로 순서를 정해주는 것

Long-term scheduler (장기 스케쥴러 or job scheduler)

• PCB를 레디큐에 옮기는 과정을 담당함
• new → ready
• 시작 프로세스 중 어떤 것들을 레디큐로 보낼지 결정
• 프로세스에 메모리를 주는 과정이라고 보면 됨 
• degree of multiprogramming을 제어
• 보통은 long-term scheduler가 없거나 아주 작은 부분을 차지

Short-term scheduler (단기 스케쥴러 or CPU scheduler or dispatcher)

• 어떤 프로세스를 다음에 running 시킬지 결정
• 프로세스에 CPU를 주는 것
• long-term scheduler보다 빠름

Medium-term scheduler (중기 스케쥴러 or Swapper)

• 여유공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄
• 프로세스에게서 메모리를 빼앗는 것 (swap out, CS용어로는 suspended라고 부름)

3. CPU 스케쥴링

목적

• CPU를 사용함에 있어서 프로세스가 적절하고 효율적으로 자원을 분배받기를 목적으로 함
• I/O 작업을 하는 동안

 

용어

• Arrival Time : 프로세스가 ready queue로 도착한 시간
• Completion Time : 프로세스가 실행을 마치는데 걸린 시간
• Burst time : 프로세스가 CPU를 실행하는데 필요한 시간
• Turnaround Time : 도착시간과 완료시간의 중간

 

성능척도

 

1) CPU를 기준으로

 

CPU utillization (이용률)
- 전체시간 중에서 CPU가 놀지 않고 일한 시간
- 비싼 자원이기 때문에 많이 일을 시켜라

 

Throughput (처리량)
- 주어진 시간당 얼마나 많이 처리하는지

 

 

2) 유저를 기준으로

 

Turnaround time (소요시간, 반환시간)
- CPU를 얻어서 쓰고 다 쓰고 나서 나갈 때까지 걸리는 시간
- 쓴시간과 기다린 시간 모두 포함

 

Waiting time (대기시간)
- 프로세스가 ready queue에서 얼마나 기다리는지
- CPU를 쓰기 위해 기다린 시간
- Preemptive일 때 쓰다가 빼앗겨서 기다리는 시간들도 포함

 

Response time (응답시간)
- 처음으로 CPU를 얻기까지 걸린 시간

 

⇒ CPU를 가급적 많이 쓰고, 처리량이 많아야하며, turnaround time, waiting time, response time이 작은 것이 효율이 높은 것임

 

스케쥴링의 종류

FCFS(First-Come First-Served)

• 먼저 요청한 프로세스 순으로 스케쥴링 (비선점형)
• 단점 : convoy 효과, 하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 것

SJF(Shortest-Job-First)

• CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케쥴
• 장점 : minimum average waiting time을 보장 (preemptive의 경우)
• non-preemptive / preemptive
  - non-preemptive : CPU를 잡으면 CPU burst가 완료될때까지 CPU를 선점당하지 않음
  - Preemptive : burst time보다 더 짧은 CPU burst time을 가지는 프로세스가 도착하면 CPU를 빼앗음
                           ⇒ Shortest Remaining Time First(SRTF)라고 함
• 단점 : 길게 걸리는 프로세스의 starvation 현상
• 예측되는 CPU burst time이 가장 짧은 것에 우선순위를 주는 일종의 priority scheduling

 

Priority Scheduling

• 높은 우선순위를 가진 프로세스에게 CPU를 할당
• non-preemptive / preemptive
• 단점 : starvation (기아현상)
• 해결 : 시간이 지날 수록 increase the priority of the process

 

Round Robin(RR)

• 각 프로세스는 동일한 크기의 할당 시간 (time quantum)을 가짐
• 할당시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 섬
• 할당시간을 매우 크게 잡으면 → FCFS와 동일함
• 할당시간을 지나치게 작게 → context switch 오버헤드가 커짐
• 장점 : response time이 빨라짐

 

Multilevel Queue

• ready queue를 여러 개로 분할 (줄마다 우선순위를 둠)
• 프로세스는 각자의 특성에 따라 특정 큐에 할당 됨
• 각 큐는 독립적인 스케쥴링 알고리즘을 가짐

 

Multillevel Feedback Queue

• ready queue가 있지만 우선순위가 뒤바뀔 수 있음
• 프로세스가 큐 간에 이동할 수 있도록 해줌
• multilevel-feedback-queue scheduler를 정의하는 파라미터
  - queue의 수
  - 각 queue의 스케쥴링 알고리즘
  - process를 상위 큐로 보내는 기준
  - process를 하위 큐로 내쫓는 기준
  - 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준