09. CPU 스케줄링

멀티프로그램 OS 에서의 기본

멀티프로그래밍의 목적

• 각 프로세스들을 동시에 실행시키기 위해
• CPU 효율을 높이기 위해

CPU bust & I/O bust

• CPU bust : running
• CPU bust 가 많은 경우 CPU bound
• I/O bust : waiting → ready
• I/O bust가 많은 경우 I/O bound

⇒ 빈도 수는 CPU-bound 보다 I/O bound 가 더 잦다

CPU scheduler

• 메모리에 올라간 프로세스 중에 누구를 고를것인지 정하는 것
• ⇒ ready 상태의 프로세스들 중에 CPU 를 할당해줄 수 있는 프로세스를 고르는 것
• 다음 프로세스를 어떻게 정할지?⇒ Priority Queue : 우선순위를 정하는 방법은?
• ⇒ FIFO Queue (First-In First-Out)

Preemptive vs Non-preemptive

• Preemptive scheduling : 비선점형, 자발적으로 CPU 를 나올때 까지 나두는 것
• Non-preemptive scheduling : 선점형, 강제적으로 CPU 선점을 뺄 수 있다

CPU-scheduling 할 때의 의사결정

1. running to waiting 상태로 가는 경우
2. running to ready 상태로 가는 경우
3. waiting to ready 상태로 가는 경우
4. terminates 할 때

• 1, 4번 : non-preemtive
• 2, 3번 : preemtive or non-preemtive

dispatcher

• context switch 를 해주는 모듈
• 가능한 빨라야 한다(짧아야 한다)

dispatcher 의 기능

• 한 프로세스에서 다른 프로세스로 문맥교환을 해주는 것
• user mode 를 바꿔주는 것
• 새 프로세스의 적당한 위치로 resume 시켜주는 것

⇒ CPU-scheduler 는 선택을 해주고 스위칭은 dispatcher 가 한다

dispatcher latency

• 프로세스 0 의 실행중이다가 0의 상태를 저장하고, 다음 실행시킬 프로세스 1의 상태를 불러오는 데 까지 걸리는 시간
• dispatcher latency 가 실제로 CPU 를 사용하는 시간보다 짧아진다면 dispatch 가 자주 일어난다
• ⇒ 문제가 일어날 수 있음

context switch 가 얼마나 자주 일어날까?

$ vmstat 1 3 // 1초에 3번 체크 // cpu 위치의 cs를 보면 됨 $ cat /proc/1/status | grep ctxt //voluntary_ctxt_switches : 자발적 스위칭 //nonvoluntary_ctxt_switches : 강제적 스위칭

⇒ Mac OS 에서는 top 이나 vm_stat 명령어를 사용(구체적인내용은 따로 찾아보자)

Checking System Activity on Mac OS X on the Command Line

Checking System Activity on Mac OS X on the Command Line

스케줄링의 목적

• CPU utilization : CPU 효율성, 가능한 바쁘게 유지하기
• Throughput : 단위시간내 프로세스완료 숫자를 최대화
• Turnaround time : execute ~ completion 시간을 최소화
• Waiting time : 어떤 프로세스가 ready queue 에 대기하고 있는 시간을 최소화
• Response time : 응답 시간 최소화

CPU scheduling 문제

• ready queue 에 있는 프로세스중 어느 프로세스를 고를 것인가?

해결법

• FCFS : First-Come, First-Served, 먼저 온 순서대로 ⇒ 요즘엔 잘 안씀
• SJF : Shortest Job First, 짧은 일을 먼저 (SRTF : Shortest Remaining Time First, 남은시간이 짧은 일을 먼저 하자)
• RR : Round-Robin, 시분할(time-sharing)
• Priority-based : 우선순위 부여
• MLQ : Multi-Level Queue : 어떤경우는 이거 어떤경우엔 저거
• MLFQ : Multi-Level Feedback Queue : MLQ 에서 피드백이 추가

FCFS 스케줄링

• CPU 를 먼저 요청한 프로세스에게 할당해주는 것

• • ⇒ Gantt Chart
  • 대기시간 : P1 = 0, P2 = 24, P3 = 27
  • ⇒ total = 51, 평균 17초 대기
  • turnaround time : P1 = 24, P2 = 27, P3 = 10
  • ⇒ total = 81, 평균 27
• 긴 프로세스가 먼저 올때 minimal 해지지 않는다,
• non-preemtive
• Convoy Effect : (화물차 효과) 앞의 큰 차때문에 뒤의 차들이 못가는것 처럼,,

SJF

• 시간이 짧은 일부터 먼저 스케줄링 하는 것
• CPU 가 사용가능 할 때 CPU bust 가 가장 짧은 것을 먼저 스케줄링
• 평균 waiting time 방면에서는 (최소)최적이다.