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

Hailey Park·2022년 2월 9일

Computer Science

목록 보기

6/6

프로세스 상태와 변화

컴퓨터 하드웨어인 CPU는 여러개의 프로세스를 동시에 실행할 수 없다.
언제나 한순간에 오직 1개의 프로세스를 수행한다.
다만, 운영체제의 멀티태스킹(Multi tasking)과 스케줄링 기법으로 여러개의 프로세스가 동시에 실행되는 것처럼 보일뿐이다.

프로세스 상태 (Process State)

New : 프로세스가 생성되는 중
Running : CPU에서 명령이 실행되는 중
Waiting : 프로세스가 어떤 event(입출력 완료, signal 수신)가 발생하기를 기다리는 중
Ready : 프로세스가 CPU에 할당되어 실행되기를 기다리는 중
Terminated : 프로세스 실행 종료

프로세스 상태 변화

new -> ready -> running
프로세스가 생성(New)되면 Ready 상태에 있다.
여러개의 프로세스들은 대부분 Ready 상태에 있고, 운영체제의 스케줄링 기법에 따라 그 중 단 1개만 Running 으로 바뀔 수 있다.
Running 상태가 되면 실제 CPU를 이용해서 하고자하는 일을 수행한다.

운영체제 스케줄러(Scheduler)란?
여러개의 프로그램을 동시에 실행되는 것처럼 보이게 하기 위해 어떤 규칙을 부여하는 것.

running -> waiting -> ready
Running 상태에 있는 프로세스는 계속 실행되는 것이 아니라 어떤 조건이 만족되면 상태가 변경된다.
예를 들어 scanf, read, printf 등 외부장치에 대해 입출력을 요구했을 때이다.
이 작업은 굉장히 느리기 때문에 CPU는 무작정 기다리는 것이 아니라 상태를 Waiting 으로 바꾸게 된다.
Waiting이 끝나는 시점은 I/O 이벤트 완료 인터럽트가 발생될 때이다.
이 인터럽트가 발생되면 다시 Ready 상태가 되어 다시 스케줄러에 의한 실행을 기다리게 된다.
running -> exit
Running 상태에 있던 프로세스의 종료를 의미한다.

running -> ready -> running -> ready -> running -> ready ....
1ms ~ 10ms 마다 타이머 인터럽트가 발생하여 운영체제는 현재 실행중인 프로세스를 강제로 중지를 시킨 뒤 Ready 상태로 빼놓는다.
그리고 Ready 상태에 있는 다른 프로세스를 실행 시킨다. 이 과정은 매우 빠르게 상태 변화를 일으키며 반복되기 때문에 마치 여러개의 프로세스가 1개의 CPU를 가지고 동시에 실행되는 것처럼 보인다.
=> 이를 통해 운영체제는 멀태태스킹 멀티프로세싱을 달성하게 된다.

프로세스 제어 블록(Process Control Block, PCB)

PCB는 프로세스에 대한 모든 정보가 모여있는 곳으로, Task Control Block(TCB) 이라고도 한다.

PCB안에는 프로세스의 상태, 프로세스 번호(PID), 해당 프로세스의 program counter(pc), register값, MMU정보, CPU점유 시간 등이 포함되어 있다.

PCB는 운영체제 내부의 프로세스를 관리하는 코드 부분에 저장되어 있다.

CPU는 한 프로세스가 종료될 때까지 수행하는 것이 아니라 여러 프로세스를 중간 중간에 바꿔가면서 수행한다.

그러므로 CPU는 수행중인 프로세스를 나갈 때, 이 프로세스의 정보를 어딘가에 저장하고 있어야 다음에 이 프로세스를 수행할 때 이전에 수행한 그 다음부터 이어서 작업할 수 있다.

이러한 정보를 저장하는 곳이 PCB이다.

Context Switching 과정

프로세스 큐 (Queue)

RAM에 적재된 프로세스는 한 개가 아니기 때문에 프로세스가 CPU의 서비스를 받으려면 순서를 기다려야 한다.

이 순서는 몇 가지 Queue에 의해 관리가 되며 스케쥴링을 위한 Queue는 크게 세 종류가 있다.

