[OS] CPU 스케줄링

스케줄링

CPU 스케줄러

스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위를 기반으로 CPU를 할당받게 해주는 역할을 한다.

고수준 스케줄링

가장 큰 틀에서 이루어지는 CPU 스케줄링으로 장기 스케줄링 또는 작업 스케줄링이라고 한다. 고수준 스케줄링은 시스템 내의 전체 작업 수를 조절하는 것을 말한다. 이 단계에서는 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다. 작업 요청이 오면 스케줄러가 시스템의 상황을 고려하여 작업을 승인할지, 거부할지 결정하여 승인 스케줄링이라고도 부른다. 이를 통해 동시에 실행 가능한 프로세스의 총 개수가 정해진다.

중간수준 스케줄링

중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는다. 즉, 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 원만하게 작동하도록 지원한다. 이는 프로세스의 상태 중 보류 상태에 해당하며, 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 한다. 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화된다.

저수준 스케줄링

실제로 작업이 이루어지는 스케줄링으로 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 일이다. 예를 들어 준비 상태에 있는 프로세스 중 하나를 골라 실행 상태로 보내고, 실행 상태에 있는 프로세스를 대기 상태로 보내며, 대기 상태의 프로세스를 준비 상태로 보내는 것을 의미한다. 저수준 스케줄링은 아주 짧은 시간에 일어나기 때문에 단기 스케줄링이라고도 한다.

CPU 스케줄링의 목적

• 공평성: 모든 프로세스가 자원을 공평하게 배정받고, 자원 배정 과정에서 특정 프로세스가 베제되어서는 안된다.
• 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 준다.
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정, 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호한다.
• 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
• 반응 시간 보장: 응답이 없는 경우, 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

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

선점형 스케줄링

어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식이다. 대표적인 예로는 인터럽트 처리가 있다. CPU가 인터럽트를 받으면 현재 실행 중인 작업을 중단하고 커널을 깨워서 인터럽트를 처리시키며, 인터럽트 처리가 완료되면 원래의 작업으로 돌아간다.

이는 문맥 교환과 같은 부가적인 작업으로 인해 낭비가 생기는 거이 단점이다. 그러나 하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.

비선점형 스케줄링

어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 방식이다. 선점형 스케줄링보다 작업량이 적고 문맥 교환에 의한 낭비도 적다. 하지만 CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어진다. 과거의 일괄 작업 시스템에서 사용하던 방식이다.

프로세스 우선순위

대부분의 CPU 스케줄러는 우선순위를 사용한다. 프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉜다. CPU 스케줄러는 각 프로세스에 우선순위를 부여하는데 커널 프로세스가 일반 프로세스보다 중요도가 높다.

우선순위가 높다는 것은 그만큼 더 빨리 자주 실행된다는 것이다. 준비 상태의 커널 프로세스와 일반 프로세스가 있다면 커널 프로세스의 우선순위가 더 높기 때문에 커널 프로세스가 먼저 실행되며 작업이 끝날 때까지 계속 CPU를 사용한다.

또한, 일반 프로세스 중에서도 중요도가 각각 다르기 때문에 우선순위가 서로 다르다. 일반 프로세스의 우선순위는 사용자가 조절할 수 있다.

CPU 집중 프로세스와 입출력 집중 프로세스

프로세스는 생성된 후, 준비, 실행, 대기 상태를 거쳐 완료된다. 준비 상태는 CPU를 할당받기 위해 기다리는 상태이므로 실제 작업이 일어나는 것은 실행 상태와 대기 상태이다. 이때 CPU를 할당받아 실행하는 작업을 CPU 버스트, 입출력 작업을 입출력 버스트라고 부른다.

CPU 집중 프로세스: 수학 연산과 같이 CPU를 많이 사용하는 프로세스, 즉 CPU 버스트가 많은 프로세스이다.

입출력 집중 프로세스: 저장 장치에서 데이터를 복사하는 일처럼 입출력을 많이 사용하는 프로세스다.

