CPU 스케줄링

sun202x·2023년 1월 22일

CPU scheduling OS

운영체제

목록 보기

17/23

해당 게시글은 kocw에서 제공하는 금오공과대학교 최태영 교수님의 무료 강의를 공부하고 정리하기 위해서 만들어졌습니다.

CPU Scheduling

멀티 프로그래밍을 하는 동기를 다시 짚어보자면,
어떤 프로그램이 돌아갈 때, 아래와 같은 사이클을 가진다.
- cpu Burst: cpu, 메모리를 사용하는 구간
- read operation: read operation이 수행되면 이 것이 종료 될 때까지 블락이 된다.
- I/O를 처리하기 때문이다.
이 것 때문에 멀티 프로그래밍 개념이 나오게 된 것이다.
cpu 사용량을 측정하게 되면,
한 프로세스당 2ms 정도 cpu를 사용하게 되고, 10ms 정도 cpu를 사용하지 않게 된다.
- 즉, I/O를 처리하는 시간이 10ms라는 말이다.
그렇기 때문에 cpu를 계속 일하게 하려면, 6개의 프로세스는 있어야 cpu를 최대한으로 돌릴 수 있게 된다.
- degre of multiprogramming: 6
그렇다는 말은 메모리에 6개의 프로세스가 올라와 있고,
1개의 프로세스가 실행되는 동안 5개의 프로세스는 대기하게 된다.
이 때, 실행중인 프로세스가 I/O를 사용하려 나가고 다음 프로세스를 선택하는 것을 스케줄링 정책(Scheduling Policy)이라고 한다.
이 스케줄링 정책 중 어느 것을 선택 하냐에 따라 시스템의 성능이 많이 바뀌게 된다.
CPU 스케줄링이 발생하는 프로세스의 4가지 상태 변경
- 1. Switchs from running to wating state
  - 실행중에서 대기 상태로 변경되는 경우
- 1. Switchs from running to ready state
  - 실행중에서 준비 상태로 변경되는 경우
- 1. Switches from wating to ready
  - 대기중에서 준비 상태로 변경되는 경우
- 1. Terminates
  - 종료 되는 경우
1, 4번 째 경우를 nonpreemptive(자발적으로 나가는)이라고 한다.
나머지 경우를 preemptive(나가게 되어지는)이라고 한다.
스케줄러가 동작하는 이유는
- cpu의 유휴 시간을 줄이고,
- 시분할 시스템을 적용하고,
- 더 중요한 프로세스를 먼저 수행하기 위해서 이다.

Dispatcher

Dispatcher는 아래 내용을 수행한다.
- context switching(PCB 저장)
- user mode로 변경
- 다음 유저 프로그램 재시작
스케줄링이 발생할 때마다 dispatching이 되기 때문에 Dispatch latency라고 한다.

Scheduling Criteria

cpu 스케줄링 기법을 판단할 때 숫자로 된 판단 척도를 쓰는데 이 것을 criteria 라고 한다.
5가지 criteria를 가지고 판단한다.
- 1. CPU utilization
  - 단위 시간동안 얼마만큼 cpu를 사용했는지 판단
  - 짧은 시간동안 측정하면 편협한 결과를 얻을 수 있기 때문에 충분히 긴 시간동안 측정하게 된다.
  - 사용시간이 길수록 좋다고 판단한다.
- 1. Throughput
  - 단위 시간동안 몇 개의 프로세스가 수행되고 종료 되었는지 판단
  - 이 역시 마찬가지로 충분한 시간을 두고 측정한다.
  - 많은 프로세스를 사용하고 종료해야 좋다고 판단한다.
- 1. Turnaround time
  - 어떤 프로세스가 수행을 시작하고 끝나는 시간을 판단
  - 수백 개의 프로세스를 측정하고 평균 turnaround 시간을 측정하게 된다.
  - 알고리즘 평가의 중요한 요소이다.
