CPU 스케줄링

CPU 스케줄링이란?

메모리에 올라온 프로세스들 중 어떤 프로세스를 먼저 처리할지 순서를 정하는 일

CPU의 이용률을 높이고, 작업처리 능력을 향상시키고, 응답 시간을 최소화 함.

<br/>

용어정리

• CPU 버스트 : CPU 사용시간

• 대기시간 : ready 상태에서 대기한 시간

• 응답시간 : 프로세서 사용 요청후, 첫 응답 받을 때까지의 시간. (대기시간 + 서비스받을시간)

<br/>

<br/>

<br/>

선점형 알고리즘 & 비선점형 알고리즘

• 선점형 알고리즘

• 한 프로세스가 CPU를 차지하고 있을때, 높은 우선순위의 프로세스가 CPU를 요청한다며,<br/>
  현재 프로세스를 중지 시킨후, 자신이 CPU를 자치 할 수 있음

• 장점 : 빠른 응답시간을 요구하는 시분할 시스템에 유용

• 단점 : 높은 우선순위의 프로세스가 많을 경우, 잦은 컨텍스트스위칭으로 오버헤드가 발생 할 수 있음

• Round Robin, SRTF, Multi Level Queue, Multi Level Feedback Queue<br/>

• 비선점형 알고리즘

• 한 프로세스가 CPU를 차지하고 있으면, 다른 프로세스가 이를 차지 할 수 없음

• 장점: 모든 프로세스가 공정하고, 응답시간 예측이 가능함

• 단점 : 짧은 작업을 수행하는 프로세스가, 긴 작업이 종료될때까지 기다려야함

• FCFS, SJF, HRN,

<br/>

<br/>

알고리즘

• FCFS(First Come, First Served) = FIFO(First In, First Out), 선입선처리 스케줄링

• 비선점, 가장 간단한 알고리즘

• 먼저 ready 큐에 들어온 프로세스를 먼저 처리함.

• 평균 대기 시간이 길어 질 수 있음.

• 예를들어 100 burst time을 가진 프로세스가 먼저 들어왔다며, 1 burst time을 가지는 다음 프로세스는 100 burst time을 기다려야함.<br/>

<br/>

• SJF(Shortest-Job-First) , 최소 작업 우선 스케줄링

• 비선점

• 가장 짧은 CPU burst를 가지는 프로세스를 우선 선택

• 가장 짧은 평균 대기시간.

• 가장 긴 프로세스가 무한히 대기할 가능성이 있음.<br/>

• HRN(Highest Response ratio Next)

• 비선점, SJF의 긴 프로세스와 짧은 프로세스의 단점을 보완한 스케줄링

• 우선순위를 (대기시간 + 서비스받을시간)/ 서비스시간으로하여, 우선순위가 높은 프로세스부터 선택됨** **<br/>

• Priority, 우선순위 스케줄링

• 선점, 비선점

• 우선순위가 높은 프로세스를 먼저 실행함

• 우선순위가 같은 프로세스는 FCFS 알고리즘을 사용

• 낮은 우선순위의 프로세스가 무한히 기다리는 상태가 생길 수 있음

• 오래동안 대기한 상태의 프로세스를 우선순위를 점차 올려주는 것으로 해결. "에이징" 기법이라함<br/>

• SRTF(Shortest Remain Time-First), 최소 잔여시간 우선 알고리즘

• 선점형

• ready큐에 현재 실행중인 프로세스 A의 잔여 CPU burst보다<br/>
  더 짧은 CPU Burst를 가진 프로세스 B가 ready 큐에 도착하면 B가 CPU를 차지함.<br/>

• RR(Round Robin), 순환 할당 알고리즘

• 선점형, 시분할 시스템을 위혜 설계됭

• 시간할당량을 정해, 이 시간할당량 동안만 실행하며, 실행 후 완료되지 않으면 CPU를 양보하고, 가장 뒤에 배치

• 시간할당량이 무한히 크다면 FCFS랑 같음.

• 너무 짧은 시간할당량은 잦은 컨텍스트스위치로 오버헤드가 발생한다.

• 시간할당량은 컨텍스트스위치 시간 보다 어느정도 커야 한다.<br/>

• Multelvel Queue Schduling, 다단계 큐 스케줄링

• 선점형

• ready큐를 다수의 독립큐로 분산하며,

• 독립 큐간에는 우선순위를 가지고, 각 독립큐는 자신만의 스케줄링 알고리즘을 가지도록하낟.

• 우선순위가 낮은 큐는 기아상태가 발생 할 수 있다.<br/>

• Multelvel Feedback Queue Schduling, 다단계 피드백 큐 스케줄링

• ​​​​​​​선점형

• 다단계 큐에서 큐 사이에 프로세스 이동을 가능하게 함

• 너무 오랫동안 CPU를 차지하는 프로세스는 우선순위가 낮은 큐로 이동

• 너무 오래 대기하는 프로세스는 우선순위가 높은 큐로 이동

• 가장 일반적인 CPU 스케줄링 알고리즘

<br/>

<br/>

<br/>

<br/>

<br/>

<br/>

​​​​​​​