http://www.kocw.net/home/search/kemView.do?kemId=978503
운영체제
운영체제의 정의 및 역할 등에 대해 알아보고, 운영체제의 주요 요소들, 즉 프로세스 관리, 주기억장치 관리, 파일 시스템 등에 대해 공부한다.
www.kocw.net
CPU Scheduling(OS의 Process management에서 하는 일임)
CPU Scheduling이란 Ready queue에서 CPU의 처리를 기다리는 프로세스들을 일정한 규칙에 맞게 처리하는 것을 뜻한다. 예를 들어, 먼저 온 프로세스를 먼저 처리할 수도 있고, 제일 짧게 걸릴 것 같은 프로세스를 제일 먼저 처리할 수도 있을 것이다. 이와 같은 scheduling 방법을 CPU scheduling algorithm이라 하며 여기에는 앞서 언급한 제일 먼저 들어온 것을 먼저 처리하는 First-Come, First-Served(FCFS), 제일 짧은 작업을 먼저 처리하는 Shortest-Job-First(SJF)이 있고, 그 외에 Priority, Round-Robin(RR), Multilevel Queue, Multilevel Feedback queue 등이 있다. CPU scheduling algorithm은 크게 선점 방식과 비선점 방식으로 나뉘며 성능은 CPU Utilization(CPU 이용률), Throughput(처리율), Turnaround time(반환시간), Waiting time(대기시간), Response time(응답시간) 등으로 판단한다.
preemptive vs non-preemptive
- 선점(preemptive)은 CPU에서 어떤 작업이 일어나는 도중 다른 작업이 그 자리를 뺐는 것 다시 말해, 기존에 있던 작업을 쫓아내고 다른 작업이 들어가는 것을 선점이라 말하고 비선점은 그 반대로 기존에 있던 작업을 쫓아내지 않고 기존 작업이 끝날 때까지 기다리는 방식을 의미한다.
CPU utilization
- CPU가 얼마나 놀지 않고 부지런히 일하는 가를 말하는 단어이다. 예를 들어, A scheduling을 이용하면 CPU가 80% 일하고 20%는 쉬는데 B scheduling을 이용하면 CPU가 100% 일한다 가정하면 B가 CPU utilization이 더 좋은 스케줄링 방식인 것이다.
Throughput
- 시간당 몇 개의 작업을 처리하는가(끝내는가)를 뜻하는 단어이다. A scheduling은 1초에 3개를 처리하고 B scheduling은 1초에 10개를 처리한다면 B scheduling의 Throughput이 더 좋은 것이다.
Waiting time
- Ready queue(CPU 작업을 할당받기 전 기다리는 장소)에서 기다리는 시간을 뜻한다.
Response time
- interactive 방식의 OS에서 중요한 것으로, 우리가 어떤 input을 주었을 때부터 응답이 나오는 시간까지의 시간을 뜻한다. 응답의 전체가 다 나올 때의 시간이 아니라 첫 응답이 나오는 그 순간까지의 시간을 뜻하는 것이다.
First-Come, First-Served
먼저 온 것을 먼저 서비스하는 알고리즘이다. 제일 간단하고 공평한 방법이다. 아래 예시를 보며 배워보자.
도착 순서 순으로 p1 = 24 msec, p2 = 3 msec, p3= 3 sec이 걸리는 작업일 때 FCFS를 사용하여 이들의 평균 대기시간을 구해보자. p1은 바로 실행되고 p2는 p1이 끝난 다음 실행 되므로 24 msec을 기다리고 p3는 p1과 p2가 끝나야 실행되므로 27 msec을 기다린다. 따라서 AWT(average waiting time)는 (0+24+27)/3 = 17 msec이다. 이번엔 반대로 나중에 도작한 순서대로 작업을 처리했을 때의 AWT를 구해보자. p3는 바로 실행되고, p2는 p3이 끝난 다음 실행 되므로 3 msec을 기다리고 p1은 p3와 p2가 끝난 다음 실행되므로 6 msec을 기다린다. 따라서 AWT = (0+3+6)/3 = 3 msec이다. 이처럼 FCFS는 AWT로 따져보았을 때 비효율적인 결과를 보일 수도 있다. CPU 실행시간을 많이 필요로 하는 작업이 앞에 있으면 나머지 작업들은 queue에서 오랫동안 기다려야 하는 단점이 있다. 이것을 호위 효과(Convoy Effect)라 한다. FCFS는 앞의 작업이 끝날 때까지 기다려야 하므로 non-preemptive에 속한다.
Shortest-Job-First
실행시간이 가장 짧은 것 먼저 실행하는 알고리즘이다. 평균 대시 시간(AWT)을 줄이는 가장 좋은 방법이다. 다만 비현실적이다. 어떤 프로세스가 CPU 시간을 얼마나 사용할지는 해봐야 하는 것이다. 사용자가 게임을 할 때 몇 분을 할지는 아무도 모르는 것과 동일하다. 프로세스는 time expired 되거나 I/O를 만나면 다시 ready queue로 돌아가거나 I/O 작업이 끝난 뒤 ready queue로 돌아가는데, 다시 ready queue에 적재되었을 때 이전 작업에서의 CPU 사용 시간을 계산하여 그것을 토대로 SJF를 할 수도 있지만, 그렇지 않아도 overhead가 큰 context switching인데 이런 작업까지 해야 한다면 overhead가 더 커지기 때문에 실질적으로는 생각만큼 효율적이지 않다. preemptive로 구현할 수도 있고 non-preemptive로 구현할 수도 있다. 사용 예시는 아래를 보며 배워보자.
p1 = 6 msec, p2 = 8 msec, p3 = 7 msec, p4 = 3 msec이 걸리는 작업이 있을 때, SJF를 사용하여 이들의 평균 대기 시간을 구해보자. 실행 시간이 제일 짧은 순으로 실행되므로 p4-p1-p3-p2 순으로 실행될 것이다. 따라서 AWT = (0+3+9+16)/4 = 7 msec이다. 비교를 위해 FCFS로도 AWT를 구해보자. FCFS는 도착 순으로 실행하므로 p1-p2-p3-p4 순으로 실행된다. 따라서 AWT = (0+6+14+21)/4 = 10.25 msec이다. 해당 예시의 경우 FCFS보다 SJF를 사용했을 때 AWT가 더 짧게 나온다.
이번에는 도착 시간이 각각 다른 예시에서 preemptive SJF와 non-preemptive SJF를 비교해 보자. Px(CPU 요구 시간, 도착 시간)이다. p1 = (8, 0), p2 = (4, 1), p3 = (9, 2), p4 = (5, 3)의 non-preemptive SJF의 AWT는 다음과 같다. p1이 0초에 도착하므로 p1을 실행.(p1만 있었으니까 실행할 수 있는 게 p1 밖에 없음) p1 실행 중 p2, p3, p4가 ready queue에 들어옴. p2, p3, p4 중 소요 시간이 제일 짧은 순(p2-p4-p3)으로 실행하면 AWT = (0+7+9+15)/4 = 7.75 msec이다. preemptive SJF로 실행한 AWT는 다음과 같다. 0초에 p1만 있으니 p1 실행 1 msec 뒤에 p2가 도착하는데 p2는 CPU 요구 시간이 4 msec이고 p1은 7 msec(1 msec8-1)이므로 p2가 더 짧으니까 p2실행. p3와 p4가 각각 p2 실행 1 msec, 2 msec 뒤 도착하지만 p2가 CPU 요구 시간이 제일 짧으므로 계속 p2 실행. p2가 실행이 끝나면 나머지 중 제일 CPU 요구 시간이 짧은 순으로 p4-p1-p3 실행. 따라서 AWT = (9+0+15+2) / 4 = 6.5 msec이다. non-preemptive SJF보다 preemptive SJF의 AWT가 더 짧다. 참고로 preemptive SJF는 남아있는 CPU 요구 시간을 기준으로 우선순위를 정하므로 Shortest-Remaining-Time-First(최소 잔여 시간 우선)이라고도 한다.
Priority scheduling
priority scheduling은 말 그대로 우선순위를 정해서 그것을 기준으로 실행을 하는 것이다. priority는 보통 정수 값으로 표현한다. 낮은 숫자가 더 높은 우선순위를 나타내며 priority는 내부적 요인(time limit, memory requirement, I/O to CPU burst, ...)과 외부적 요인(돈 많이 낸 사람 우선으로 작업, 그 외 정책적인 사항)을 기준으로 정한다. priority scheduling은 SJF와 마찬가지로 preemptive 방식 혹은 non-preemptive 방식으로 구현할 수 있다. 문제점으로는 indefinite blocking(=startvation, 굶주림, 기아 상태)이 있는데 우선순위가 낮으면 무한히 기다리기만 하고 CPU 할당을 못 받을 수도 있다는 것이다. 이 문제는 ready queue에 오래 머문 프로세스의 우선순위를 높여주는 aging 기법을 통해 방지할 수 있다.
Round-Robin
CPU의 전체 사용 시간을 작고 동일한 시간으로 나누어 번갈아가며 그 시간을 사용하는 Time-sharing system이다. 조그만 시간 토막을 time quantum 혹은 time slice라고 하며 preemptive scheduling 방식이다.
time quantum이 무한이면 사실상 FCFS와 같은 방식이며 time quantum이 작을수록 context switching overhead가 부담이 되므로 Round-Robin 방식의 성능은 적당한 time quantum 사이즈 설정에 달려있다.
예를 들어, p1 = 6 msec, p2 = 3 msec, p3 = 1 msec, p4 = 7 msec이 걸릴 때, time quantum이 1 msec인 경우 ATT(Average Turnaround Time)은 p1이 15 msec 뒤에 완료되고 p2, p3, p4는 각각 9 msec, 3 msec, 17 msec 뒤에 완료되므로 (15+9+3+17) / 4 = 11 msec이 소요되지만 time quantum이 5 msec인 경우 p1, p2, p3, p4의 turnaround time은 각각 15 msec, 8 msec, 9 msec, 17 msec이므로 (15+8+9+17) / 4 = 12.25 msec이 걸린다.
Multilevel Queue Scheduling
CPU로 가기 위해 대기하는 ready queue를 여러 가지로 나누고 각각의 queue에 수선순위를 주어 CPU scheduling을 하는 방식이다. 각 queue는 독립된 scheduling 정책을 가질 수 있으며 Process group은 System processes, Interactive processes, Interactive editing processes, Batch processes Student processes 등등 여러 가지로 나눌 수 있다. 큐 안에 있는 작업들의 중요도가 모두 다르므로, 이 작업들을 각자의 특성(성격)에 따라 분리하고 그렇게 분류된 것들을 각각 하나의 큐로 만들면 스케줄링하기가 더 편해지지 않을까 하는 생각에서부터 출발한 스케줄링 방식이다.
Multilevel Feedback Queue Scheduling
복수 개의 queue가 존재하며 다른 queue로의 점진적 이동이 가능하다. 모든 프로세스는 하나의 입구로 진입하고 너무 많은 CPU time 사용 시 다른 queue로 이동시키는 방식이다. 기아 상태 우려 시 우선순위가 높은 queue로 이동시킬 수도 있다. 어떠한 process가 기아 상태가 지속되거나 CPU time을 너무 많이 잡아먹으면 해당 queue의 scheduling 방식과 해당 process가 서로 잘 맞지 않는 것일 수 있다. 그렇다면 해당 process를 다른 scheduling 방식을 채택한 queue로 보내면 문제가 해결될 수도 있지 않을까 하는 아이디어로부터 출발한 스케줄링 방식이다. 아래 그림에서는 밑으로 내려가는 것만 그렸지만 보통 위로 올라갈 수도 있다.
** 상용 OS는 작업의 특성에 맞게 스케줄링 방식을 적용하기 때문에 FCFS, SJF, Round-Robin, Priority 등등 많은 스케줄링 방식을 사용한다. 따라서 MQS 혹은 MFQS 스케줄링 방식을 채택한다.