Job Queue
- 프로세스가 시스템에 들어오면 job queue에 놓인다.
- RAM은 용량이 적기 때문에 원하는 프로그램을 모두 RAM으로 옮길 수 없고, 따라서 RAM으로 올라올 프로그램을 정하는 queue가 job queue이다.
- 하드 디스크에 있는 프로그램이 실행되기 위해 메인 메모리의 할당 순서를 기다리는 queue.
Ready Queue
- CPU 점유 순서를 기다리는 queue
Device Queue
- I/O를 하기 위한 여러 장치가 있는데, 각 장치를 기다리는 Queue가 각각 존재한다.

위와 같이 여러 큐가 존재하는데, 각 큐 내부에 저장된 실제 데이터는 각 프로세스의 PCB가 저장되어 있다. 그리고 이러한 순서를 기다리는 공간이 있다면 이 순서를 정해주는 알고리즘이 있어야 한다. 이러한 알고리즘을 스케줄링(Scheduling)이라 한다.

Job Queue - Job Scheduler(Long-term scheduler)
- 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정하는 역할을 한다.
- 메모리와 디스크 사이의 스케줄링을 담당.
- degree of Multiprogramming 제어 (실행중인 프로세스의 수 제어)
- Job queue의 순서를 정해주는 job scheduler를 long-term scheduler라고도 하는데, 이는 이 스케줄링이 발생하는 시간이 비교적 오래걸리기 때문이다. (프로그램이 RAM으로 올라오는 일은 상대적으로 덜 일어남)
- 또한, 프로세스는 연산의 비중이 높은 프로세스와 입출력의 비중이 높은 프로세스로 나뉘는데, 두 종류의 프로세스의 균형을 맞추는 것도 이 스케쥴러가 담당한다.
- new->ready로 상태 전이 시켜줌

cf) 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않은 것이다. 참고로 time sharing system (시분할 시스템) 에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.

Ready Queue - CPU Scheduler(Short-term scheduler)
- CPU 와 메모리 사이의 스케줄링을 담당.
- Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.
- ready queue의 스케줄러를 short-term scheduler라고도 하는데, 이는 스케줄링이 발생하는 시간이 매우 짧기 때문이다. CPU scheduling은 말 그대로 프로세스가 CPU를 점유하는 순서를 정해주는데 이는 매우 빠른 시간안에 이루어져야한다. 현대 컴퓨터가 여러 프로그램을 동시에 사용하는 것과 같은 효과를 주는 이유가 이 스케줄링 속도가 매우 빠르게 이루어지기 때문이다. (이런 작업은 빈번히 발생됨)
- ready -> running으로 상태 전이 시켜줌
Device Queue - Device Scheduler
- 해당 장치를 어느 프로세스가 사용할 지 결정하는 스케줄러
- waiting 상태에 있는 프로세스가 입출력 서비스를 받으면 다시 ready 상태로 돌아감
Medium-term Scheduler
- Medium-term scheduler는 말그대로 short-term보다는 덜 발생하지만, long-term보다는 자주 발생하는 scheduler이다.
- 하는 일은 운영체제가 실행하는 동안 주기적으로 메인 메모리에 있는 전체 프로세스를 검사하여 보조기억장치로 옮길 프로세스를 찾아 옮긴다. 옮기는 기준은 여러가지 있겠지만 대표적으로 장기간 사용하지 않는 프로세스가 있다.
- 이 기준으로 동작하는 것이 Swapping이다. 이는 메인 메모리에서 장시간 사용하지 않는 프로세스를 하드디스크(Swap device = Backing store, 일반적으로 하드디스크는 File system + Backing store 로 구성되어 있다.)로 옮겨주고(Swap out), 나중에 이 프로세스가 다시 사용되려고 하면 하드디스크에서 해당 프로세스를 다시 메인 메모리에 할당해준다.(Swap in)
- Swap out을 통해 메인 메모리의 공간이 생기므로 이를 더욱 효율적으로 사용할 수 있다. 만약 swap out된 프로세스가 다시 swap in으로 메인 메모리에 할당하려고 할 때 이전의 공간으로 할당되는 것을 보장하지는 않는다. 왜냐하면 위에 말했듯이 swap out으로 생긴 메모리 공간은 다른 프로세스가 사용할 수 있기 때문이다.

CPU Scheduling

CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업 - 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것
프로세스들에게 자원을 최대한 공평하게 배분하며 처리율과 CPU 이용률을 증가시키고, 오버헤드, 응답시간(Response time / Turnaround time), 대기시간을 최소화하기 위한 기법
선점형 스케줄링(Preemptive Scheduling) 과 비선점형 스케줄링(Non-preemptive / Cooperative Scheduling) 이 있음
메모리에 여러 개의 프로세스를 올려놓고(다중 프로그래밍), CPU의 가동시간을 적절히 나누어(시분할) 각각의 프로세스에게 분배하여 실행

CPU 스케줄링이 발생하는 상황

실행 상태에 있던 프로세스가 I/O 요청 등에 의해 Block 상태가 되는 경우
실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 되는 경우
I/O 요청으로 Block 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고, 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
CPU에서 실행 상태에 있는 프로세스가 종료되는 경우

선점형 스케줄링과 비선점형 스케줄링

선점형 스케줄링 기법 (Preemptive)
- 하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식
- 비교적 응답이 빠르다는 장점이 있지만, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드를 초래
- 실시간 응답환경, Deadline 응답환경 등 우선순위가 높은 프로세스를 빠르게 처리해야 할 경우 등에 유용
- 스케줄링 알고리즘 : 라운드 로빈, 다단계 큐, 다단계 피드백 큐

비선점형 스케줄링 기법 (Non-preemptive)
- 한 프로세스가 CPU를 할당받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 PCU 점유가 불가능한 스케줄링 방식
- 모든 프로세스에 대한 요구를 공정하게 처리할 수 있지만, 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기해야할 수도 있다. (콘베이 현상)
- 처리시간 편차가 적은 특정 프로세스 환경에 용이
- 전체 시스템 입장에서 낮은 처리율 (단점)
- 스케줄링 알고리즘 : 우선순위, 기한부, 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 사용시간으로 우선순위를 설정한 비선점형 스케줄링
SJF의 아사현상을 해결하기 위한 기법이나, 여전히 공평성이 낮아 사용 X
우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간

RR (Round Robin) 스케줄링

순환순서.
FIFO 스케줄링 기법을 Preemptive(선점형)기법으로 구현한 스케줄링 방법으로, 프로세스는 FIFO형태로 대기 큐에 적재되지만, 주어진 시간 할당량(time slice)안에 작업을 마쳐야 하며, 할당량을 다 소비하고도 작업이 끝나지 않은 프로세스는 다시 대기 큐의 맨 뒤로 되돌아간다.
시스템이 사용자에게 적합한 응답시간을 제공해주는 대화식 시분할 시스템에 적합

SRT (Shortest Remaining Time) 스케줄링

SJF + RR 형식의 선점형 스케줄링
여전히 운영체제는 프로세스의 남은 시간을 계산하기 힘들 뿐만 아니라 아사 가능성도 존재
새로 도착한 프로세스를 비롯하여 대기 큐에 남아있는 프로세스의 작업이 완료되기까지의 남아있는 실행시간 추정치가 가장 적은 프로세스에 먼저 CPU 할당

MLQ (Multi-Level Queue) 스케줄링

다단계 큐 스케줄링
우선순위에 따라 여러 queue가 존재 -> 고정형 우선순위
높은 우선순위의 queue부터 순서대로 실행

MLFQ (Multi-Level Feedback Queue) 스케줄링

다단계 피드백 큐 스케줄링
CPU 사용 후에는 우선순위를 하나 낮춰주어 MLQ의 저순위 queue의 불리함을 보완한 방법
새로운 프로세스는 그 특성에 따라 각각 대기 큐에 들어오게 되며, 그 실행 형태에 따라 다른 대기 큐로 이동
예를 들어 연산 위주의 프로세스들은 처음에 RR방식의 대기 큐에서 주어진 시간 할당량이 만료되면 다음 단계의 큐에 배치되고, 실행시간이 길수록 점점 낮은 우선순위를 지니게 되어 마지막 가장 낮은 우선순위의 큐에 도달하면 작업이 끝날 때까지 RR방식으로 스케줄된다

우선순위 (Priority) 스케줄링

각 작업마다 우선 순위가 주어지며, 우선 순위가 제일 높은 작업에 먼저 CPU가 할당되는 방법
우선 순위가 낮은 작업은 Indefinite Blocking이나 Starvation에 빠질 수 있고, 이에 대한 해결책으로 체류 시간에 따라 우선 순위가 높아지는 Aging 기법을 사용할 수 있다