[OS] CPU Scheduling algorithm

선점? 비선점?

선점(preemptive): 우선순위가 높은 작업이 오거나, 해당 작업이 더 우선되어야 한다고 판단되면 해당 작업에게서 CPU를 빼앗을 수 있다.

비선점(non-preemptive): 일단 CPU를 할당받으면 해당 프로세스가 끝날때까지 CPU를 빼앗기지 않는다.

 

 

Scheduling algorithm

1. FCFS(Fisrt come First Served)
   • 특징
     • 선입선출 비선점형스케줄링 비효율적
   • 단점
     • 응답시간이 길어질 수 있음Convoy Effect(호위 효과)
       👉🏻 Short process behind long process, 처리시간이 오래걸리는 프로세스가 먼저 할당되어버리면 그 작업이 끝날 때 까지 다른 프로세스들은 마냥 기다리는 현상
2. SJF(Shortest Job First)
   • 특징
     • CPU burst time이 짧은 작업을 우선으로 할당하는 방법
     • 각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 할당
       👉🏻 일종의 우선순위 기법 priority = predicted next CPU burst time
     • 비선점형(SJF)과 선점형(SRTF) 방식이 있음
     • 최소 평균 대기 시간을 보장한다.
   • 단점
     • Starvation(기아 현상) 발생 가능성이 있음
3. SRTF or SRF(Shortest Remaining Time First)
   • 특징
     • SJF의 선점형 스케줄링 방식
     • 남은 프로세스의 burst time보다 더 짧은 process가 도착하면 CPU를 빼앗음
   • 단점
     • Starvation
     • 새로운 프로세스가 들어올 떄마다 스케줄링이 변경되므로 CPU 사용시간(burst time)을 정확히 예측하기 어렵다.
4. Priority Sceduling
   • 특징
     • highest priority를 가진 프로세스에게 CPU를 할당
     • 👉🏻 highest priority = smallest inteager*
     • 선점형 방식에서는 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스보다 높으면 CPU를 선점한다.
     • 비선점형 방식에서는 더 높은 우선순위의 프로세스가 들어오면 Ready queue의 head 부분에 넣는다.
   • 단점
     • Starvation
     • 무한 정지(infinite blocking) : 프로세스가 CPU를 사용할 준비가 되었지만 우선순위가 낮을 경우 무한 대기하는 상태가 되는 것
       👉🏻 [해결법] Aging 기법으로 큐에 남아있었던 시간으로 가중치를 부여해, 해당 문제점을 해결할 수 있다.
5. RR(Round Robin)
   • 특징
     • 현대식 기법으로 시분할 시스템을 위해 설계되었다.
     • 선점형 스케줄링 기법
     • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지고, 할당 시간이 지나면 프로세스는 선점 당하고 Ready queue의 맨 뒤로 가게 된다.
     • n개의 프로세스가 Ready queue에 있고 할당시간이 q time unit이라면 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
     • 👉🏻 어떠한 프로세스도 q time unit 이상 기다리지 않는다. 공정한 알고리즘이다.*
     • CPU 사용시간이 랜덤할때 더욱 효율적이다.
     • 문맥교환을 통해 프로세스의 Context를 저장할 수 있기 때문에 가능한 기법이다.
     • 평균 대기 시간(Average Waiting Time)은 조금 길어질 수 있으나, 응답시간(Response)이 짧아진다.
   • 단점
     • q time unit이 커지면 FCFS와 같아져 비효율적일 수 있다.
     • q time unit이 지나치게 작으면, 문맥교환이 대량으로 발생해 오버헤드가 증가한다.