두 프로세스가 같이 있을 때는 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. 입출력 집중 프로세스가 실행 상태로 가면 입출력 요구에 의해 대기 상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있다. 만약 CPU 집중 프로세스가 먼저 실행 상태로 가게되면 타임아웃이 날 때까지 다른 프로세스가 실행되지 못할 것이다.

전면 프로세스와 후면 프로세스

전면 프로세스

• GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
• 현재 입력과 출력을 사용하는 프로세스
• 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 함

후면 프로세스

• 사용자와 상호작용이 없는 프로세스
• 사용자의 입력 없이 작동하기 때문에 일괄 작업 프로세스라고도 함
• 전면 프로세스의 우선순위가 후면 프로세스보다 높음

준비 상태의 다중 큐

프로세스는 저마다 중요도가 다르고 이는 프로세스 제어 블록에 표시된다. 그러나 매번 모든 PCB를 검색해서 우선순위가 높은 프로세스를 찾는 것은 번거로운 일이다.

우선순위별로 큐를 통해 정리되어 있으면 편리하게 찾을 수 있다.

고정 우선순위 방식 : 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식

변동 우선순위 방식 : 작업 중간에 변하는 방식, 구현이 어렵지만 시스템 효율성을 높일 수 있다.

대기 상태의 다중 큐

대기 상태에서도 다중 큐를 사용하는데, 시스템의 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다. 하드디스크, CD-ROM, LAN 등 기준에 맞게 큐에 저장된다.

다중 큐 비교

준비 상태의 큐와 대기 상태의 큐는 차이가 있다.

대기 큐는 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮길 수 있다. 많은 입출력 장치가 있기 때문에 입출력이 동시에 끝날 경우 여러개의 인터럽트가 한번에 처리된다. 이렇게 동시에 끝나는 인터럽트 처리를 위해 인터럽트 벡터를 사용한다.

스케줄링 알고리즘의 선택 기준

스케줄링 알고리즘의 평가 기준

CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율.
처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수.
대기 시간 : 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
응답 시간 : 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지의 시간
실행 시간 : 프로세스 작업이 시작된 후 종료되기까지의 시간
반환 시간 : 대기 시간을 포함하여 실행이 종료될 때까지의 시간

평균 대기 시간

모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값

FCFS 스케줄링

FCFS 알고리즘(선입 선출 알고리즘)은 비 선점 스케줄링 기법을 사용한다. 먼저 도착한 순서에 따라 처리하기 때문에 반응형 보다는 배치형(일괄처리) 시스템에 적합하다. 비 선점 스케줄링을 사용하고 있어서 오버헤드가 낮다는 장점을 가지고 있지만, 긴 수행시간을 가지고 있는 프로세스가 자원을 점유하고 있을 경우, 다른 프로세스들이 그만큼 대기시간을 갖게된다. 이러한 현상을 Convey Effect라고 부른다.

SJF 스케줄링

최단 작업 우선 스케줄링(Shortest Job First Scheduling)은 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식의 CPU 스케줄링 알고리즘으로 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘이다. 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 항상 양보되어 기아 상태가 발생할 수 있으며, 대기 상태에 있는 프로세스의 요구시간에 대한 정확한 자료를 얻기 어렵다는 문제점이 있다. 단기 스케줄링 보다는 장기 스케줄링에 유리하다.

HRN 스케줄링

HRN 스케줄링 기법은 SJF 스케줄링 기법의 약점인 긴 작업과 짧은 작업 사이의 불평등을 보완하기 위한 방법이다. HRN의 우선순위 선정 방법은
우선순위: (대기시간 + 서비스(실행)시간) / 서비스(실행)시간 = 시스템 응답시간
위 공식에서 시스템 응답시간이 커질수록 우선순위가 높아진다.

라운드 로빈 스케줄링

시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘

SRT 우선 스케줄링

