CPU 스케줄링

CPU 스케줄링 (=프로세스 스케줄링)

 

프로세스 스케줄링이란, CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업

 

스케줄링의 목표

- 처리율, CPU 이용률↑

- 오버헤드, 응답시간, 반환시간, 대기시간 ↓

 

*오버헤드란?

어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 의미

ex. A라는 작업을 실행하는 데에 10초가 소요되는데, 안전성을 고려하여 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초

 

 

 

1. 프로세스 상태

- 생성(Create) : 사용자에 의해 프로세스가 생성된 상태

- 준비(Ready) : CPU를 할당받을 수 있는 상태

   → 준비 리스트가 존재하며, 높은 우선순위를 가진 프로세스 순서대로 CPU를 할당받음

- 실행(Running) : 프로세스가 CPU를 할당받아 동작 중인 상태

- 대기(Waiting) : 프로세스 실행 중 입출력 처리 등으로 인해 CPU를 양도하고 처리가 완료될 때까지 대기 리스트에서 기다리는 상태

- 완료(Complete) : 프로세스가 CPU를 할당받아 주어진 시간 내에 완전히 수행을 종료한 상태

 

 

 

 

 

2. 프로세스 상태 전이

- 프로세스의 상태가 준비, 실행 및 대기 상태 등으로 변하는 활동을 의미

- 활동 상태란, 프로세스가 기억장치를 할당받은 상태

- 지연 상태란, 프로세스가 기억장치를 할당받지 못한 상태

 

* 디스패치 (Dispatch) : 준비 상태 리스트에 있는 프로세스들 중 실행될 프로세스를 선정하여 CPU를 할당

* 타이머 런 아웃 (Timer run out = Timeout) : CPU를 할당받은 프로세스는 지정된 시간이 초과되면 스케줄러에 의해 PCB에 저장, CPU 반납 후 다시 준비 상태로 전이

* 블록 (Block) : 실행 상태에 있는 프로세스가 지정된 시간을 초과하기 전에 입출력이나 기타 사건 등이 발생하면 CPU를 스스로 반납하고, 입출력이 완료될 때까지 대기 상태로 전이

* 웨이크 업 (Wake-up) : 어느 순간 입출력이 종료되면, 대기 상태에서 준비 상태로 전이

* Swap-in : 프로세스에게 다시 기억장치가 할당될 경우

* Swap-out : 프로세스가 기억장치를 잃은 경우

 

 

 

 

 

3. 프로세스 스케줄링 주요 용어

- 시간 할당량 : 한 프로세스가 프로세서를 독점하는 것을 방지하기 위해 서비스되는 시간 할당량

- 서비스 시간 : 프로세스가 결과를 산출하기까지 소요되는 시간

- 응답시간(반환시간) : 프로세스들이 입력되어 수행하고 결과를 산출하기까지 소요되는 시간

- 대기 시간 : 프로세스가 자원의 할당을 대기하는 시간

 응답시간 = 대기시간 + 수행시간(=서비스 시간)

 

 

 

 

 

4. 프로세스 스케줄링 유형

 

4-1) 선점형 스케줄링

- 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식

 

 

- 장점

비교적 빠른 응답

대화식 시분할 시스템에 적합

 

*시분할 시스템이란? 여러 사용자가 각자의 단말장치를 통하여 동시에 운영체제와 대화하면서 각자의 프로그램을 실행하는 듯한 느낌을 받는 방식

 

 

- 단점

높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래

 

- 종류

1) 라운드 로빈 (Round Robin)

- 모든 프로세스는 같은 크기의 CPU 시간을 할당받음(시간 할당량)

- 프로세스가 할당된 시간 내에 처리 완료를 못하면 준비 리스트의 가장 뒤로 보내지고, CPU는 대기 중인 다음 프로세스로 넘어감

 

 

2) SRT (Shortest Remaining Time First)

- 가장 짧은 시간이 소요되는 프로세스를 가장 먼저 수행

- 남은 처리시간이 더 짧다고 판단되는 프로세스가 준비 리스트에 생기면, 언제라도 프로세스가 선점됨

 

 

3) 다단계 큐 (MLQ: Multi Level Queue)

- 어떤 프로세스냐에 따라서 여러 종류의 그룹으로 분류하고, 여러개의 큐에 다양한 알고리즘을 적용하는 스케줄링 방식

   → 운영체제는 프로세스를 분류할때 보통 사용자와 상호작용하는 앞단의 프로세스(ex.구글검색)를 중요하게 여기고, 백그라운드에서 돌아가는 프로세스들 (ex.압축풀기, 영화다운로드)은 상대적으로 덜 중요하다고 판단

- 각각의 큐는 자신의 스케줄링 알고리즘(RR, FCFS 등)을 수행

 

 

4) 다단계 피드백 큐 (MFQ: Multi Level Feedback Queue)

- 다단계 큐와 비슷하지만, 프로세스들이 큐를 이동할 수 있음

- 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고 마지막 단계는 라운드 로빈 방식을 적용

 

 

 

 

 

4-2) 비선점형 스케줄링

- 하나의 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식

 

 

- 장점

응답시간 예상 용이

모든 프로세스에 대한 요구를 공정하게 처리

 

- 단점

짧은 작업을 수행하는 프로세스가 긴 작업 종료시까지 대기해야 함

 

- 종류

1) 우선순위 (Priority)

- 프로세스별로 우선순위가 주어지고, 해당 우선순위에 따라 CPU를 할당함

- 동일 순위는 FCFS(FIFO)로 처리

 

 

2) 기한부 (Deadline)

- 작업들이 명시된 시간이나 기한 내에 완료되도록 계획

 

 

3) FCFS (First Come First Service) = FIFO (FIRST IN FIRST OUT)

- 프로세스가 대기 큐에 도착한 순서에 따라 CPU를 할당받음 (도착 순서대로 처리)

 

 

4) HRN (High Resposne Ratio Next)

- 대기 중인 프로세스 중 현재 응답률(Response Ratio)이 가장 높은 것을 선택 (우선순위를 계산하여 선택)

- HRN의 우선순위 : (대기시간 + 서비스시간) / 서비스시간

 

 

5) SJF (Shortest Job First)

- 프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료시까지 자원을 점유

 

* SRT vs SJF

SRT는 다른 프로세스가 실행 중에, 서비스 시간이 짧은 프로세스가 생기면 언제든지 자원을 점유할 수 있음

반면 SJF는 한번 서비스 시간이 가장 짧은 프로세스가 자원을 점유하게 되면, 해당 작업이 끝날 때까지 계속 자원을 점유