CS_운영체제_CPU 스케줄링

99duuk 2024. 6. 15. 22:11

[고,중,저 수준 스케줄링]

고수준 스케줄링

목적: 시스템 내의 전체 작업 수를 조절한다.
기능: 프로세스의 활성화/비활성화를 결정해 프로세스 수를 조절한다. 어떤 작업을 시스템이 받아들일지, 거부할지 결정한다.

고수준 스케줄링은 프로세스가 시스템에 들어오거나 나가는 시점을 관리하며, 시스템의 과부하를 방지하기 위해 프로세스의 수를 조절한다. 이는 시스템 전체의 자원을 효율적으로 사용하도록 돕는다.

고수준 스케줄링은 일반적으로 비선점형 방식으로 작동하며, 시스템의 상태와 리소스 사용량을 고려해 새로운 작업을 받아들일지 결정한다.

중간 수준 스케줄링

목적: 활성화, 중지를 통해 활성화된 프로세스 수를 조절해 과부하를 막는다.
기능: 활성화된 프로세스 수를 조절함으로써 시스템이 효율적으로 운영되도록 보장한다. 필요에 따라 현재 실행 중인 프로세스를 일시 중지하거나 재개할 수 있다.

활성화: 대기 상태에 있는 프로세스를 실행 가능한 상태로 전환하여 시스템에 더 많은 프로세스를 활성화한다.

중지: 현재 실행 중이거나 준비 상태에 있는 프로세스를 대기 상태로 전환하여 시스템의 프로세스 수를 줄인다.

주로 프로세스를 일시 중지하거나 재개하는 방식으로 작동하여, 시스템이 효율적으로 운영되도록 보장한다.

(특정 시점에서 자원이 부족한 경우에 선점형 방식으로 프로세스를 관리하는 것과 유사한 효과를 가져온다.)

저수준 스케줄링

목적: 가장 작은 단위의 스케줄링이다.
기능: (CPU 스케줄러 입장에서) 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.

선점형 및 비선점형 방식 모두에서 작동할 수 있다.

선점형 저수준 스케줄링에서는 실행 중인 프로세스를 중단하고 더 높은 우선순위의 프로세스에 CPU를 할당할 수 있다.

반면, 비선점형 저수준 스케줄링에서는 프로세스가 자발적으로 CPU를 반환할 때까지 기다린다.

프로세스의 주요 상태

생성 (New): 프로세스가 생성되어 준비 상태로 전환되기 전의 초기 상태
준비 (Ready): CPU 할당을 기다리는 상태.
실행 (Running): CPU를 할당받아 실행 중인 상태.
대기 (Waiting): 입출력 작업 등으로 인해 기다리는 상태.
완료 (Terminated): 작업이 완료된 상태.

[상태 전이 과정]

상태 전이 과정

생성 -> 준비 (New -> Ready): 프로세스가 생성되고, 운영 체제에 의해 준비 상태로 이동
- 이벤트: 프로세스 생성
준비 -> 실행 (Ready -> Running): 스케줄러가 준비 상태의 프로세스 중 하나를 선택하여 CPU를 할당
- 이벤트: 스케줄러에 의해 CPU 할당
실행 -> 준비 (Running -> Ready): 실행 중인 프로세스가 타임퀀텀을 다 사용하거나, 다른 프로세스가 더 높은 우선순위를 가질 경우 준비 상태로 전환
- 이벤트: 타임퀀텀 만료, 우선순위가 높은 프로세스 도착
실행 -> 대기 (Running -> Waiting): 실행 중인 프로세스가 입출력 작업 등의 이벤트를 기다리기 위해 대기 상태로 전환
- 이벤트: 입출력 요청, 특정 이벤트 대기
대기 -> 준비 (Waiting -> Ready): 대기 상태에 있던 프로세스가 기다리던 이벤트가 완료되면 준비 상태로 전환
- 이벤트: 입출력 작업 완료, 이벤트 발생
실행 -> 완료 (Running -> Terminated): 실행 중인 프로세스가 모든 작업을 완료하면 종료 상태로 전환
- 이벤트: 프로세스 종료

scheduler

cpu가 놀지 않고 일을 할 수 있도록,
스케줄러는 프로세스를 선택하는 역할

실행중인 프로세스는 종료될 수도(terminated)

i/o 작업할 수도(waiting) 있고 ready 상태가 될 수도 있다.

