운영체제(5/11) - CPU Scheduling 1, 2

스케쥴링 알고리즘 

- FCFS(first-come-first-served): 선점 후 다쓰고 cpu를 반납함 

- 예시: 일반적인 화장실 대기줄 

단점 예시) 중국집 

먼저 도착한 고객이 5시간 걸리는 음식을 주문한 상황 

뒤에 짜장면 먹으러 온 손님(빨리 걸리는 음식)은 계속 기다려야 함

 

- SJF(shortest-job-first): 짧게 거리는 작업에 먼저 cpu를 할당함 

- 장점: 전체 Q가 짧아짐 

- non-preemptive SJF와 preemptive SJF(SJF중에서도 더 짧은 프로세스가 나오면 거기에 할당함)로 나뉨

- preemptive SJF가 더 옵티멀함 

- 문제점: 긴 프로세스는 계속 cpu를 사용못할 수 있음(starvation), 사용하는 cpu를 계산하지 못함(과거의 데이터로 추정은 가능)

 

- Priorty Scheduling: 우선순위가 가장 높은 프로세스에게 cpu 할당, sjf도 이것 중 하나임 

 

- Round Robbin(RR): 각 프로세스에게 할당 시간을 주고, 끝나면 cpu를 뺏음, 뒤에 가서 다시 할당을 기다림 

- 장점: 응답 시간이 빠름, 공정함 

 

- Multilevel Queue: 우선순위에 따라서 배치를 여러 줄(ready queue를 여러개로 분할)로 하여 cpu를 할당 

- 각 큐는 독립적인 스케줄링 알고리즘을 가짐 

- 단점: 큐에 대한 스케쥴링이 필요, 주어진 우선순위 계급을 거스르지 못함 

 

- Multilevel Feedback Queue: 프로세스가 다른 큐로 이동 가능 

- 주어진 우선순위 계급이 변경 가능(기준 필요)

 

- Multiple-Processor-Scheduling 

- cpu가 여러 개인 경우 스케줄링은 더욱 복잡해짐 

- load sharing: 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요 

 

- Real-Time-Scheduling 

- hard(데드라인이 있음)와 soft(데드라인을 어길 수 있음, 우선순위만 존재)로 나뉨

 

- Thread Scheduling 

- local(운영체제는 cpu를 모름, 사용자 프로세스가 cpu를 할당)과 global(os가 cpu를 할당)로 나뉨 

 

성능척도 

- 시스템 입장)

이용률: 최대한 일을 많이 시키는 것 

처리량: 주어진 시간동안 많은 일을 처리 

 

- 고객입장)

소요시간: 기다려서 작업을 완료한 시간이 짧은 것 

대기시간: 가능한 빨리 서비스를 받는 것 

응답 시간: 처음으로 cpu를 받은 시간이 짧은 것

예시) 중국집 사장이라면 

이용률: 고용한 주방장이 놀지 않는 비율 

처리량: 손님의 수 

소요시간: 고객이 들어와서 주문하고 먹고 나가는 시간 

대기시간: 고객이 음식을 기다리는 시간 

응답시간: 첫번째 음식이 나오는 시간

 

알고리즘 평가 

- Queueing model 

- 확률 분포로 보여지는 지표로 각종 index값을 계산 

 

- 구현 & 성능 측정 

- 실제 시스템에 알고리즘을 구현하여 성능 측정 

 

- 모의 실험 

- 알고리즘을 모의 프로그램으로 작성 후 trace를 입력하여 결과 비교