[OS]운영체제_6

CPU 스케쥴링

CPU 스케쥴링

• Reedy Que안에 혹은 메인메모리에 여러개의 프로세스가 줄서서 기다리고 있을때 현재 실행하는게 끝나면 그다음 어느프로세스를 선택하고 결정

• Preemptive vs Non-preemptive(선점 vs 비선점)
  • Preemptive(선점) : CPU가 어떤 프로세스를 실행하고잇는데 강제로 쫒아내고 새로운것이 들어갈수 있는방식(응급환자)
  • Non-preemptive(비선점) : 이미 어떤 프로세스가 실행중에있으면 끝나거나 I/O를 만나기 전에는 절대 스케쥴링이 안일어남
• Scheduling criteria (척도,어떤스케쥴링방식이 더좋은가)
  • CPU Utilization (CPU 이용률 %)
  • Throughput (처리율) : 시간당 몇개의 작업을 처리하는가 (시간당몇개)
  • Turnaround time (반환시간) : 작업이 Ready Que에 들어가서 나오는시간(병원에 들어간 시간부터 진료다받고 나오는시간)
  • Waiting time (대기시간) : CPU의 서비스를 받기위해 Ready Que에서 얼마나 기다렸는가
  • Response time (응답시간) : 인터렉티브 시스템에서 중요함,처음응답이 나올때까지 중요한시간

CPU Scheduling Algorithms

• First-Come, First-Served (FCFS) : 먼저온놈 먼저서비스
  • Simple & Fair (간단, 공평)
  • 단점 : 평균대기시간이김, 짧은놈부터 실행하는게 오히려 속도가 더빠름
  • Convoy Effect (호위효과) : 긴 프로세스가 있으면 나머지 대기하고있는 프로세스가호위하듯이 따라간다
  • Nonpreemptive scheduling
  • Example: Find Average Waiting Time AWT = (0+24+27)/3 = 17 msec

Gantt Chart

Process	Burst Time (msec)
p1	24
p2	3
p3	3

• Shortest-Job-First (SJF) : 작업이 짧은놈을 먼저서비스
  • Shortest-Remaining-Time-First
  • 대기시간을 줄이는데 가장좋은 방법
  • 단점 : 비 현실적(예측을 할수없음)
  • Preemptive or Non-preemptive(선점 or 비선점)
  • Example: AWT(Average Waiting Time) = (3+16+9+0)/4 = 7 msec cf. 10.25 msec (FCFS)

Process	Burst Time (msec)
p1	6
p2	8
p3	7
P4	3

• Priority : 우선순위대로 먼저 서비스
  • Low number represents high priority in general (Unix/Linux)
  • 우선순위 정하는기준(내부 , 외부)
  • 내부 : time limit,Memory requirement ,I/O to CPU burst
  • 외부 : amount of funds being paid, political factors
  • 단점 : (기아,굶어죽음) 우선순위가 낮은 프로그램은 계속기다림
  • 해결방법 : (aging)오래기다릴수록 우선순위를 올려줌
  • AWT = (6+0+16+18+1) / 5 = 8.2 msec

Process	Burst Time (msec)	Priority
p1	10	3
p2	1	1
p3	2	4
P4	1	5
P5	5	2

• Round-Robin (RR) : 돌면서 순서대로 서비스
  • 일정시간이 기준으로 프로세스 변경
  • 타임퀀텀(일정시간)이 무한대로돌면 FCFS와 동일
  • 타임퀀텀(일정시간)이 0에 수렴하면 오버헤드 발생
  • Time-sharing system (시분할/시공유 시스템)
  • Time quantum 시간양자(=Time slice)
  • Preemptive
  • Example AWT = (6+4+7)/3 = 5.66 msec

Time Quantum = 4msec

Process	Burst Time (msec)
p1	24
p2	3
p3	3

• Multilevel Queue : 큐를 여러개
  • 프로세스를 그룹화 (System process , Interactive process ,Interactive editing process, Bacth process, Student process)
• Multilevel Feedback Queue : 큐를 여러개
  • 하나의 Queue에서 머무르는것이아닌 다른 Queue로의 점진적이동
  • 모든 프로세스는 하나의 입구로 진입
  • 너무 많은 CPU time 사용 시 다른 Queue 로
  • 기아 상태 우려 시 우선순위 높은 Queue 로