ready Queue에는 실행을 기다리는 프로세스가 기다리고 있다.

∴ cpu scheduler : cpu에서 실행될 프로세스를 선택하는 역할

dispatcher

선택된 프로세스를 실제로 실행될 수 있도록 만드는 역할을 수행한다.

Context Switching을 수행한다. 이는 cpu와 관련된 민감한 작업이다. 커널 모드에서 실행된다.

ㄴ> cpu에서 실행되고 있던 프로세스를 스케줄러가 선택한 프로세스로 바꾸는 것

이어서 선택된 프로세스가 시작할 수 있도록 돕는 역할

새로운 프로세스가 실행되려면 유저 모드로 전환되어야 한다.

디스패처는 새롭게 선택된 프로세스에게 컨트롤을 넘겨주는 일도 한다.

또한 새롭게 선택된 프로세스가 어디서부터 실행되어야 할지.

실행되어야 할 적절한 위치로 선택된 프로세스를 이동 시키는 역할도 수행한다.

∴ dispatcher : 선택된 프로세스에게 cpu를 할당하는 역할

스케줄러와 디스패처는 문서에 따라 합쳐져 설명되기도 하고 구분되기도 한다.

이런 스케줄링은

모든 프로세스가 공평하게 작업하도록 하는 데 목적을 갖는다.

시스템 자원의 효율적 사용과 공정한 프로세스 실행을 통해 전체 시스템 성능을 최적화 하는 것이다.

이런 스케줄링은 선점형, 비선점형 스케줄링으로 나뉜다.

선점형 스케줄링 (빼앗기 가능)

cpu를 할당받아 실행중이더라도 OS가 cpu를 강제로 빼앗을 수 있는 스케줄링 방식

하나의 프로세스가 cpu를 독점할 수 없기 때문에 빠른 응답시간 요구하는 대화형 시스템이나 시분할 시스템에 적합하다.

예시 운영체제: Linux, Windows, macOS

비선점형 스케줄링 (빼앗기 불가능)

cpu를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

cpu 사용시간이 긴 프로세스가 cpu 점유하면,

cpu 사용시간이 짧은 여러 프로세스가 오래 기다리게 돼 전체 시스템의 효율이 떨어진다.

(과거 일괄 작업 시스템에서 사용하던 방식, MS-DOS, Windows 3.x, Classic Mac OS)

일반 프로세스와 커널 프로세스의 우선순위

셸과 커널의 위치 및 역할

셸 (Shell): 운영 체제와 사용자 사이에 위치한다. 사용자와 운영 체제 간의 인터페이스로 명령어를 해석하고 실행한다.
커널 (Kernel): 운영 체제 내부에 포함되어 있으며, 하드웨어와 소프트웨어 간의 중재자 역할을 한다.

일반 프로세스: 일반 사용자 애플리케이션이나 프로그램이 실행되는 프로세스를 말한다. (웹 브라우저, 문서 편집기, 게임 등)
커널 프로세스: 운영 체제의 커널이 실행하는 프로세스로, 시스템 자원 관리, 장치 드라이버, 파일 시스템 관리 등 중요한 작업을 수행한다.

커널 프로세스가 시스템의 안정성과 성능을 보장하기 위해 중요한 작업을 수행한다.

예를 들어, 메모리 관리, 프로세스 스케줄링, 인터럽트 처리 등은 즉각적으로 처리되어야 시스템이 원활하게 작동할 수 있다.

따라서 커널 프로세스는 높은 우선순위를 부여받아 필요한 경우 즉시 실행될 수 있다.

∴ 커널 프로세스는 중요한 시스템 기능을 수행하므로 일반 프로세스보다 우선순위가 높다.

프로세스는 생성된 후 준비, 실행, 대기 상태를 거쳐 완료된다. 프로세스는 작업 형태에 따라 두 가지로 나뉜다.

프로세스의 작업 형태

CPU 버스트 (CPU Burst): CPU를 집중적으로 사용하는 작업
입출력 버스트 (I/O Burst): 입출력 작업을 집중적으로 사용하는 작업

프로세스의 작업 형태는 프로세스의 상태 변화에 영향을 미친다.

