해당 게시글은 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가지 상태 변경
- Switchs from running to wating state
- Switchs from running to ready state
- Switches from wating to ready
- Terminates
- 1, 4번 째 경우를 nonpreemptive(자발적으로 나가는)이라고 한다.
- 나머지 경우를 preemptive(나가게 되어지는)이라고 한다.
- 스케줄러가 동작하는 이유는
- cpu의 유휴 시간을 줄이고,
- 시분할 시스템을 적용하고,
- 더 중요한 프로세스를 먼저 수행하기 위해서 이다.
Dispatcher
- Dispatcher는 아래 내용을 수행한다.
- context switching(PCB 저장)
- user mode로 변경
- 다음 유저 프로그램 재시작
- 스케줄링이 발생할 때마다 dispatching이 되기 때문에 Dispatch latency라고 한다.
Scheduling Criteria
- cpu 스케줄링 기법을 판단할 때 숫자로 된 판단 척도를 쓰는데 이 것을 criteria 라고 한다.
- 5가지 criteria를 가지고 판단한다.
- CPU utilization
- 단위 시간동안 얼마만큼 cpu를 사용했는지 판단
- 짧은 시간동안 측정하면 편협한 결과를 얻을 수 있기 때문에 충분히 긴 시간동안 측정하게 된다.
- 사용시간이 길수록 좋다고 판단한다.
- Throughput
- 단위 시간동안 몇 개의 프로세스가 수행되고 종료 되었는지 판단
- 이 역시 마찬가지로 충분한 시간을 두고 측정한다.
- 많은 프로세스를 사용하고 종료해야 좋다고 판단한다.
- Turnaround time
- 어떤 프로세스가 수행을 시작하고 끝나는 시간을 판단
- 수백 개의 프로세스를 측정하고 평균 turnaround 시간을 측정하게 된다.
- 알고리즘 평가의 중요한 요소이다.
- Waiting time
- 프로세스가 기다리는 시간
- Turnaround time = Waiting time + 수행 시간
- 결국 waiting time이 tunrnaround time을 결정하게 되는 요소이다.
- 이 것이 짧으면 짧을 수록 성능이 좋아진다.
- 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
- Throughput
- 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라고 한다.
- 우선 순위가 낮은 큐에서 높은 쪽으로 피드백 하거나, 높은 쪽에서 낮은 쪽으로 피드백할 수 있다.
- 현재 대부분의 시스템이 해당 큐를 사용한다.
- 멀티레벨 피드백 큐를 설계하기 위해 아래 내용들을 고려해야 한다.
- 큐의 개수
- 각 큐 마다 사용할 알고리즘
- 아래 쪽 큐에서 위 쪽 큐로 올리기 위한 기준
- 위 쪽 큐에서 아래 쪽 큐로 내리기 위한 기준
- 프로세스가 어떤 큐에 들어갈지 결정하기 위한 기준