[SW] 프로세스 스케쥴링

컴퓨터 시스템 구조 (Computer System Architecture)

단일 CPU 시스템

다중 CPU 시스템

분산 시스템

 

프로세스 스케쥴링 기법?

프로세스(Process)란? 실행 중인 프로그램으로, 프로세스는 작업, task, job 등의 용어와 혼용함.

응용프로그램은 여러 개의 프로세스로 이루어 질 수 있으므로, 응용프로그램이 프로세스는 아님

프로세스 스케쥴링은 실행 중인 모든 프로세스들에게 CPU 시간을 골고루 할당하기 위한 방법이다.

스케쥴링 알고리즘의 선택은 목표에 따라 다르다.

- 시분할 시스템은 프로세스 응답 시간을 가능한 짧게

- 멀티 프로그래밍은 CPU 사용량을 최대화, 프로세스를 빨리 실행

스케쥴링 알고리즘의 선택 기준은 다음 등이 있다.

- CPU 사용률을 높게

- 단위 시간당 처리한 프로세스 양이 많을 수록

- 프로세스의 대기 시간이 적게

- 프로세스의 응답 시간이 적게

- 프로세스의 반환 시간이 적게

 

일괄처리 시스템 (Batch Systems)

멀티 프로그래밍 (Multi-Programming) : 최대한 CPU를 활용하는 시스템

시분할(Time-sharing)/멀티태스킹(Multi-tasking) : CPU 점유 시간을 분할하여 태스크를 할당

 

프로세스 스케쥴링 방법들

일괄 처리 시스템 : 자동으로 다음 응용 프로그램이 이어서 실행할 수 있도록 하는 시스템

시분할 시스템 : 응용프로그램이 CPU 점유 시간을 잘게 쪼개어 실행될 수 있도록 하는 시스템/다중 사용자도 지원하는 시스템

- 멀티 태스킹과 멀티 프로세싱 : 동시에 실행되는 것처럼 보이도록.

멀티 태스킹 : 단일 CPU에 대해서 CPU 점유 시간을 시분할하여 태스크를 할당함

멀티 프로세싱 : 여러 CPU에 대해서 하나의 프로그램을 병렬로 실행하여 실행시간을 극대화함.

 

멀티 프로그래밍? 최대한 CPU를 활용하도록 하는 시스템

예를 들면 저장매체에서 데이터를 읽어오는데 해당 장치들은 시간이 오래걸리니 이때 요청한 데이터가 오기 까지 CPU에게 다른 일을 시킨다.

 

용어 정리

범용 OS / 실시간 OS

- 범용 OS (General-Purpose OS)

 프로세스 실행시간에 민감하지 않고, 일반적인 목적을 위해 설계된 OS로, Windows, Linux 등이 있다.

- 실시간 OS (Real-Time OS)

 응용 프로그램의 실시간 성능 보장을 목적으로 설계된 OS으로, 사용되는 목적이 구체적이고 제한적이다.

 

연성/경성 실시간 시스템(Soft/Hard Real-Time System)

 두 시스템의 가장 중요한 차이점은 Time-Critical한 속성을 지니는가이다.

 외부 이벤트(작업 요청)에 대한 명시된 시간 제약인 데드라인(Dead Line)의 엄격성에 따라 구분된다.

 - Soft Real-Time System

 데드라인을 넘어도 시스템의 성능에 크게 영향을 주지 않는다. (PC, 모바일 기기 등)

 - Hard Real-Time System

 데드라인을 넘기면 시스템에 심각한 영향을 준다. (원전, 항공기, 자동차 등)

 

스케쥴링 기법의 분류와 예

비선점형 (Non-Preemptive) / 선점형 (Preemptive) 스케쥴링

선점/비선점은 어떤 프로세스가 다른 프로세스 대신 프로세서(CPU)를 선점할 수 있는지에 따라 구분된다.

- 비선점형 스케쥴링

 현재 실행중인 프로세스를 끝내야 다른 프로세스가 프로세서를 사용할 수 있다.

 ex) FIFO(First-In First-Out), SJF(Shortest Job First), HRN(High Response Rate Next)

- 선점형 스케쥴링

 현재 실행중인 프로세스 대신 우선순위가 높은 다른 프로세스가 프로세서를 사용할 수 있다.

 ex) 전경/배경(Foreground/Background), RR(Round Robin), SRT(Shortest Remaining Time), MQ(Multi-level Queue)

우선순위 기반(Priority-Based) 스케쥴링

 우선순위가 높은 작업이 먼저 CPU를 사용하게 도는 방법이다.

 문제점 : 우선순위가 낮은 작업은 무한 대기 상태가 발생할 수 있다.