CPU 집중 프로세스는 수학 연산, 게임, 영상 편집 등 CPU를 많이 사용하는 프로세스를 말한다. 이러한 프로세스는 주로 CPU 버스트 상태에 있으며, 실행 상태에서 긴 시간을 보낸다.
입출력 집중 프로세스는 저장 장치에서 데이터 복사 등 입출력을 많이 사용하는 프로세스를 말합니다. 이러한 프로세스는 입출력 버스트 상태에 있으며, 입출력 작업을 위해 대기 상태로 자주 전환된다.

이런 프로세스의 작업 형태 변화는 스케줄링 전략에 큰 영향을 미친다.

입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다. 이는 입출력 집중 프로세스가 입출력 작업으로 인해 대기 상태로 자주 전환되기 때문에, 다른 프로세스가 CPU를 사용할 수 있는 기회가 늘어나기 때문이다. 입출력 작업을 기다리는 동안, CPU 집중 프로세스가 실행될 수 있다.
반면에, CPU 집중 프로세스는 자신의 타임퀀텀을 다 쓸 때까지 CPU를 점유하므로, 다른 프로세스가 실행되지 못한다. 따라서, 입출력 집중 프로세스를 우선 실행하면 시스템 자원의 효율성이 높아진다.

또, 프로세스의 우선순위는 작업 형태뿐만 아니라 사용자와의 상호작용 여부에 따라 달라진다.

전면 프로세스는 GUI를 사용하는 맨 앞에 놓인 프로세스로, 사용자와 상호작용이 가능하다. 예를 들어, 웹 브라우저나 문서 편집기가 전면 프로세스다.
후면 프로세스는 사용자와 상호작용이 없는 프로세스로, 백그라운드에서 실행된다. 예를 들어, 데이터 백업이나 바이러스 스캔 작업이 후면 프로세스다.

우선순위 결정

전면 프로세스는 사용자의 요구에 즉각 반응해야 하기 때문에, 후면 프로세스보다 우선순위가 높다. 이는 사용자 경험을 향상시키고 시스템의 응답성을 높이기 위함이다.
따라서, 스케줄링 시 전면 프로세스와 입출력 집중 프로세스의 우선순위를 높게 설정하면 전체 시스템 성능이 최적화된다.

∴ 입출력 집중 프로세스를 먼저 실행하면, 이 프로세스가 대기 상태로 전환될 때

CPU 집중 프로세스가 CPU를 사용할 수 있게 되어 시스템의 효율성이 향상된다.

전면 프로세스의 우선순위를 높게 설정하면, 사용자 경험을 향상시키고 시스템의 응답성을 높일 수 있다.

따라서 스케줄링 시 입출력 집중 프로세스와 전면 프로세스의 우선순위를 높게 설정하면 전체 시스템 성능이 최적화된다.

스케줄링 알고리즘

스케줄링 알고리즘은 다양한 기준에 따라 프로세스의 실행 순서를 결정한다.

First-Come, First-Served (FCFS): 먼저 도착한 프로세스를 먼저 실행하는 방식이다. 간단하지만, 비효율적인 경우가 많다.
Shortest Job Next (SJN): 실행 시간이 가장 짧은 프로세스를 먼저 실행한다. 최적의 평균 대기 시간을 제공하지만, 실행 시간을 예측하기 어렵다.
Priority Scheduling: 우선순위가 높은 프로세스를 먼저 실행한다. 우선순위는 내부적으로 설정되거나 외부적으로 부여될 수 있다. 우선순위가 낮은 프로세스가 무한정 대기할 수 있는 문제점이 있다.
Round Robin (RR): 각 프로세스에 동일한 시간 할당량(타임퀀텀)을 부여하여 순환하면서 실행한다. 시분할 시스템에 적합하며, 공정성을 보장한다.
Multilevel Queue Scheduling: 프로세스를 여러 개의 큐로 분류하여 각 큐에 다른 스케줄링 알고리즘을 적용한다.
Multilevel Feedback Queue: 프로세스의 실행 시간과 입출력 패턴에 따라 큐를 이동시켜가며 실행한다. 동적인 우선순위 조정이 가능하다.

[Multilevel Queue Scheduling, Multilevel Feedback Queue 예]

다단계 큐 (Multi-Level Queue)

비유: 공항의 체크인 카운터

공항의 체크인 카운터에는 퍼스트 클래스, 비즈니스 클래스, 이코노미 클래스 세 가지 줄이 있다.
퍼스트 클래스 승객은 가장 빨리 처리되고, 그 다음 비즈니스 클래스, 마지막으로 이코노미 클래스가 처리된다.
각 클래스마다 고정된 우선 순위가 있어서 이코노미 클래스 승객은 아무리 오래 기다려도 퍼스트 클래스 승객보다 먼저 처리되지 않는다.

