프로세스 큐(Queue)
•
여러 프로세스를 동시에 실행 시키면 프로세스가 CPU를 점유하려면 순서를 기다려야한다. 이 순서는 몇 가지 Queue에 의해 관리되며 스케줄링을 위한 Queue는 크게 세종류가 있다.
•
Job Queue
프로세스가 시스템에 생성되면 들어가게 되는 큐로, RAM 용량이 한계가 있기 때문에 RAM에 올릴 프로그램들이 대기하는 큐다. 하드 디스크에 있는 프로그램이 실행되기 위해 메인 메모리의 할당 순서를 기다리는 큐이다.
•
Ready Queue
프로세스 상태의 준비 상태 큐로, 프로세스들이 준비 상태에서 실행 상태로 넘어가기 위해 CPU 점유를 기다리는 큐다.
•
Device Queue
I/O 장치를 기다리는 큐로, 여러 I/O 장치마다 큐가 각각 존재한다.
프로세스 작업 특성
•
CPU burst
◦
CPU 버스트는 프로세스가 연산이나 계산을 수행하는 동안 CPU를 활용하는 시간을 의미한다.
◦
CPU 버스트는 프로세스의 CPU 요구량을 나타내며, 일반적으로 CPU 버스트의 길이가 짧으면 CPU 사용시간이 짧고 CPU 버스트가 길면 CPU 사용시간이 길어진다.
•
I/O burst
◦
입출력 버스트는 프로세스가 입출력 작업을 수행하는 동안 대기해야하는 시간을 의미한다.
◦
입출력 버스트는 프로세스가 다른 외부장치나 시스템과 상호작용하는 시간을 나타내며, 프로세스가 입출력 작업을 요청하면 프로세스는 I/O 버스트 상태로 대기한다.
•
프로세스는 CPU를 사용하여 계산을 수행하고 입출력 작업을 요청 후 대기하는 식으로, CPU 버스트와 I/O 버스트를 번갈아가며 수행한다.
•
짧고 많은 CPU 버스트가 존재하는 프로그램을 I/O-bound Job이라 부르고, CPU burst가 길고 적은 프로그램을 CPU-bound Job이라 부른다.
•
버스트들의 길이와 순서는 프로세스의 작업 특성에 따라 달라지는데, 프로세스 스케줄링 알고리즘은 CPU 버스트와 I/O 버스트의 길이를 고려하여 프로세스를 관리하고 CPU와 입출력 장치의 효율적인 사용을 목표로 스케줄링한다.
프로세스 스케줄링
•
프로세스 큐의 내부에는 대기하고 있는 프로세스의 PCB가 저장되어 있다. 이렇게 대기하고 있는 프로세스들의 순서를 정해주는 알고리즘을 스케줄링(Scheduling)이라 한다. 스케줄링에는 장기, 중기, 단기 단위가 있다.
•
장기 스케줄링(Long-term scheduling)
◦
많은 프로세스들이 한번에 메모리에 올라올 경우, 디스크에 임시로 저장하고 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 준비 큐로 보낼지 결정한다.
◦
메모리와 디스크 사이의 스케줄링을 담당한다.
◦
상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행된다.
◦
수행 빈도가 적고 느리다.
◦
Job Queue를 스케줄링하는 것은 발생하는 시간이 비교적 오래걸리는데, 이 때문에 Job Scheduler를 Long-term scheduler라고도 한다.(프로그램이 새로 메모리에 올라오는 일이 자주 발생하지 않음)
◦
전체 시스템의 부하를 고려해 new 상태의 프로세스를 admit하는 작업에 대해 요청을 받을 지 거부할 지를 결정하기 때문에, 장기 스케줄링의 결정에 따라 시스템 내의 프로세스 총 개수(degree of multiprogramming)가 정해진다.
◦
CPU-bound 프로세스와 I/O-bound 프로세스의 균형을 맞추는 역할도 이 스케줄러가 담당한다.
•
중기 스케줄링(Middle-term scheduling)
◦
말 그대로 short-term 보다는 덜 발생하지만, long-term 보다는 자주 발생하는 스케줄링이다.
◦
시스템의 과부하를 막기위해 활성화된 프로세스들의 중지 여부를 결정하여 활성화된 프로세스의 수를 조절한다.
◦
주기적으로 메인 메모리에 있는 전체 프로세스를 검사하여, CPU를 할당 받으려는 프로세스가 많을 때는 프로세스를 보조기억장치로 옮긴다. 이렇게 옮겨진 프로세스들은 보류 상태(지연 상태)가 된다.
◦
Swapping(swap-in/out)을 결정한다(메모리 부족 시 swap-out, 남으면 swap-in). 메인 메모리에서 장시간 사용하지 않은 프로세스를 하드디스크(swap device = Backing storage)로 옮기고, 나중에 해당 프로세스가 다시 사용될 때 하드디스크에서 꺼내어 다시 메인 메모리에 할당해준다.
일반적으로 하드디스크는 File system + swap device(Backing storage)로 구성되어 있다.
•
단기 스케줄링(Short-term scheduling)
◦
대기 큐에 존재하는 프로세스 중 어떤 프로세스를 CPU에 점유시킬 지를 결정한다.(ready → running 상태 전이)
◦
메모리와 CPU 사이의 스케줄링을 담당한다.
◦
프로세서 스케줄링 또는 하위 스케줄링이라고도 한다.
◦
프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행된다.
◦
자주 수행되고 빠르다.
◦
Ready Queue를 스케줄링하는 것은 발생 시간이 매우 짧기 때문에, CPU-scheduler를 Short-term scheduler라고도 한다.(작업이 매우 빈번하게 발생됨)
스케줄링 성능 척도
1.
시스템 입장에서의 성능 척도
•
CPU 이용률(CPU Utilization)
전체 시간 중 CPU가 사용된 시간
•
처리량(Throughput)
단위 시간당 수행 완료된 작업의 수
2.
프로그램(사용자) 입장에서의 성능 척도
•
소요시간(Turnaround Time)
프로세스가 실행되고 준비 큐에서 대기한 시간부터 작업을 완료하는데까지 걸린 시간
•
대기시간(Wating Time)
프로세스가 준비 큐에서 대기한 시간
•
응답 시간(Response Time)
프로세스가 처음으로 CPU를 할당받기까지 걸린 시간
선점형 스케줄링 / 비선점형 스케줄링
•
선점형 스케줄링(preemptive)
◦
하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단 시키고 CPU를 점유하는 스케줄링 방식이다.
◦
비교적 응답이 빠르다는 장점이 있지만, context switching에 의한 오버헤드가 발생하고 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 이어서 들어오는 경우에 오버헤드를 초래한다는 단점이 있다. 또한 여러 프로세스가 데이터를 공유하는 환경에서 경쟁 상태(Race condition)의 문제가 있다.
◦
실시간 응답환경, Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리할 경우에 유용하다.
◦
스케줄링 알고리즘 : Round Robin, MQL, MLFQ
•
비선점형 스케줄링(non-preemptive)
◦
한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식이다.
◦
모든 프로세스에 대해 요청을 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 다른 프로세스의 긴 작업이 끝날 때까지 대기해야하는 상황이 발생할 수 있다(Convey Effect). 또한 전체 시스템 입장에서는 낮은 처리율을 가진다는 단점이 있다.
◦
프로세스 처리시간의 편차가 적은 환경에서 용이하다.
◦
스케줄링 알고리즘 : 우선순위, 기한부, SJF, HRN, FIFO
스케줄링 알고리즘
•
FIFO(First-In-First-Out) 스케줄링
◦
가장 간단한 스케줄링 기법으로, 먼저 대기 큐에 들어온 작업부터 CPU에 할당하는 비선점 스케줄링 방식
◦
중요하지 않은 작업을 처리하느라 중요한 작업이 나중에 처리될 수 있다.
◦
처리시간이 큰 프로세스가 CPU를 먼저 차지하면 전체 시스템 성능이 저하된다(Convey Effect).
◦
대화식 시스템에 부적합하다.
◦
FCFS(First Come First Served)라고 불리기도 한다.
•
SJF(Shortest Job First) 스케줄링
◦
작업 시간이 낮은 프로세스부터 우선해서 CPU에 할당하는 비선점형 스케줄링 방식
◦
운영체제가 프로세스의 소요시간을 맞추기 어렵고, 여러 짧은 소요시간을 가진 프로세스가 많다면 소요시간이 큰 프로세스는 실행되지 않는다는 단점이 있다.(Starving)
•
HRN(Highest Response Ratio Next) 스케줄링
◦
기다린 시간과 CPU 사용시간을 통해 우선순위를 설정하는 비선점형 스케줄링 방식
◦
우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간
◦
SJF의 아사(Starving)현상을 해결하기 위한 기법이지만, 여전히 공평성이 낮아 사용되지 않는다.
•
RR(Round Robin) 스케줄링
◦
모든 프로세스를 일정 시간동안만 CPU를 점유하게 순환하는 선점형 스케줄링 방식
◦
FIFO 스케줄링 기법에 Preemptive(선점형) 기법으로 구현한 스케줄링 방식으로, FIFO 형태로 대기 큐에서 작업을 가져오지만 일정 시간(time slice) 안에 작업을 마치지 못하면 해당 프로세스는 큐의 맨 뒤로 되돌아간다.
◦
시스템이 사용자에게 적합한 응답시간을 제공해주는 대화식 시분할 시스템에 적합하다.
•
SRT(Shortest Remaining Time) 스케줄링
◦
SJF 스케줄링 방식과 RR 스케줄링 방식을 조합한 형식의 선점형 스케줄링 방식
◦
여전히 운영 체제가 프로세스의 작업 소요시간을 계산하기 어렵다는 단점과 아사 가능성이 존재한다.
◦
새로 도착한 프로세스를 비롯하여 대기 큐에 남아있는 프로세스의 작업이 완료되기까지 남아있는 소요시간 추정치가 가장 적은 프로세스가 CPU에 먼저 할당된다.
•
MLQ(Multi-Level Queue) 스케줄링
◦
우선순위에 따라 여러 개의 큐를 두고 높은 우선순위의 큐부터 순서대로 실행하는 선점형 스케줄링 방식
◦
다단계 스케줄링이라 불린다.
•
MLFQ(Multi-Level Feedback Queue) 스케줄링
◦
MLQ 방식에서 CPU를 점유한 이후에는 우선순위를 하나 낮추어 큐에 저장하는 식으로 낮은 우선순위 큐의 불리함을 보완한 선점형 스케줄링 방식
◦
우선순위가 낮은 큐의 작업 중 너무 대기 시간이 너무 길어지면 우선순위를 높이는 Aging 기법을 적용하여 Starving을 보완할 수 있다.
◦
다단계 피드백 큐 스케줄링이라 불린다.
•
우선순위(Priority) 스케줄링
◦
각 작업마다 우선순위가 주어지고, 해당 우선순위가 가장 높은 작업부터 CPU에 할당되는 비선점형 스케줄링 방식
◦
우선순위가 낮은 작업은 Indefinite Blocking이나 Starving에 빠질 수 있고, 이에 대한 해결책으로 체류 시간이 길어질수록 우선순위가 높아지는 Aging 기법이 있다.
•
기한부(Deadline) 스케줄링
◦
작업이 주어진 시간제한이나 Deadline 시간 안에 완료되도록 하는 비선점형 스케줄링 방식