[운영체제] 프로세스 스케줄링

■ 프로세스(Process)의 정의

 주기억 장치에 저장된 프로그램. 즉, 실행중인 프로그램을 뜻한다. 작업(Job) 또는 태스크(Task)라고도 불린다.

 

[특징]

1. 운영체제가 관리하는 최소 단위의 작업

2. 프로세서가 할당되는 실체

 

[관련 용어]

* 프로그램 (Program)
: 보조기억장치에 저장된 프로그램

 

* 프로세스 (Process)

: 주기억 장치에 적재된 프로그램. 즉 CPU가 '실행'중인 프로그램

 

* 프로세서 (Processor)
: 프로세스를 처리하는 CPU이다.

■ 프로세스 상태 전이도

* 주요 3가지 상태

 : 준비, 실행, 대기

 

그림판으로 못생겼지만 그려봤다

상태	설명
제출 상태 (Submit)	처리할 작업을 시스템에 제출한 상태
접수 상태 (Hold)	제출된 작업이 스풀(Spool) 공간인 디스크에 저장된 상태
준비 상태 (Ready)	(★) 프로세스가 CPU를 사용하여 실행될 수 있는 상태
실행 상태 (Run)	(★) 프로세스가 CPU를 차지하여 실행 중인 상태
대기 상태 (Wait, Block)	(★) 어떤 사건이 발생하기를 기다리는 상태
종료 상태 (Terminate, Exit)	프로세스가 CPU를 할당받아 주어진 시간 내에 완전히 수행을 종료한 상태

 

 

[관련 용어]

용어	설명
(★) Dispatch	준비 상태에 있는 여러 프로세스 중 우선 순위가 가장 높은 프로세스를 선택하여 CPU를 할당 하는 것. (준비 -> 실행)
Timer Runout (시간 만료)	CPU를 할당 받아 실행 중인 프로세스가 할당시간을 초과하면 CPU를 다른 프로세스에게 양도하고 자신은 준비상태로 전이되는 것
Interrupt (인터럽트)	CPU의 정상적인 실행을 방해하는 이벤트가 발생한 것. 즉 방해하는 무엇인가가 발생했다는 것이다. 이때 프로세스는 마이크로프로세서(CPU)에게 처리를 요청한 뒤, 실행을 잠시 멈추고, 해당 상황이 종료된다면 다시 작업을 재개 한다.  (ex) 정전, 입출력 오류 발생 등
Block	실행 중인 프로세스가 지정된 시간 이전에 다른 작업(Interrupt)을 위해 스스로 프로세서(CPU)를 양도하고 대기 상태로 전이되는 것. (실행 -> 대기)
Wake Up	실행중인 프로세스가 완료되어 대기 중인 프로세스를 준비 상태로 전이하는것  (대기 -> 준비)
Scheduler (스케줄러)	프로세스를 생성, 실행, 중단, 소멸 시키는 것.
Spooling (스풀링)	저속의 입/출력 장치와 고속의 CPU 간의 속도 차이를 해소하기 위한 방법 (아래 부가설명 有)
Codec (코덱)	(번외로 추가한 용어) 디지털 비디오와 오디오를 위한 압축/복원 기술
Partition (파티션)	(번외로 추가한 용어) 영역을 분할 하는 것 (ex) 디스크를 물리적으로 한 공간이지만 논리적으로 C드라이브, D드라이브로 나누는 것
Fragmentation (단편화)	(번외로 추가한 용어) 기억 장소에서 빈 공간이 발생하거나 또는 자료가 여러 개의 조각으로 나뉜 현상

 

■ 스풀링

다중 프로그래밍 환경 하에서 용량이 크고 신속한 엑세스가 가능한 디스크를 이용하여 각 사용자 프로그램의 출력할 데이터를 직접 프린터로 보내지 않고 디스크에 모았다가 나중에 한꺼번에 출력함으로써 프린터 장치의 공유 및 프린터 처리 속도를 보완하는 기법

 

 

- 어떤 작업의 입/출력과 다른 작업의 계산을 병행 처리(이원화)하는 기법

- 스풀링은 디스크 일부를 매우 큰 버퍼처럼 사용하는 기법이다.

