본론으로 들어가기에 앞서
프로세스 스케줄링은 다중 프로그래밍과 시분할과 연관된다.
다중 프로그래밍 시스템
- 어떤 프로세스를 수행하다 입출력이 발생하면 해당 입출력이 처리되는 동안 CPU가 다른 프로세스를 수행하는 방식이다.
- 여러 프로세스 중 어떤 프로세스을 선택할지는 '스케줄링'을 통해 해결한다. 이는 적절한 정책을 통해 다음 프로세스를 결정해준다.
- 이러한 과정은 각 프로세스가 입출력이 발생할 때만 발생된다. 즉, 다른 프로세스로 작업이 이동되려면 하나의 프로세스가 입출력이 발생해야 한다.
다중 프로그래밍의 목적은 CPU 이용을 최대화하기 위하여 어떤 프로세스가 항상 실행 중이도록 하는데 있다.
시분할 시스템
- 시분할 시스템의 핵심은 '타임슬라이스'이다. 입출력 발생시에도 스케쥴링이 일어나지만 타임슬라이스에서 무조건 스케쥴링을 진행하는 것이다. 이에 따라 한 프로그램에서 입출력 완료 후 대기 시간이 적어졌다. 그에 따라 대화가 빈번한 프로그램도 자연스럽게 수행될 수 있게 되었다.
- 이러한 '타임슬라이스'는 타이머 인터럽트를 통해 구현된다. 보통 10ms의 인터벌로 타이머 인터럽트를 설정해 구현된다.
시분할 시스템의 목적은 각 프로그램이 실행되는 동안 사용자가 상호작용 할 수 있도록 프로세스들 사이에서 CPU를 빈번하게 교체하는 것이다. (CPU를 아주 빨리 교체해서 병렬로 실행되는 것처럼 보인다.)
-목차-
1. 스케줄러
스케줄링은 Queue에 의해 수행된다.
실행될 프로세스가 여러 개 있으면 하나만 실행되고 나머지는 CPU가 자유로워질 때까지 대기하는 것으로 선입선출의 방식을 따른다.
프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재한다.
- Job Queue : 메모리 할당을 대기 중인 프로세스들로 구성된다.
- Ready Queue : 현재 메모리 내에 있으면서 CPU 할당을 대기 중인 프로레스들로 구성된다.
- Device Queue : 입출력 장치 할당을 대기 중인 프로세스들로 구성된다.
프로세스가 시스템에 들어가면 이들은 Job Queue에 넣어진다. Job Queue는 시스템에서 모든 프로세스들이 존재하는 곳이다. 메인 메모리에 거주하는 프로세스들은 Ready Queue라고 불리우는 리스트에서 실행되기를 기다리고 대기한다.
큐는 보통 링크드 리스트로 저장된다. 레디 헤더는 포인터를 포함하는데, 이 포인터는 리스트에서 PCB의 처음과 끝을 가리킨다. 각 PCB는 포인터 필드를 포함하고 있는데, 이는 레디 큐에 있는 다음 PCB를 가리킨다.
프로세스 스케줄링의 공통적인 표현 방식은 아래 그림 2와 같은 queueing diagram이다. 원은 queue를 서비스하는 자원이며, 화살표는 시스템에서 프로세스들의 흐름을 표현한다.
새로운 프로세스는 처음에 ready queue에 놓인다. 프로세스는 CPU를 할당받을 때(dispatch)까지 ready queue에서 대기한다. 프로세스에 CPU가 할당되어 실행되면 아래 사건들 중 하나가 발생할 수 있다.
- 프로세스가 I/O(입출력)을 요청하여 I/O Queue(device queue)
- 할당된 시간 간격이 초과되어 프로세스가 코어에서 강제로 제거되어 준비 큐로 돌아갈 수 있다.
- 프로세스가 자식 프로세스를 생성하고 그 프로세스의 종료를 기다릴 수 있다.
- 프로세스가 interrupt의 결과에 따라 강제로 CPU로부터 제거되어 ready queue에 다시 놓일 수 있다.
프로세스는 결국 waiting state에서 ready state로 전환되고 다시 ready queue에 넣어진다. 프로세스는 종료될 때까지 이 주기를 계속하며, 종료되면 모든 queue에서 삭제되고 프로세스의 PCB와 자원을 반납(deallocate)한다.
각각의 Queue 에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다.
1.1 장기 스케줄러(Long-term scheduler or job scheduler)
메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정하는 역할을 한다.
- 메모리와 디스크 사이의 스케줄링을 담당.
- 프로세스에 memory(및 각종 리소스)를 할당(admit)
- degree of Multiprogramming 제어
(실행중인 프로세스의 수 제어) - 프로세스의 상태
new -> ready(in memory)
1.2 단기 스케줄러(Short-term scheduler or CPU scheduler)
- CPU 와 메모리 사이의 스케줄링을 담당.
- Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
- 프로세스에 CPU 를 할당(scheduler dispatch)
- 프로세스의 상태
ready -> running -> waiting -> ready
이 두 scheduler 사이의 주요한 차이점은 실행 빈도다. short-term scheduler는 CPU의 최대 효율을 위해 빈번하게(frequently) 프로세스를 선택해야만 한다. 프로세스는 I/O request까지 겨우 수 밀리초 동안만 실행될 수도 있다. 이렇게 실행 간격이 짧기 때문에 short-term scheduler는 반드시 매우 빨라야 한다. 빈번하게 실행되는데 느리다면 scheduling 하는데 너무 많은 CPU를 낭비하게 된다.
반면에 long-term scheduler는 훨씬 덜 빈번하게(infrequently) 실행된다. long-term scheduler는 다중 프로그래밍의 수준(메모리에 있는 프로세스의 수)을 제어한다. 다중 프로그래밍의 수준이 안정적이면 프로세스 생성률이 이탈률과 반드시 같아야한다. 실행 간격이 기므로 short-term scheduler보다는 많은 시간을 소비해도 된다.
long-term scheduler는 신중한 선택을 하는 것이 중요하다. 대부분의 프로세스들은 I/O bound 또는 CPU bound로 묘사된다.
I/O bound process는 연산보다 입출력 실행에 더 많은 시간을 소요하는 프로세스이다. 반면에 CPU bound process는 I/O bound process보다 연산에 시간을 더 소요하여 입출력 요청을 드물게 발생시키는 프로세스이다.
long-term scheduler는 I/O bound process와 CPU bound process들이 적절히 혼합되도록 선택하는 것이 중요하다.
1.3 중기 스케줄러(Medium-term scheduler or Swapper)
- 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
- 프로세스에게서 memory 를 deallocate
- degree of Multiprogramming 제어
- 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
- 프로세스의 상태
ready -> suspended
시분할 시스템과 같은 일부 운영체제들은 medium-term scheduler를 도입했다. medium-term scheduler의 핵심 아이디어는 메모리에서 프로세스들을 제거하여, 즉 CPU를 위한 경쟁에서 제거하여, 다중 프로그래밍의 정도를 완화하는 것이다. 차후에 다시 프로세스를 메모리로 불러와서 중단되었던 지점에서부터 실행을 재개한다. 이러한 기법을 swapping이라고 한다. swapping은 프로세스 혼합 상태를 개선하기 위하여 혹은 메모리가 가용 메모리를 초과하여 메모리를 비우기 위해 필요하다.
2. CPU 스케줄러(Scheduling Algorithm)
앞서 스케줄러의 종류에 대해서 알아보았다. 이제 이러한 스케줄링이 어떠한 알고리즘으로 이루어 지는지 알아보도록 하자. Ready Queue에 위치한 프로세스는 특정 기준을 통해 CPU 자원을 할당 받는데 이를 스케줄링 알고리즘이라고 한다. 예를들어 Process1이 처리되는 시간을 10 Process2가 처리되는 시간을 100이라 가정해보자.
1. Process1 -> Process2 순서대로 처리하면, 평균 응답시간은 5이다.
2. 반면, Process2 -> Process1 순서대로 처리하면, 평균 응답시간은 50이다.
이와같이 스케줄링을 어떻게 하냐에 따라, 시스템의 성능에 큰 영향을 미친다. 이러한 스케줄링 알고리즘의 종류는 아래와 같다.
FCFS(First Come First Served)
특징
- 먼저 온 고객을 먼저 서비스해주는 방식, 즉 먼저 온 순서대로 처리.
- 비선점형(Non-Preemptive) 스케줄링
일단 CPU 를 잡으면 CPU burst 가 완료될 때까지 CPU 를 반환하지 않는다. 할당되었던 CPU 가 반환될 때만 스케줄링이 이루어진다.
문제점
- convoy effect(콘보이 효과)
소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
CPU Burst란?
프로그램의 수행중에 연속적으로 CPU를 사용하는 구간 스케줄링의 단위가 된다.
SJF(Shortest - Job - First)
특징
- 다른 프로세스가 먼저 도착했어도 CPU burst time 이 짧은 프로세스에게 선 할당
- 비선점형(Non-Preemptive) 스케줄링
- 현재 ready queue에 도착한 프로세스들의 평균 대기시간이 최소가 되도록 스케줄링 한다.
문제점
- starvation(기아현상, 굶주림)
효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용 시간이 긴 프로세스는 거의 영원히 CPU 를 할당받을 수 없다.
SRTF(Shortest Remaining Time First)
특징
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
- SJF에 선점형 (Preemptive) 스케줄링을 도입한 방법이다.
현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다.
문제점
- starvation(기아현상, 굶주림)
Priority Scheduling
특징
- 우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
- 선점형 스케줄링(Preemptive) 방식
더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다. - 비선점형 스케줄링(Non-Preemptive) 방식
더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다.
문제점
- starvation
- 무기한 봉쇄(Indefinite blocking)
실행 준비는 되어있으나 CPU 를 사용못하는 프로세스를 CPU 가 무기한 대기하는 상태
해결책
- aging
아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여주자.
Round Robin
특징
- 현대적인 CPU 스케줄링
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
- 할당 시간이 지나면 프로세스는 선점당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.
- RR은 CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우에 효율적
- RR이 가능한 이유는 프로세스의 context 를 save 할 수 있기 때문이다.
장점
- Response time이 빨라진다.
n 개의 프로세스가 ready queue 에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n 을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. - 프로세스가 기다리는 시간이 CPU 를 사용할 만큼 증가한다.
공정한 스케줄링이라고 할 수 있다.
주의할 점
설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch 로 overhead 가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.
3. 선점과 비선점 스케줄링
위에서 살펴본 스케줄링 기법은 선점과 비선점 방식으로 나뉜다. 각각의 정의는 아래과 같다.
- 선점(Preemptive)방식 : 한 프로세스가 CPU를 할당받아 실행중이라도 다른 프로세스가 현재 프로세스를 중지 시키고 CPU를 강제적으로 뺏을 수 있는 스케줄링 방식
- 비선점(Nonpreemptive)방식 : 한 프로세스가 CPU를 할당받아 실행중이라면 다른 프로세스들이 CPU를 강제적으로 뺏을 수 없는 스케줄링 방식
이제 비선점 방식의 장점과 단점을 비교해 보자.
1) 비선점(Nonpreemptive) : FCFS, SJF
- 장점
- 모든 프로세스에 대한 공정한 처리
- 문맥교환으로 인한 오버헤드가 적음
- 단점
- burst time이 긴 프로세스에 의해 burst time이 짧은 프로세스가 기다리는 현상이 생길 수 있음
2) 선점(Preemptive) : SRTF, RR, Priority Scheduling
- 장점
- 우선순위가 높은 프로세스에 빠른 응답시간 보장
- 단점
- 프로세스간 문맥교환이 자주 발생
- 우선순위가 낮은 프로세스가 영원히 기다리는 기아 현상(Starvation)이 발생할 가능성이 있다.
추가로 좋은 스케줄링 방식을 판단하는 기준은 아래와 같다.
좋은 스케줄링 방식 판단 기준
- CPU utilization(CPU 사용량)
- Throughput(처리량)
- Turnaround time(처리 시간)
- Waiting time(대기 시간)
- response time(응답 시간)
4. Dispatch Latency와 Context Switching
1) Dispatch Latency
- 스케줄러가 선택한 프로세스를 CPU에 할당하는 것을 Dispatch라고 함
- Dispatcher가 하나의 프로세스를 중단하고, 다른 프로세스를 실행하기까지 소요하는 시간
2) Context Switching
- 인터럽트로 인해 다음 우선순위의 프로세스가 실행되어야 할 때, 기존의 상태(Context)를 PCB에 저장하고, 다음 프로세스를 수행할 수 있도록 다음 PCB로부터 상태(Context)를 레지스터에 적재하는 작업
참고 자료
https://lazymankook.tistory.com/25
https://rollercoaster25.tistory.com/60
https://jhnyang.tistory.com/372
https://dheldh77.tistory.com/entry/운영체제-스케줄러Scheduler
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS#스케줄러
'운영체제' 카테고리의 다른 글
| 프로세스 동기화(Process Synchronization) [파이썬(Python)] (0) | 2022.02.03 |
|---|---|
| Blocking, Non-blocking, Sync, Async 의 차이 (0) | 2022.02.02 |
| 운영체제란 무엇인가? (0) | 2022.01.27 |
| 프로세스와 스레드 (0) | 2022.01.26 |
| 메모리 구조 (코드, 데이터, 힙, 스택 영역) (0) | 2022.01.26 |
댓글