CPU 스케쥴러

운영체제는 준비완료 큐에 있는 프로세스들 중에서 실행될 프로세스를 선택해서 CPU를 할당해야 한다. CPU 스케줄링은 프로세스가 다음과 같을 때 발생할 수 있다.
1.러닝 상태에서 wait 상태로의 전환(I/O작업을 해야 한다는 뜻)
2.러닝 상태에서 레디 상태로 전환 (주로 인터럽트 발생으로 인해 프로세스가 다시 레디 큐로 들어간다.)
3.wait 상태에서 ready 상태로 전환 (I/O작업이 종료 됐을 때)
4.프로세스 종료. 상황 1과 4일 때는 스케줄링 측면에서 선택의 여지가 없이 새로운 프로세스(준비완료 큐에 하나라도 존재할 경우)가 반드시 선택되어야 한다. 그러나 상황 2와 3에서는 선택의 여지가 있다.

💡 스케쥴링 방식

1. Nonpreemptive(비선점형) - CPU가 프로세스를 실행하면 프로세스가 끝나기 전까지 CPU를 뺏어올 수 없다. 상황1과 상황4에서만 스케쥴링이 일어나면 비선점 방식이다.

2. Preemptive(선점형) - 만약 새로운 프로세스가 지금 실행중인 프로세스보다 더 작으면, 지금 처리 중인 프로세스가 중지되고 새로 들어온 것부터 처리한다.

📌 스케쥴링 기준

1. CPU utilization(이용률) - CPU 이용률이 효율적이도록 바쁘게 만든다.
2. Throughput(처리량) - 단위 시간당 완료된 프로세스의 개수가 많도록 한다.
3. Turnaround time(총처리 시간) - 특정 프로세스가 시작되고부터 종료되는데 까지 걸리는 시간
4. Waiting time – CPU 스케줄링 알고리즘은 프로세스가 실행하거나 입출력하는 시간에는 영향을 미치지 않는다. 오직 프로세스가 레디 큐에서 대기하는 시간의 양에만 영향을 준다. Waiting time은 레디 큐에서 대기하면서 보낸 시간의 합이다.
5. Response time (응답 시간) - 어떤 프로세스가 시작되고 반응을 보이는 데까지 걸리는 시간.

• CPU 사용 효율과 처리율은 최대화하고 반환시간, 대기시간, 응답 시간은 최소화하는 알고리즘이 가장 이상적이다.

📌 스케쥴링 알고리즘

🎈 선입 선처리 스케줄링(First-Come, First-Served Scheduling)

• 가장 간단한 알고리즘으로 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 이 알고리즘은 비선점 방식이다. 단점으로는 convoy 효과가 발생할 수 있다는 점이다. 호위효과(convoy)는 하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 현상을 말한다.

🎈 최단 작업 우선 스케줄링(SJF, Shortest-Job-First Scheduling)

• 가장 작은 작업을 먼저 하겠다. CPU가 이용 가능해지면, 다음 CPU 버스트 시간이 가장 작은 프로세스에게 할당한다. 두 프로세스의 다음 CPU 버스트가 같다면, 순위를 정하기 위해 선입 선처리 스케줄링을 적용한다. 이 알고리즘은 평균대기시간 측면에서는 최적에 가장 가깝다. 하지만 프로세스의 다음 CPU 버스트 시간을 예측하는 것에 큰 어려움이 있다.

• 선점 SJF 알고리즘은 새 프로세스가 준비완료 큐에 도착하면 이 프로세스의 다음 CPU 버스트사간과 현재 수행중인 프로세스의 남은 CPU버스트 시간을 비교한다. 이때 새 프로세스의 다음 시간이 수행중 프로세스의 남은 시간보다 적으면 기존 프로세스를 강제종료하고 새 프로세스를 할당한다. 이는 Shortest-Remaining-Time-First(SRTF)로 불린다. SJF는 waiting time을 최소화 가능한 알고리즘이다.

🎈 우선순위 스케줄링(Priority Scheduling)

• 0에 가까울수록 우선순위가 높다. 여기서도 선점형 비선점형이 있으며 비선점형은 새로운 프로세스가 들어와도 처리 중인 프로세스는 끝까지 작업을 마친다. SJF는 우선순위 스케줄링이다. 우선순위 스케줄링의 문제는 낮은 우선순위의 프로세스는 영원히 실행되지 못 할 수도 있다는 것이다. 해결책으로는 Aging기법으로 시간이 지나면 우선 순위를 높여주는 것이 있다.

• 선점형 우선순위 방식은 위 SRTF와 마찬가지로 작동한다.

🎈 라운드 로빈(Round Robin, RR)

• 라운드 로빈 스케쥴링 알고리즘은 시분할 시스템에서 사용하는 알고리즘이다. RR은 기본적으로 선점방식이다. 각 프로세스들은 CPU 할당 시 CPU를 사용할 수 있는 시간이 정해진다. 시간 안에 안 끝나면 무조건 중지되고 큐의 맨 뒤로 가서 다시 기다리게 된다. 레디 큐에 n개의 프로세스가 있고 시간 할당량이 q라면 최대 q 시간 단위의 조각으로 1/n CPU time을 가진다. q가 크면 FIFO 성질을 갖게 된다. q가 너무 작으면 context switching을 많이 하게 돼서 오버헤드가 너무 높아진다. 일반적으로 SJF보다는 높은 turnaround time을 보이지만, 응답 시간은 짧다. q의 설정은 여러 프로세스 중 하나를 뺀 나머지 프로세스는 한 번의 퀀텀값 안에 끝나는 정도의 time quantum값을 주는 것이 좋다. time quantum에 따라 일관되지 않는 결과가 나온다.