이처럼 다단계 큐에서는 프로세스들이 우선 순위에 따라 서로 다른 큐에 들어가고, 각 큐는 독립적으로 작동한다. 높은 우선 순위의 큐가 비어 있을 때만 낮은 우선 순위의 큐가 처리된다.

다단계 피드백 큐 (Multi-Level Feedback Queue)

비유: 공항의 체크인 카운터2

공항의 체크인 카운터에는 퍼스트 클래스, 비즈니스 클래스, 이코노미 클래스 세 가지 줄이 있습니다. 각 클래스마다 고정된 우선 순위가 있지만, 다단계 피드백 큐에서는 상황에 따라 승객이 줄을 이동할 수 있습니다.

만약 퍼스트 클래스 승객이 체크인 데스크에 도착하지 않았거나, 자격 요건을 만족하지 못하면, 해당 승객은 비즈니스 클래스 줄로 내려갑니다.
마찬가지로 비즈니스 클래스 승객이 체크인 데스크에 도착하지 않았거나, 자격 요건을 만족하지 못하면, 해당 승객은 이코노미 클래스 줄로 내려갑니다.
반대로, 이코노미 클래스 줄에서 매우 오랜 시간 동안 기다린 승객은 비즈니스 클래스 줄로 승급될 수 있습니다.
그리고 비즈니스 클래스 줄에서 오랜 시간 기다린 승객은 퍼스트 클래스 줄로 승급될 수 있습니다.

이처럼 다단계 피드백 큐는 승객(프로세스)이 각 줄(큐)에서 보내는 시간을 기반으로 줄을 이동하게 합니다. 오래 기다린 승객은 높은 우선 순위의 줄로 올라가게 되고, 자격을 만족하지 못하면 낮은 우선 순위의 줄로 내려갑니다. 이를 통해 모든 승객이 공정하게 체크인할 수 있도록 조정합니다.

스케줄링 기준 및 평가

스케줄링 알고리즘이 얼마나 효율적이고 공정하게 작동하는지 판단하는 데 사용된다.

CPU 이용률 (CPU Utilization): CPU가 유휴 상태 없이 바쁘게 일하는 비율
처리량 (Throughput): 단위 시간당 완료되는 프로세스의 수
대기 시간 (Waiting Time): 프로세스가 준비 큐에서 기다린 총 시간
응답 시간 (Response Time): 프로세스가 처음 요청을 제출한 후 처음 응답을 받을 때까지의 시간
반환 시간 (Turnaround Time): 프로세스가 시작해서 완료될 때까지 걸린 총 시간

실제 운영 체제에서의 스케줄링 기법

현대 운영 체제는 다양한 스케줄링 알고리즘을 결합하여 사용한다. 각 운영 체제는 고유한 방식으로 스케줄링을 최적화해 시스템 성능을 극대화한다.

Linux: 완전 공정 스케줄러 (Completely Fair Scheduler, CFS)를 사용한다. 이 스케줄러는 각 프로세스가 공평하게 CPU 시간을 받을 수 있도록 설계되었다.
Windows: 우선순위 기반 스케줄링을 사용하며, 정적 우선순위와 동적 우선순위를 결합하여 프로세스를 관리한다.
macOS: Mach 커널 기반으로, 다양한 우선순위 수준과 실시간 스케줄링 기능을 제공한다.

스케줄링의 추가 고려 사항

해당 요소들은 특정 환경에서 스케줄링이 효과적으로 작동하도록 보장한다.

실시간 스케줄링: 실시간 시스템에서는 응답 시간의 예측 가능성이 중요하다. 하드 실시간 시스템에서는 엄격한 시간 제약을 준수해야 하며, 소프트 실시간 시스템에서는 시간이 중요하지만 유연성이 허용된다.
멀티코어 스케줄링: 멀티코어 시스템에서는 여러 CPU 코어 간의 작업 분배가 중요하다. 로드 밸런싱과 코어 간 상호작용을 최적화해야 한다.
스레드 스케줄링: 프로세스 내부의 여러 스레드 간의 스케줄링도 중요하다. 유저 스레드와 커널 스레드 간의 상호작용과 우선순위 조정이 필요하다.