SRT(Shortest Remaining Time) 스케줄링은 SJF(shortest job first) 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로 최소 잔류 시간 우선 스케줄링이라고 한다. 즉, SJF의 preemptive 버전이라고 할 수 있다.

우선순위 스케줄링

프로세스는 중요도에 따라 우선순위(priority)를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘이 우선순위 스케줄링이다.

고정 우선순위 알고리즘

한 번 우선순위를 부여받으면 종요될 때까지 우선순위가 고정된다. 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.

변동 우선순위 알고리즘

일정 시간마다 우선순위가 변한다. 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반형하여 효율적인 운영이 가능하다.

다단계 큐 스케줄링

다단계 큐(multilevel qeuue)스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 라운드 로빈 방식으로 운영되는 큐는 우선순위 따라 다단계로 나눠어 있어 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정된다. 우선순위는 고정형 우선순위를 사용하며 상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

다단계 피드백 큐 스케줄링

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)은 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완하는 방식이다. 다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링과 기본적인 형태가 같아 우선순위를 가진 여러 개의 큐를 사용한다. 하지만 다단계 큐 스케줄링의 경우 각 단계의 큐에 라운드 로빈 방식을 사용하고 우선순위에는 변화가 없는 데 반해, 다단계 피드백 큐 스케줄링의 경우 CPU를 사용하고 난 뒤 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스의 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 원래 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.

동기적 인터럽트와 비동기적 인터럽트

• 동기적인 인터럽트는 CPU의 제어 유닛이 명령어를 실행하는 과정에서 발생하는데, 제어 유닛은 명령어 실행을 마친 후에만 이를 발생시키기 때문에 동기적이라고 한다.

• 비동기적 인터럽트는 다른 하드웨어 장치가 CPU 클럭의 신호와 관계없이 아무 때나 발생한다.

인터럽트 처리 과정

1. 인터럽트가 발생하면 현재 실행 중인 프로세스는 일시 정지 상태가 되며, 재시작하기 위해 현재 프로세스 관련 정보를 임시로 저장
2. 인터럽트 컨트롤러가 실행되어 인터럽트의 처리 순서를 결정
3. 먼저 처리할 인터럽트가 결정되면 인터럽트 벡터에 등록된 인터럽트 핸들러가 실행
4. 인터럽트 벡터에 연결된 핸들러가 인터럽트 처리를 마치면 일시정지된 프로세스가 다 시 실행되거나 종료

이중 모드

사용자 모드사용자

• 애플리케이션 코드 실행
• 시스템에 제한된 접근만 허용, 하드웨어 직접 접근 불가
• 시스템 콜 수행 시 사용자 모드에서 커널 모드로 전환

커널 모드

• 커널 모드에서 OS는 모든 하드웨어 접근 및 제어 가능
• 시스템의 모든 메모리에 접근 및 모든 CPU 명령 실행 가능
• 일부 명령어는 커널 모드 특권(Privileged) 수준 코드 실행

이중 모드

다중 프로그래밍 환경에서 자원에 대한 접근을 사용자 모드(User Mode)와 커널 모드(Kernel Mode)로 분리하여 운영체제를 보호하는 기법

시스템 호출과 API

OS는 다양한 서비스들을 수행하기 위해 하드웨어를 직접적으로 관리한다. 이와 반면 응용 프로그램은 OS가 제공하는 인터페이스를 통해서만 자원을 사용할 수 있다. OS가 제공하는 이러한 인터페이스를 시스템 호출(System Call)이라 한다.

시스템 호출은 이러한 커널 영역의 기능을 사용자 모드가 사용 가능하게, 즉 프로세스가 하드웨어에 직접 접근해서 필요한 기능을 사용할 수 있게 해준다.

시스템 호출을 편하게 사용하기 위한 수단으로 API를 제공한다. API는 응용 프로그램을 쉽게 만들기 위한 도구로 덕분에 쉽게 프로그래밍이 가능해졌다.