CPU 스케줄링 알고리즘, Scheduling Algorithms [운영체제]

 

여러가지 알고리즘이 있는데?

 

몇 개만 맛만 보자

 

---

 

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다.

여러 가지 다른 CPU스케줄링 알고리즘들이 있다. 

 

1. 선입 선처리 스케줄링 (First Come First-Served Scheduling)

2. 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

3. 라운드 로빈 스케줄링(Round-Robin Scheduling)

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

5. 다단계 큐 스케줄링(Multilevel Queue Scheduling

6. 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)

 

몇개만 보자

 

**알고 들어가야할 용어가 있다.

 

Gantt Chart, 간트 차트라고 하는데

참여한 각 프로세스의 시작 시각과 종료 시각을 포함하여 특정 스케줄 기법을 표현하는 막대형 그래프이다.

 

 

---

 

1번부터 보자

 

FCFS라고도 한다.

 

선입 선처리라고 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는 것이다.

 

선입 선처리 정책의 구현은 선입선출(FIFO)큐로 쉽게 관리할 수 있다.

 

프로세스가 준비 큐에 진입하면, 이 프로세스의 프로세스 제어 블록(PCB)을 큐의 끝에 연결한다.

CPU가 가용상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당된다. 

이 실행 상태의 프로세스는 이어 준비 큐에서 제거된다. 

 

** 단점이라면 선입 선처리에서 평균 대기시간이 좀 많이 길 수도 있다.

 

이렇게 들어올 수도 있지만

반대로 이렇게 들어올 수 있다.

 

 

 

분명 종료시각은 같은데 평균 대기시간이 

 

3ms, 17ms로 많이 차이난다.

++ 컴퓨터에서 14ms는 꽤나 큰 숫자다.

 

++만약 동적인 상황이라면?

 

하나의 CPU bound 프로세스와 많은 I/O bound 프로세스를 가진다고 하면

1. CPU 중심 프로세스가 CPU를 할당받아 점유하는데

2. 그동안 I/O프로세스는 I/O를 끝내고 준비 큐로 이동해서 CPU를 기다릴 것이다. // I/O 장치는 쉬고 있다.

3. CPU 중심 프로세스가 자신의 CPU burst를 끝내고 I/O장치로 간다.

4. I/O 중심 프로세스는 CPU burst가 짧다.

5. 그러나 CPU 중심 프로세스는 I/O 후 다시 CPU를 할당받는다.

 

위에 상황처럼

 

다른 프로세스들이 하나의 긴 프로세스가 CPU burst를 기다리는 것을 호위 효과(Convoy effect)라고 한다.

 

**선입 선처리 스케줄링 알고리즘은 비선점형(nonpreemptive)이다.

 

**대화형 시스템에서는 정말 비효율적이다.

 

---

 

2번은 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

 

SJF라고 부른다.

 

• Associate with each process the length of its next CPU burst
1. Use these lengths to schedule the process with the shortest time

 

• SJF is optimal – gives minimum average waiting time for a given set of processes
1. The difficulty is knowing the length of the next CPU request
2. Could ask the user

 

이 알고리즘은 각 프로세스에 다음 CPU burst 길이를 연관시켜서

 

CPU가 이용가능한 상태가 되면 가장 작은 다음 CPU burst를 가진 프로세스에 할당한다.

 

** 만약 두 개 이상의 프로세스가 burst 길이가 같으면 순위를 정하기 위해 선입 선처리를 적용한다.

 

이 스케줄링은 프로세스 전체길이가 아니라 다음  CPU burst의 길이에 의해 스케줄링 된다.  

 

 

이 차트로 위의 개념을 적용시켜보면 똑같이 나온다.

 

**SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다. (증명되었다)

 

SJF 알고리즘이 최적이긴 하지만, 다음 CPU의 burst 길이를 알 방법이 없어서

CPU 스케줄링 수준에서는 구현할 수 없다.

 

그래서 CPU burst값을 알 수는 없지만 예측하는 방법으로 구현한다.

 

우리는 다음 CPU burst 길이가 이전의 CPU burst 와 비슷하다고 기대하고 근삿값을 계산해 

가장 짧은 예상 CPU burst를 가진 프로세스를 선택한다.

 

CPU 버스트는 일반적으로 이전의 CPU 버스트의 길이를 지수 평균한다고 생각하고하자

 

다시 말해서

 

이렇게 식을 두고 풀어나가보자

 

 

 

짧게하자면 이렇게

 

 

 

 

+++++++

SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 

앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생하기 마련이다.

 

새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있다.

 

선점형 SJF 알고리즘은 현재 실행하는 프로세스를 선점할 것이고

 

반면에 비선점형 SJF 알고리즘은 현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다.

 

** 선점형은 때로 최소 잔여 시간 우선(shortest remaining time first)라고도 한다.

 

도착시간이 더해져 있는 차트이다.

 

 

** 만약 비선점형이었다면 7.75ms 가 될 것이다.

 

 

 

---

 

3번째로는 라운드 로빈 스케줄링 (Round-Robin Scheduling)

 