- 1. Waiting time
  - 프로세스가 기다리는 시간
  - Turnaround time = Waiting time + 수행 시간
  - 결국 waiting time이 tunrnaround time을 결정하게 되는 요소이다.
  - 이 것이 짧으면 짧을 수록 성능이 좋아진다.
- 1. Response time
  - 컴퓨터 사용자의 동작에 의해서 컴퓨터가 결과를 내기 까지의 시간
  - 최소한 인터럽트 루틴이 수행되는 시간이 포함되고, 심지어 몇 초 씩 걸리기도 한다.
  - 이 것도 짧으면 짧을수록 성능이 좋다.
1, 2번은 어떤 스케줄링 알고리즘이라도 성능과 관계없이 좋은 결과를 낼 수 있기 때문에 스케줄링 알고리즘 비교에서는 제외하도록 한다.

First-Come, First-Served(FCFS) Scheduling

스케줄링을 이야기 할 때, 항상 ready queue를 같이 말하게 되는데,
- ready queue는 준비중인 프로세스를 모아두는 큐이다.
FCFS는 말 그대로 먼저 들어온 프로세스가 먼저 처리 되는 스케줄링 알고리즘이다.
프로세스의 수행이 O(1)만에 수행 되므로 상당히 간단한 알고리즘 이라고 할 수 있다.
시간이 0인 시점에 동시에 세 개의 프로세스가 들어왔다고 했을 때,
- Process: P1, Burst Time: 24
- Process: P2, Burst Time: 3
- Process: P3, Burst Time: 3
- Process는 PID이고, Burst Time은 cpu 사용 시간이다.
차례대로 P1, P2, P3가 수행이 되고, 이것의 Criteria를 계산해 보면
- CPU utilization
  - 100%
- Throughput
  - 30/3 = 0.1
- Waiting time
  - (0(P1) + 24(P2) + 27(P3))/3 = 17
  - 이 때, 들어온 순서를 P3, P2, P1이라고 하면,
    - (0 + 3 + 6)/3 = 3
    - 효율이 달라지는 것을 알 수 있다.
Convoy Effect
- 수행시간이 느린 프로세스를 먼저 수행하느라 기다리는 시간이 길어지는 것

Shortest-Job-First(SJF) Scheduling

