6. 스케줄링

1. 스케줄링

 

개념: 다중 프로그래밍의 목적은 항상 실행할 수 있는 프로세스가 있도록 하여 CPU 사용 효율을 극대화 하는데 있다.

 

CPU - I/O 버스트 주기

프로세스는 실행되는 동안 CPU 실행과 입출력 대기라는 두 주기를 반복한다.

계산 중심 프로세스의 경우 적은 수의 매우 긴 CPU 버스트를 가지며, 입출력 중심 프로세스는 많은 수의 짧은 CPU 버스트를 가진다.

 

CPU 스케줄러

CPU가 유휴 상태가 되면 준비완료 큐에 있는 프로세스를 하나 선택해서 실행한다. 이 선택은 단기 스케줄러가 한다.

CPU 스케줄링에 대한 결정은 4가지 상황에서 일어난다.

 

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때(입출력 요청, 자식 프로세스들 중 하나가 종료되는것을 기다리기 위해 wait를 호출할 때)
2. 프로세스가 실행 상태에서 준비완료 상태로 전환될 때(인트럽트 발생)
3. 프로세스가 대기 상태에서 준비완료 상태로 전환될 때(입출력 완료)
4. 프로세스가 종료할 때 

 

• 비선점(nonpreemptive) 스케줄링: 프로세스가 CPU에 할당되면 그 프로세스가 종료되거나 대기중 상태로 전환될 때까지만 CPU를 점유한다. 실행을 위해서는 반드시 새로운 프로세스가 선택되어야 한다. 
• 선점(preemptive) 스케줄링: 이와는 반대로 선택의 여지가 있다. 특정 조건이 만족되면 현재 실행중인 프로세스의 의사와 상관없이 실행을 중단하고 다른 프로세스를 CPU에 할당한다. 실행중인 프로세스를 중단하면 문제가 발생할 수 있기에 이를 대비해야 한다.

 

정리하자면 1과 4는 non-preemptive 하기 때문에 새로운 프로세스가 할당되어야 하지만, 2와 3은 preemptive해야 할 수 있다. 

 

Dispatcher

스케줄러가 선택한 프로세스를 CPU에 할당해주는 요소를 말한다. 디스패처는 문맥전환 + 모드 전환의 임무를 맡고 있다.

디스패처가 하나의 프로세스를 중단하고 다른 프로세스를 실행하기까지 걸리는 시간을 패치 지연이라 한다.

 

2. 스케줄링 기준

User-Oriented scheduling  (Minimize)

• 전체 처리 시간 (turnaround time) : 하나의 프로세스가 제시된 시점에서 종료 될 때까지 걸린 시간으로, 메모리에 적재되기 위해 기다리며 소비한 시간+준비완료 큐에서 대기한 시간+CPU에서 실행한 시간+입출력 시간
• 대기 시간 (waiting time) : 한 프로세스가 준비완료 큐에서 대기한 총 시간
• 응답 시간 (response time): 서비스를 요청한 후에 그 서비스에 대한 첫 반응이 나오기까지 걸린 시간

평균 응답 시간(요청 접수 후 응답 시작까지의 시간)을 최소화하는 동시에 적절한 응답을 받는 대화형 사용자 수를 최대화합니다.

---

System-Oriented scheduling  (Maximize)

• 처리율 (throughput) : 시간당 완료되는 프로세스의 수
• CPU 사용 효율 (CPU utilization) : CPU를 얼마나 효율적으로 사용했는가, 안쉬고 작업했다면 100%

 

시스템 관점에서는 최대화하고 사용자 관점에서는 최소화하는 알고리즘이 이상적이다.

 

추가로

• fairness: 어떤 프로세스도 starvation이 없어야 한다. (하지만, response time을 줄이기 위해 덜 공정할 수 도 있다.) 
• Balance resource: keep all resources of the System busy

Other (non-performance related) system- oriented scheduling policy goals:

 