사람 이름이겠거니 싶다. RR로 불리곤 한다.

 

• Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

 

• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits for more than (n-1)q time units.

 

• Timer interrupts every quantum to schedule next process

• Performance
1. q large -> FIFO
2. q small -> q must be large with respect to context switch, otherwise overhead is too high

 

 

선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨다닐 수 있도록 선점이 추가되었다.

 

시간 할당량(time quantum), 타임 슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다.

 

++시간 할당량은 일반적으로 10-100 ms다.

 

준비 큐는 원형 큐로 되어있고 CPU 스케줄러는 준비큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.

 

RR을 위해  준비 큐가 선입선출 큐로 동작하게 만들어야 한다.

++새로운 프로세스들은 준비 큐의 꼬리에 추가된다. 

 

CPU스케줄러는 준비 큐에서 첫 번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머(timer)를 성정한 후 프로세스를 디스패치(dispatch)한다. 

 

그렇게 설정한다면 2가지 경우가 발생할 것인데

 

1. 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 작은 경우

2. 현재 실행 중인 프로세스의 CPU 버스트가 한 번의 시간 할당량보다 긴 경우

 

1번의 경우에는 CPU가 자발적으로 방출되어 다음 프로세스로 진행될 것인데??

 

2번의 경우는 타이머가 끝나고 인터럽트를 걸어서 문맥 교환이 일어나고 그 후 실행하던 프로세스는 준비 큐의 꼬리에 넣어지고 CPU 스케줄러는 다음 프로세스를 선택할 것이다.

 

그래서 RR 알고리즘은 때때로 평균 대기시간이 조금 길다.

 

한 번 보자

 

한번에 4ms씩 도는 거 알겠지? 

 

RR알고리즘에서는 유일하게 실행가능한 프로세스가 아니라면 연속적으로 두 번 이상의 시간 할당량을 받는 프로세스는 없다.  // 위의 경우는 P1밖에 없으니까 그렇다는 얘기다.

 

**RR 알고리즘은 시간 할당량의 크기에 따라 영향을 받는다.

**만약 극단적으로 시간 할당량이 커버리면 선입 선처리랑 같아진다.

**만약 극단적으로 짧아도 문맥교환일어나는 시간이 많아지면 그냥 비효율적 갖다버려야한다.

 

RR알고리즘을 쓸 때 목표는 문맥교환 시간보다는 시간 할당량이 더 커지는 것을 추구해야한다.

 

 

 

 

 

---

 

4번째로 우선순위 스케줄링, Priority Scheduling

 

• A priority number (integer) is associated with each process 

 

• The CPU is allocated to the process with the highest priority (smallest integer == highest priority) 
1. Preemptive 
2. Non-preemptive 

 

• SJF is a priority scheduling where priority is the inverse of predicted next CPU burst time 

 

• Problem == Starvation – low priority processes may never execute 
• Solution == Aging – as time progresses increase the priority of the process

 

++SJF 알고리즘은 우선순위를 프로세스 실행시간으로 결정했다. 라고 보면 되겠다.

 

우선순위가 될 수 있는 수많은 기준이 있겠지?? 알아보자

 

**우선순위가 같으면 FCFS(선입선처리)로 진행된다.

 

우선순위는 측정 가능한 양이 다 될 수 있다.

 

시간 제한, 메모리 요구, 열린 파일의 수, 평균I/O 버스트의 평균 CPU 버스트에 대한 비율 등 많이 있다.

 

또한 우선순위 스케줄링은 선점. 비선점형 두 가지가 있다.

 

중간에 들어온 프로세스의 우선순위가 지금 실행되고 있는 프로세스의 우선순위보다 높을 수 있다.

 

비선점형이라면 들어온 CPU는 단순히 준비 완료 큐의 머리 부분에 새로운 프로세스를 넣으면 된다.

 

 

**사실 우선순위 스케줄링의 문제는 바로 Indefinite blocking(무한 봉쇄) 그리고 Starvation(기아) 가 있다.

 

실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스는

CPU를 기다리면서 봉쇄된 것으로 간주할 수 있다. 

 

그니까 다시 말하면 우선순위가 낮은 애들이 이제 CPU 이용하려고 하면 중간에 꼭 중간애들이 와서 먼저 먹을게 이러면서 CPU 계속 차지하니까 얘네는 CPU를 점유할 수 없는 상태가 지속된다.

그게 바로 무한 봉쇄.

 

 

 

무한 봉쇄에 대한

 

첫번째 해결책은 aging(노화)가 있다.

오랫동안 숙성되면 우선순위가 높아진다. ㅋㅋㅋㅋ // 폐관 수련ㅋㅋㅋㅋㅋㅋㅋ

 

예를 들면 1초마다 우선순위가 올라가진다거나 그런 식으로 수행한다.

 

두번째 해결책은 RR과 결합하는 것이다.

 

시스템이 우선순위가 가장 높은 프로세스를 실행하고 우선순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용한다.

 

그림을 보자

 

 

 

시간 할당량을 2로 했을 경우

 

P4가 우선순위가 제일 높으므로 수행하고 P2,P3는 RR 방식으로 수행한다.