수행 시간이 짧은 프로세스를 먼저 수행하는 알고리즘이다.
짧은 시간을 먼저 수행하기 때문에 waiting time이 가장 짧게 나오는 알고리즘이다.
아래 4 개의 프로세스가 들어왔을 때,
- Process: P1, Burst Time: 6
- Process: P2, Burst Time: 8
- Process: P3, Burst Time: 7
- Process: P4, Burst Time: 3
waiting time을 구해보면,
- (0(P4) + 3(P1) + 9(P3) + 16(P2)/4 = 7

Determining Length of Next CPU Burst

SJF 알고리즘의 문제는 프로세스의 수행시간을 알아야 한다는 문제점이 있다.
- 코드가 수행되는 것을 그때그때 알아내야 한다.
그렇게 하기 위해 이전에 수행했던 결과를 가지고 근사치를 내어 계산하게 된다.
- 다음차례 예측시간 = (수행시간가중치) + (예측시간(1-가중치))
- 가중치는 0~1 사이의 적절한 값이다.
- 위와 같은 형태의 수식이 나오게 된다.

Shortest-remaining-time-first

현실적으로 스케줄러가 수행될 때, 프로세스들이 동시에 도착하기 보다 시간을 두고 각각 준비 상태로 들어오게 된다.
이 때, 수행되고 있는 프로세스의 남은 수행시간과 새로 들어온 프로세스의 수행시간을 비교하여 더 작은 수행시간을 가진 프로세스를 먼저 수행시킨다.
아래 4 개의 프로세스가 각각 들어온다고 할 때,
- Process: P1
  - Arrival Time: 0
  - Burst Time: 8
- Process: P2
  - Arrival Time: 1
  - Burst Time: 4
- Process: P3
  - Arrival Time: 2
  - Burst Time: 9
- Process: P4
  - Arrival Time: 3
  - Burst Time: 5
waiting time을 구해보자.
- (0(P1) + 0(P2) + 2(P4) + 9(P1) + 15(P3))/4 = 26/4 = 6.5
- 중요한 것은 들어온 시간에 따라 수행되는 프로세스가 변경되기 때문에
- 들어온 시간을 계산해서 기다리는 시간을 계산해야 한다는 것이다.
- P2같은 경우 수행시간이 짧기 때문에 바로 수행되어 0의 대기시간을 가지는 것을 알 수 있다.

Priority Scheduling

FCFS 보다 자주 쓰이는 스케줄링 기법이다.
프로세스마다 우선순위가 주어지며 이 우선순위를 바탕으로 실행순위를 결정한다.
PCB에 이 priority가 들어있고, 시스템마다 숫자 값에 따라 우선순위가 달라진다.
- priority가 낮을수록 높은 우선순위를 가지는 시스템: linux
- priority가 높을수록 높은 우선순위를 가지는 시스템: solaris
동작 방식
- 큐에 들어온 프로세스의 우선순위를 확인한다.
- 우선순위가 같을 경우 먼저 들어온 프로세스가 우선권을 갖는다.
- 우선 순위가 높은 프로세스를 우선적으로 실행한다.
- 만약 현재 실행중인 프로세스보다 우선순위가 더 높은 프로세스가 들어올 경우,
- 현재 실행중인 프로세스를 중단하고 더 높은 우선순위가 높은 프로세스를 우선적으로 실행한다.
이러한 동작 방식 때문에 Starvation Problem이 발생한다.
- 낮은 우선순위의 프로세스가 절대 실행되지 않는 문제
- 우선순위가 높은 프로세스가 계속해서 들어올 경우 발생한다.
- 해결 방법은 오래된 프로세스들의 우선순위를 높여주면 된다.(Aging)
- 다만 Aging을 해주면 cpu의 오버헤드가 증가한다는 점이 발생한다.
내부 ready queue로 사용하는 자료구조는 heap(priority queue)이다.

Round Robin(RR)

많이 사용 되는 또 다른 스케줄링 기법으로, 모빌처럼 프로세스 들이 빙글빙글 돌면서 cpu를 나눠쓰는 스케줄링 기법이다.
PCB내에 존재하는 time quantum(cpu를 사용하기 위한 시간 값)을 가지고 스케줄링을 수행한다.
- 주로 time quantumd은 넉넉하게 10~100ms 정도 주어진다.
먼저 도착한 프로세스가 수행되고 time quantum에 따라 시간이 지나갈 경우 현재 수행중인 프로세스를 제거(preemption)하고, 다음 프로세스를 실행한다.
이때 제거된 프로세스는 ready queue에 가장 뒤 쪽으로 들어가게 된다.
RR을 사용하는 이유는 아래와 같다.
- 시분할 시스템(Time sharing)을 사용하기 위해
- maximum response time을 보장하기 위해
  - MRT에 영향을 주는 요소는 프로세스 개수, Time Quantum 이다.
현재 실행중인 프로세스의 time quantum이 지났는지 확인하기 위해 time interrupt를 사용하게 된다.
따라서 프로세스는 time quantum을 정확하게 지키는게 아니라 반복적으로 수행되는 time interrupt가 호출 되어야 프로세스를 제거하게 된다.
RR의 장점은 time quantum을 크게 늘려주면 FCFS와 같이 사용할 수 있으므로 유동적으로 스케줄링 방식을 결정할 수 있다는 점이다.
반대로 time quantum 값을 적게 주면 maximum response time이 줄어드므로 응답성이 좋아진다는 점이있다.
- 문제는 프로세스가 변경될 때마다 dispatch latency가 발생한다.
- 이것도 계속 누적되면 성능저하의 원인이 될 수 있다.
아래 3개의 프로세스가 들어오고 Time Quantum이 4일 때,
- Process: P1, Burst Time: 24
- Process: P2, Burst Time: 3
- Process: P3, Burst Time: 3
우선적으로 P1이 수행되고 time quantum이 지나면 쫓겨나진다.
그 후 P2가 수행되고 무사히 종료된다.
그 다음 P3가 수행되고 마찬가지로 종료된다.
이후 P1이 time quantum만큼 수행되고 제거 되는 것을 반복하게 된다.
- 마지막 남은 프로세스가 하나이더라도 타이머 인터럽트는 주어진 시간이 지나면 반복해서 쫓아낸다.
- 이렇게 반복하면서 수행되는 것이 dispatch latency이다.
총 30.001 ms 정도 시간이 소요된다.

Time Quantum과 Context switch time

TQ를 크게 준다면 maximum response time이 커지겠지만, dispatch latency가 발생하는 횟수가 줄어든다.
반대로 TQ를 적게 준다면 maximum response time이 줄어들고 dispatch latency 횟수가 늘어난다.
- context switching overhead가 늘어난다.
시스템의 목적에 따라 스케줄링을 선택해야 한다.
- 일반적인 시스템일 경우 프로세스 수행기간이 짧기 때문에, dispatch latency가 많이 발생하지 않지만,
- 과학 데이터 계산 시스템 같은 경우 프로세스의 수행시간이 길기 때문에, dispatch latency가 자주 발생하여 overhead가 늘어난다.
- 그렇기 때문에 대부분의 과학 시스템 같은 경우 FCFS를 사용하거나 time quantum이 매우 긴 RR을 사용한다.

운영체제의 스케줄링 방법

FCFS부터 RR 까지가 현재 쓰이는 스케줄링 기법이다.
기본적으로 운영체제에서는 RR과 Priority Scheduling을 조합한 방식을 가장 많이 사용한다.

Multilevel Queue

프로세스는 최소 두가지의 성향으로 분류된다.
- foreground(interactive)
  - 이런 프로세스의 특징은 cpu를 조금만 사용하고 I/O를 수행하러 간다.
- background(batch)
  - 이런 프로세스의 특징은 다른건 안하고 계산만 계속 수행한다.
이런 두가지 성향으로 나눠지는 프로세스 들을 처리하기 위해 ready queue를 두 개로 나눠서 처리한다.
- 이 것을 Multilevel queue라고 한다.
foreground 프로세스 들을 담은 큐는 RR로 동작하게 하고,
background 프로세스 들을 담은 큐는 FCFS로 동작시킨다.
- context switching overhead가 줄어든다.
cpu가 비게 되면, foreground 프로세스가 우선적으로 수행된다.
- 사용자에게 반응이 좋게 제공하기 위해서이다.
foregound 프로세스가 계속 수행되게 되면 background 프로세스가 수행되지 않으므로 마찬가지로 Starvation Problem이 발생한다.
- 이 것을 해결하기 위해 time slice를 두고 적당한 비율로 foreground, background 프로세스를 수행한다.
멀티레벨 큐는 아래와 같이 구성되며 위에 있을 수록 우선순위가 높은 큐이다.
- system processes
  - demon processes
  - kernel processes
- interactive processes
  - 게임, 동영상
- interactive editing processes
  - 문서 에디터
- batch processes
- student processes

Multilevel Feedback Queue

우선순위가 낮은 큐가 기아현상이 발생하지 않으려면 Aging 처리를 해주어야 한다.
이런 식으로 한쪽 큐에서 다른 쪽 큐로 이동할 수 있는 큐를 Multilevel Feedback Queue라고 한다.
우선 순위가 낮은 큐에서 높은 쪽으로 피드백 하거나, 높은 쪽에서 낮은 쪽으로 피드백할 수 있다.
현재 대부분의 시스템이 해당 큐를 사용한다.
멀티레벨 피드백 큐를 설계하기 위해 아래 내용들을 고려해야 한다.
- 큐의 개수
- 각 큐 마다 사용할 알고리즘
- 아래 쪽 큐에서 위 쪽 큐로 올리기 위한 기준
- 위 쪽 큐에서 아래 쪽 큐로 내리기 위한 기준
- 프로세스가 어떤 큐에 들어갈지 결정하기 위한 기준