- 정적 우선순위 (Fixed Priority Scheme)

 프로세스마다 우선순위가 미리 지정함.

- 동적 우선순위 (Dynamic Priority Scheme)

 스케쥴러가 상황에 따라 우선순위를 동적으로 변경

 

FIFO 스케쥴러

 가장 간단한 구조(일괄 처리 시스템)로, 요청한 순서대로 처리한다. FCFS (First-Come First-Served)라고도 부른다.

 문제점 : 공평할 순 있지만, 작업 시간이 오래 걸리는 프로세스가 앞에 끼면 평균적인 대기시간(waiting time)이 길어지는 Convoy effect가 나타난다.

최단 작업 우선(SJF, Shortest Job First) 스케쥴러

 가장 실행 시간이 짧은 프로세스부터 먼저 CPU를 사용한다.

 빨리 끝나는 프로세스를 먼저 끝내기 때문에 평균적인 대기시간이 짧아지는 효과가 있다.

 문제점 : 실행 시간을 예측하기가 어렵다. 공평성의 위배로, 작업 시간이 긴 프로세스는 순서가 밀리는 아사(Starvation) 현상이 발생. 이는 에이징(Aging) 기법으로 해결할 수 있다.

HRN(Highest Response Rate Next)

 대기 시간과 실행 시간을 통해서 우선순위를 정하여 CPU를 사용한다. 대기 시간이 긴 프로세스의 CPU 사용률을 높여서 SJF의 아사 현상을 완화한다.

우선순위 = (대기시간+실행시간)/실행시간

 문제점 : 여전히 공평성을 위배한다.

 

전경/배경 스케쥴링 알고리즘

 매우 간단한 선점형 스케쥴링 알고리즘으로 수퍼루프(Super-Loop)라고도 부른다.

 주기적으로 원하는 작업(함수)를 수행하는 무한루프인 배경 프로세스와 인터럽트 서비스 루틴(ISR, Interrupt Service Routine)으로 전경 프로세스에서 비동기 이벤트들을 처리한다. 그래서 배경에서 무한루프 작업을 수행하다가 인터럽트가 걸리게되면 멈추어 전경에 있는 인터럽트부터 처리한 후에 배경으로 복귀한다.

 여기서 우선순위는 하드웨어 종속적으로 결정되어 있으며, 제공되는 인터럽트 벡터 테이블(Interrupt Vector Table)에 정의된 우선순위에 따라 인터럽트가 실행된다.

 간단하고 소형의 시스템에 적합하며, 배경의 스케쥴링은 순수 RR 스케쥴러에 가깝다.

 문제점 : 빈번한 인터럽트 작업 시간으로 인해 배경 프로세스에 아사(Starvation) 현상이 발생 할 수 있으며

라운드 로빈(RR, Round Robin) 스케쥴러

 시분할 시스템을 위해 FIFO 알고리즘을 선점형으로 변형한 기법이다.

 대기 큐를 사용하여, 대기 큐에 먼저 들어온 프로세스가 먼저 CPU를 사용한다. 시간 단위 동안 CPU를 사용한 후에 다시 대기 큐에 배치하여 대기한다.

 문제점 : 시간 단위(Time Slice, Quantum)이 클 경우 FIFO와 유사하며, 작을 경우 문맥 교환(Context Switching)의 오버헤드(Overhead)가 불필요하게 증가하기 때문에 적당한 시간 단위를 설정해야한다.

최단 잔여 시간(SRT, Shortest Remaining Time) 스케쥴러

 최단 작업 우선(SJF) 알고리즘을 선점형으로 변형한 기법이다. (RR+SJF)

 진행 중인 프로세스가 있어도 최단 잔여시간인 프로세스가 먼저 CPU를 사용한다.

 문제점 : SJF 와 동일

다단계 큐(Multi-Level Queue) 스케쥴러

 프로세스의 우선순위에 따라서 대기 큐를 다르게 배정하고, 우선순위를 가지는 대기 큐를 사용한다.

 

참고문헌

1. "[운영체제 OS] 스케줄링 알고리즘 SJF(Shortest Job First) 정리, 장점, 한계, non preemptive," jhnyang.tistory.com/155

2. "[운영체제 OS] FIFO/FCFS(피포/first come first served)정의와 문제 & Convey Effect," jhnyang.tistory.com/34

3. "[09.스케쥴링 알고리즘과 우선순위]," popcorntree.tistory.com/60

4. "선점형(preemption), 비선점형(non-preemption) 스케쥴링," maxpulse.tistory.com/208

5. 옹주의 개발블로그, "CPU 스케쥴링 알고리즘 : FCFS, SJF, HRN, RR, SRT [과제:구현하기]," m.blog.naver.com/silro812/221567674463