3. 스케줄링 알고리즘

• 선점 - SRTF, 우선순위, RR, MLQ(RR+우선순위), MLFQ(MLQ+큐들 사이 이동 허용)
• 비선점 - FCFS, SJF, 우선순위

1)FCFS(First-Come First-Served)

먼저 요청한 프로세스 순으로 스케줄링 한다.  FIFO 큐를 이용하여 구현
convoy effect 발생 가능하다. 하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 현상을 말한다.

• Non-preemptive
• Response time: slow if there is a large varaiance in process execution times -> 한 프로세스가 CPU를 지나치게 오래 점유 = convoy effect
• Throughput: low
• Fairness: short process & I/O bound process에게 penalty
• Starvation: 발생 안함, 순차적이므로
• Overhead: minimal, context switching이 거의 일어나지 않음

 

2)SRTF(Shortest-Remaining-Time-First)

다음 CPU버스트 시간이 가장 짧은 프로세스 순으로 스케줄링한다.

프로세스가 같은 CPU 버스트 시간을 가지면 FCFS 정책을 따른다.

• Preemptive
• Response time: 좋은 편이다. process가 동적으로 할당될 때 평균 waiting time을 최소화 해준다.
• Throughput: 높다. 짧은거 먼저 실행하므로
• Fairness: long process들이 penalty. 그러나 긴 애들도 서서히 짧아질 있다.
• Starvation: long process들에게 있을 수 있다.
• Overhead: 클 수 있다. context swtiching and recording and estimating  CPU burst times 

 

 

3)SJF(Shortest-Job-First)

새 프로세스가 준비완료 큐에 도착하면 이 프로세스의 다음 CPU 버스트 시간과 현재 수행중인 프로세스의 남은 CPU 버스트 시간을 비교하여, 새 프로세스의 다음 시간이 수행 중 프로세스의 남은 시간보다 적으면 기존 프로세스를 강제로 종료하고 새 프로세스를 할당한다.

tie일 경우, FCFS를 사용한다. 프로세스의 과거 성능과 예측을 기반으로 길이를 예측하기에 근사치를 사용한다.

• Non-preemptive
• Response time: good for short proecesses. FCFS보단 좋아졌으나 긴 프로세스가 짧은 프로세스 앞에서 실행시 오래 기다려야한다
• Throughput: 높다.
• Fairness: long process들에게 penalty
• Starvation: long process들에게 있을 수 있다
• Overhead: 클 수 있다. recording and estimating  CPU burst times 

 

4)Priority Scheduling(현재 OS에서 사용하는 것)

우선순위는 중요도, 돈, 정치 등을 기준으로 외부적으로 정의

우선순위는 메모리 요구 사항, 파일 요구 사항, CPU 요구 사항 vs I/O 요구 사항 등에 따라 내부적으로 정의

SJF 또한 일종의 priority가 존재하는 것이다.  

Priority Scheduling는 preemtpive(Mac, Windows)도 되고, non-preemptive(임베디드컴퓨터, 실시간 OS의 경우)도 된다. 

• 프로세스가 ready queue도착 시 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스와 비교하여 바꾸는 preemptive
• 준비완료 큐의 head에 새로운 프로세스를 넣는 non-preemptive

starvation: low-priority procsses에게 발생 가능하며, 이를 해결하기 위해 aging 기법을 사용한다.

• aging

오랜 시간 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법 (Ready queue에서 기다리는프로세스에 대해서, 따라서 I/O 하면서 있는건 대기시간이 아니다.)

Priority는 PCB에 저장된다.

 

5)라운드로빈

시분할 시스템을 위해 설계

time slice ( = time quantum)을 정의하고, 해당 프로세스를 최대한 time slice동안 실행하고, 이 사이에 완료되지 않으면 ready queue의 tail에 추가한다.

time slice안에 완료되면 ready queue의 head에서 다른 프로세스를 선택하고 해당 프로세스를 time slice동안 실행한다.