기준	스풀링  (Spooling)	버퍼링 (Buffering)
공통점	저속의 입출력 장치와 고속의 CPU 간의 속도 차이를 해소하기 위해서 나온 방법
차이점	1. 보조 기억장치 (디스크)와 CPU 간의 속도차이 개선 2. 다중 작업 (Multi-Tasking) 방식이다.	1. 주기억장치와 CPU 간의 속도차이 개선 2. 단일 작업 (Single-Tasking) 방식이다. 즉 병행처리가 안된다.
* 버퍼 (Buffer) 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 명역 송신자와 수신자의 속도 차이를 해결해준다.

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

   컴퓨터 시스템의 성능을 높이기 위해 그 사용 순서를 결정하기 위한 정책
      - 프로세스가 수행(실행) 상태, 대기 상태, 준비 상태와 같은 변환 과정을 반복할 때, 각 프로세스에게 중앙처리장치의 사용 시간을 할당하는 것


[목적 (성능평가)]
   : 처리량 증가, 응답 시간/ 반환시간/ 대기 시간 최소화, 모든 작업에 대해 공평성 유지 


[스케줄링 기법의 종류]
(1) 비선점 스케줄링 (Non Preemptive) : 비효율적, 비양보
- 프로세스에게 이미 할당된 CPU를 강제로 빼앗을 수 없고, 사용이 끝날 때 까지 기다려야하는 방법
- 일괄 처리(오버헤드 발생x), 실시간 처리가 안되므로 중요한 작업이 기다리는 경우 발생
- 대표적인 스케줄링 : FIFO, SJF, HRN

(2) 선점 스케줄링  : 효율적
- 우선 순위가 높은 다른 프로세스가 할당된 CPU를 강제로 뺴앗을 수 있는 방법 (양보)
- 실시간 처리, 대화식 시분할 처리(오버헤드 발생 할 수 있음)
- 대표적인 스케줄링 : RR, SRT

■ 비선점 스케줄링의 종류

종류	설명
FIFO (First In First Out)	준비 상태에서 도착한 순서에 따라 CPU 할당 (선입선출) = FCFS (First Come First Service)
SJF (Shortest Job First)	작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행
HRN (Highest Response ration Next)	SJF 방식의 단점 (긴 작업과 짧은 작업간의 지나친 불평등)을 보완하는 기법
우선 순위	대기 큐에서 기다리는 각 프로세스마다 우선 순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당해주는 기법

 

■ 선점 스케줄링의 종류

종류	설명
RR (Round-Robin)	(★) 대화식 시분할 시스템(TimeSharingSystem)을 위해 고안된 방식으로, FIFO방식의 선점형 기법. [특징] 할당되는 시간이 클 경우 FCFS기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환(Context Switch) 및 그에 따른 오버헤드가 발생한다.
SRT (Shortest Remaining Time)	SJF 방식의 선점형 기법으로, 현재 실행중인 프로세스의 남은 시간과 준비 상태 큐에 새로 도착한 프로세스의 실행시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법.
다단계 큐(MQ) (Multi-level Queue)	프로세스들을 우선 순위에 따라 시스템 프로세스, 대화형 프로세스, 일괄처리 프로세스 등으로 상위, 중위, 하위 단계의 단계별 준비 큐를 배치하는 기법. * 큐 사이에 우선 순위를 부여하는 기법이다.
다단계 피드백 큐(MFQ) (Multi-level Feedback Queue)	특정 그룹의 준비 상태 큐에 들어간 프로세스가 다른 준비 상태 큐로 이동할 수 없는 MQ기법을 준비 상태 큐 사이를 이동할 수 있도록 개선한 기법

 

(RR 예시)

A작업이 8초 걸리는 작업, B작업이 6초 걸리는 작업, C 작업이 5초 걸리는 작업일때, 각 작업의 시간할당량(Time Slice)이 5초일 경우

 

* 오버헤드 (Overhead)

: 어떤 처리를 하기위해 간접적으로 들어가는 시간 ● 메모리 (예시)

 

(MQ 예시)

 

 

(MFQ 예시)