[운영체제] 프로세스 스케줄링 1 (process scheduling)

운영체제의 스케줄러는 어떤 프로세스를 실행할 것인가를 결정해야 한다.
학부 수준에서는 CPU 를 하나만 사용하는 유니 프로세스 스케줄링만 다룬다.

스케줄러를 결정할 때 다음을 고려해야 한다.

1. 프로세스 특성
   CPU bound : CPU 중심 작업
   I/O bound : I/O 중심 작업
   제약 조건 : 데드라인
2. 운영체제의 특성
   preemption 을 허용하는가?
3. 사용자 특성
   interactvie 한가?

엄밀하게 나누면 스케줄러와 디스패처가 있다.
scheduler : 어떤 프로세스를 실행시킬 지 결정한다.
dispatcher : 현재 프로세스와 선택된 프로세스를 컨텍스트 스위칭 해 준다.

스케줄링은 어느 시점에서 해야하는가?

1. 현재 프로세스가 종료되었을 때
2. 현재 프로세스가 waiting queue 로 빠졌을 때
3. 현재 프로세스가 ready queue 로 갔을 때
4. 어떤 프로세스가 ready queue 로 갔을 때
   1, 2 는 non preemtive 이고 3, 4 는 preemtive 이다.
   이 외에도 데드라인이 정해져 있거나 다양한 상황이 있을 수 있다.

dispatch latency : context switching overhead
SCS : system contention scope
PCS : process contention scope
우리가 고려하는 것은 SCS 이다. PCS 는 유저 레벨 스레드를 사용하기 때문에 프로세스에서 스케줄링한다.

burst time : CPU 사용 시간

스케줄러 선택 기준

1. CPU utilization : CPU 사용률 최대화
2. max throughput : 동일 시간에 완료되는 프로세스 최대화 (min turnaround time, min wating time)
3. min response time : 응답시간 최소화
4. fairness : 공평한 CPU 사용 시간
   4가지를 모두 만족하는 스케줄러는 존재하지 않는다.

response time : start time (첫 번째로 CPU 를 차지하는데 걸리는 시간)
waiting time : ready queue 에 체류하는 시간

FCFS : First Come First Serve

첫 번째로 도착한 프로세스를 첫 번째로 처리하는 간단한 스케줄러
convey effect : burst time 이 긴 프로세스가 먼저 처리되어 짧은 프로세스가 수행되지 못 하는 경우
throughput, response time, fairness 모두 불만족스럽다.

SJF : Shortest Job First

burst time 이 짧은 프로세스를 먼저 처리한다.
non preemtive 스케줄러 중 turnaround time 이 optimal 이다.
수행시간이 긴 프로세스가 먼저 도착할 경우 convey effect 가 발생할 수 있다.
busrt time 이 얼마일지 미리 알아야 한다.

STCF : Shortest Time-to-Completion time First

남은 수행시간이 짧은 프로세스 먼저 처리한다. 새로운 프로세스가 들어오면 원래 있던 프로세스를 밀어낸다. 개념 자체는 SJF 와 유사하다. turnaround time 이 optimal 이기 때문에 다른 스케줄러와 비교 대상이 된다.

RR : Round Robin

scheduling quantum, time slice : CPU 한 번 올라갔을 때 수행하는 시간
response time 이 짧다.

RR vs STCF
RR 은 response time 이 짧다.
RR 은 컨텍스트 스위칭이 빈번하게 발생한다.
RR 은 throughput 이 안 좋다.
RR 은 fairness 가 좋다.
STCF 는 response time 이 안 좋다.
STCF 는 컨텍스트 스위칭이 거의 일어나지 않는다.
STCF 는 throughput 이 최적이다.
STCF 는 fairness 가 안 좋다.

• 인천대학교 컴퓨터공학부 3학년 전공필수 과목인 박문주 교수님의 운영체제 강의를 듣고 작성한 글입니다.