ready queue는 원형큐로 동작한다. CPU 스케줄러는 ready queue에서 첫번째 프로세스를 선택해 한 번의 time slice 이후에 인트럽트를 걸도록 타이머를 설정한 후, 프로세스들을 dispatch

• Preemptive
• Response time: 짧은 프로세스들에게 좋다. 긴 프로세스들은 기다려야 할 수도 있다.
• Throughput: time slice에 의해 결정된다.
  • time slice가 너무 작으면 context switching이 너무 자주 일어나서 안좋다.
  • 너무 크면 FCFS와 동일해진다.
• Fairness: I/O bound process에게 penalty(I/O bound process가 CPU에서의 실행시간을 모두 사용하지 못하고 I/O 작업을 수행하는 동안 일부 시간이 낭비 될 수 있다.) -> 동시병렬성 좋아진다.(새끼 CPU들이놀지않게 되기때문)
• Starvation: 일어나지 않는다. 모두 동일한 time slice를 가지기 때문
• Overhead: 낮다. 기계적으로 다음거 돌리기에 낮은편

 

6)다중레벨 큐 스케줄링(MLQ)

앞에서는 기본적으로 Ready queue가 한개이다. 이제, 준비완료 큐를 여러 개의 큐로 나누어 사용한다.

프로세스의 특성에 따라 특정 큐에 할당되며, 이때 각 큐는 독자적인 스케줄링 알고리즘을 사용한다.

preemptively or non-preemptively

foreground -  background

 

쉘에서 ps치면프로세스가다보이는데, 이는foreground

background로 돌리려면 &로 돌리면된다.

System(kernel process 3가지: scheduler, Pager ), interactive(e.g. office, game), editing, computing

e.g. 80% of CPU time to foreground, using RR & 20% of CPU time to background, using FCFS

1) 상위 우선순위 큐는 하위 우선순위 큐보다 절대적 우선순위를 가지도록 할 수 있다. 이때, preemptive하다.

2) 큐 간에 일정 비율로 CPU 시간을 할당해 줄 수 있다.

 

7)다중레벨 피드백 큐 스케줄링(MLFQ)

MLQ는 유연성이 떨어진다는 단점이 있다. (프로세스들이 시스템 진입 시 영구적으로 하나의 큐에 할당되고 다른 큐로 이동불가)

이와달리 MLFQ는 프로세스가 큐간에 이동할 수 있도록 해준다. 즉, 어떤 프로세스가 CPU를 너무 많이 사용하면 낮은 우선순위 큐로 이동할 수 있다는 것이다.

preemptively or non-preemptively

CPU 버스트 시간 특성이 다른 프로세스들을 분리하여 starvation과 convoy effect를 제거하는 것이 주 목표이다.

대화식 프로세스와 입출력 중심 프로세스는 상위 큐에 할당되고 CPU 중심 프로세스는 하위 큐에 할당된다.

MLFQ를 결정하는 파라미터로는 큐의 개수, 각 큐의 스케줄링 알고리즘, 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법, 프로세스를 낮은 우선순위 큐로 내려주는 시기를 결정하는 방법, 프로세스가 준비완료 큐에 들어올 때 어떤 큐에 할당할지를 결정하는 방법이 있다.

우선순위가 높은 큐에서 각 프로세스를 시작하고, 각 CPU 버스트가 완료되면 우선순위가 낮은 큐로 이동
오래된 프로세스는 우선순위가 높은 큐로 이동 -> aging과 비슷한 방식으로 starvation 예방

Feedback = 과거를 사용하여 미래를 예측 - 과거에 CPU를 많이 사용하지 않은 작업(SRT에 가까운 작업)을 선호

• Kernel processes have negative values.
• Userprocesses have positive values.

참고문헌

https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/6_CPU_Scheduling.html

Operating Systems: CPU Scheduling