CPU 스케줄링 Algorithms in Opera팅 시스템

⚡ 스마트 요약

CPU 스케줄링은 운영 체제가 다음에 실행할 준비된 프로세스를 결정합니다.ping 프로세서가 바쁘게 작동하고 있으며 선착순(First Come First Serve), 최단 작업 우선(Shortest Job First), 우선순위(Priority), 라운드 로빈(Round Robin)과 같은 알고리즘을 통해 성능이 향상되고 있습니다.

🔄 정의: CPU 스케줄링은 CPU가 유휴 상태가 될 때마다 준비 큐에서 프로세스를 선택합니다.
⚖️ 유형 : 선점형 스케줄링은 실행 중인 작업을 중단할 수 있는 반면, 비선점형 스케줄링은 작업이 CPU를 해제할 때까지 기다립니다.
📊 기준 : 우수한 알고리즘은 대기 시간, 응답 시간 및 처리 시간을 최소화하면서 CPU 활용률과 처리량을 극대화합니다.
🧮 Algorithms: FCFS, SJF, 최단 잔여 시간, 우선순위, 라운드 로빈 및 다단계 큐는 각각 다른 작업 부하에 적합합니다.
🚦 디스패처 : 디스패처는 선택된 프로세스에 CPU 제어권을 넘겨주는 컨텍스트 스위치를 수행합니다.
🤖 AI 관점: 머신 러닝은 스케줄링 결정을 최적화하고, Copilot은 스케줄러 알고리즘의 코딩 및 테스트를 지원합니다.

CPU 스케줄링이란 무엇입니까?

CPU 스케줄링 CPU 스케줄링은 다른 프로세스가 대기 중일 때 어떤 프로세스가 CPU를 실행에 사용할지 결정하는 과정입니다. CPU 스케줄링의 주요 역할은 CPU가 유휴 상태일 때마다 운영체제가 준비 큐에 있는 프로세스 중 적어도 하나를 선택하여 실행하도록 하는 것입니다. 이러한 선택 과정은 CPU 스케줄러가 수행하며, 스케줄러는 메모리에 있는 실행 준비 상태의 프로세스 중 하나를 선택합니다.

CPU 스케줄링 유형

스케줄링 방법에는 두 가지 종류가 있습니다.

선제적 스케줄링

선점형 스케줄링에서는 대부분 작업에 우선순위가 부여됩니다. 때로는 우선순위가 낮은 작업이 아직 실행 중이더라도 우선순위가 높은 작업을 먼저 실행하는 것이 중요할 수 있습니다. 이 경우 우선순위가 낮은 작업은 잠시 대기하다가 우선순위가 높은 작업이 완료되면 다시 실행을 시작합니다.

비선점형 스케줄링

이러한 스케줄링 방식에서는 CPU가 특정 프로세스에 할당됩니다. CPU를 계속 사용하고 있는 프로세스는 컨텍스트를 전환하거나 종료함으로써 CPU를 해제합니다. 이 방식은 선점형 스케줄링처럼 타이머와 같은 특수 하드웨어가 필요하지 않기 때문에 다양한 하드웨어 플랫폼에서 사용할 수 있는 유일한 방식입니다.

스케줄링이 선제적인가요, 아니면 비선제적인가요?

스케줄링이 선점형인지 비선점형인지 판단하려면 다음 네 가지 매개변수를 고려하십시오.

프로세스가 실행 중 상태에서 대기 상태로 전환됩니다.
특정 프로세스가 실행 상태에서 준비 상태로 전환됩니다.
특정 프로세스가 대기 상태에서 준비 상태로 전환됩니다.
프로세스가 실행을 완료하고 종료됩니다.

조건 1과 4만 충족되는 경우, 해당 스케줄링을 비선점형 스케줄링이라고 합니다. 그 외의 모든 스케줄링 상황은 선점형 스케줄링입니다.

주요 CPU 스케줄링 용어

버스트 시간/실행 시간: 프로세스가 실행을 완료하는 데 필요한 시간입니다. 실행 시간이라고도 합니다.
도착 시간: 프로세스가 준비 상태에 진입하는 시점.
종료 시간: 프로세스가 완료되어 시스템을 종료하는 시간.
다중 프로그래밍: 메모리에 동시에 실행될 수 있는 프로그램의 수.
작업: 사용자 상호작용이 전혀 없는 프로그램 유형.
사용자 : 사용자 상호작용이 있는 프로그램의 일종.
프로세스 : 작업과 사용자 모두에 사용되는 참조입니다.
CPU/IO 버스트 주기: 프로세스 실행의 특징을 나타내며, CPU 활동과 I/O 활동이 번갈아 발생합니다. 일반적으로 CPU 시간은 I/O 시간보다 짧습니다.

CPU 스케줄링 기준

CPU 스케줄링 알고리즘은 다음을 최대화하고 최소화하려고 합니다.

극대화하다

CPU 사용률 : CPU 사용률은 운영 체제가 CPU를 최대한 바쁘게 유지해야 하는 핵심적인 요소입니다. CPU 사용률은 0%에서 100%까지의 범위를 가질 수 있습니다. 특히 실시간 운영 체제(RTOS)의 경우, 저수준 시스템의 경우 40%에서 고수준 시스템의 경우 90%까지 다양하게 나타날 수 있습니다.

처리량 : 단위 시간당 실행을 완료하는 프로세스 수를 처리량이라고 합니다. 따라서 CPU가 프로세스를 실행하느라 바쁠 때는 작업이 진행되고 있으며, 단위 시간당 완료되는 작업량을 처리량이라고 합니다.

최소화

대기 시간: 대기 시간은 특정 프로세스가 준비 대기열에서 기다려야 하는 시간입니다.

응답 시간: 이는 요청이 제출된 시점부터 첫 번째 응답이 나올 때까지의 시간입니다.

처리 시간: 처리 시간(Turnaround time)은 특정 프로세스를 실행하는 데 걸리는 시간입니다. 메모리에 로드되기까지 대기하는 시간, 대기열에서 기다리는 시간, CPU에서 실행되는 시간을 모두 합한 시간입니다. 프로세스 제출 시점부터 완료 시점까지의 기간이 처리 시간입니다.

인터벌 타이머

타이머 중단은 선점과 밀접한 관련이 있는 방법이다. 특정 프로세스가 CPU 할당을 받으면 타이머가 지정된 간격으로 설정될 수 있습니다. 타이머 중단과 선점 모두 CPU 버스트가 완료되기 전에 프로세스가 CPU를 반환하도록 강제합니다.

대부분의 다중 프로그램 운영 체제는 프로세스가 시스템을 영원히 점유하는 것을 방지하기 위해 일종의 타이머를 사용합니다.

디스패처란 무엇입니까?

디스패처는 프로세스에 CPU 제어권을 제공하는 모듈입니다. 디스패처는 컨텍스트 스위치가 발생할 때마다 실행될 수 있도록 빨라야 합니다. 디스패치 지연 시간은 CPU 스케줄러가 하나의 프로세스를 중지하고 다른 프로세스를 시작하는 데 필요한 시간입니다.

디스패처가 수행하는 기능:

컨텍스트 전환.
사용자 모드로 전환합니다.
새로 로드된 프로그램에서 올바른 위치로 이동합니다.

CPU 스케줄링 유형 Algorithms

크게 XNUMX가지 종류가 있는데 프로세스 스케줄링 알고리즘:

선착순(FCFS)
최단 작업 우선(SJF) 스케줄링
가장 짧은 남은 시간
우선순위 스케줄링
라운드 로빈 스케줄링
다단계 대기열 스케줄링

예약 Algorithms

선착순

FCFS는 다음을 의미합니다. 선착순이는 가장 쉽고 간단한 CPU 스케줄링 알고리즘입니다. 이 알고리즘에서는 CPU를 요청한 프로세스가 먼저 CPU를 할당받습니다. 이 스케줄링 방식은 FIFO 큐를 사용하여 관리할 수 있습니다.

프로세스가 준비 대기열에 들어가면 해당 프로세스의 PCB(프로세스 제어 블록)가 대기열의 맨 뒤에 연결됩니다. 따라서 CPU가 사용 가능해지면 대기열의 맨 앞에 있는 프로세스에 할당되어야 합니다.

FCFS 방법의 특징

이는 비선점형 스케줄링 알고리즘입니다.
작업은 항상 선착순으로 실행됩니다.
구현하고 사용하기 쉽습니다.
그러나 이 방법은 성능이 좋지 않으며 일반적인 대기 시간이 상당히 길다.

가장 짧은 남은 시간

SRT의 정식 명칭은 최단 잔여 시간(Shortest Remaining Time)입니다. SJF 선점형 스케줄링이라고도 합니다. 이 방식에서는 프로세스가 완료가 가장 가까운 작업에 할당됩니다. 이를 통해 새로 준비된 프로세스가 오래된 프로세스의 완료를 지연시키는 것을 방지할 수 있습니다.

SRT 스케줄링 방법의 특징

이 방법은 주로 작업 속도가 빠른 배치 환경에 적용되며, 특히 작업 속도가 빠른 경우에 우선적으로 처리됩니다.
이는 필요한 CPU 시간을 알 수 없는 공유 시스템에서 구현하기에 이상적인 방법은 아닙니다.
각 프로세스는 다음 CPU 버스트의 길이와 연결되어 있으므로 운영 체제는 이러한 길이를 사용하여 가능한 한 가장 짧은 시간 안에 프로세스를 스케줄링합니다.

우선순위 기반 스케줄링

우선순위 스케줄링 우선순위에 따라 프로세스를 예약하는 방법입니다. 이 방법에서 스케줄러는 우선순위에 따라 작업할 작업을 선택합니다.

우선순위 스케줄링은 운영체제가 우선순위를 할당하는 데에도 도움이 됩니다. 우선순위가 높은 프로세스가 먼저 실행되고, 우선순위가 같은 작업은 라운드 로빈 방식 또는 선착순(FCFS)으로 실행됩니다. 우선순위는 메모리 요구 사항, 시간 요구 사항 및 기타 요소를 기반으로 결정될 수 있습니다.

라운드 로빈 스케줄링

라운드 로빈 이 알고리즘은 가장 오래되고 간단한 스케줄링 알고리즘 중 하나입니다. 알고리즘 이름은 각 사람이 돌아가며 동일한 몫을 받는 라운드 로빈 원칙에서 유래했습니다. 주로 멀티태스킹 시스템의 스케줄링에 사용되며, 프로세스의 기아 현상 없는 실행을 가능하게 합니다.

라운드 로빈 스케줄링의 특성

라운드 로빈은 클럭 속도에 따라 작동하는 하이브리드 모델입니다.
특정 작업을 처리하는 데 할당되는 시간은 최소한이어야 합니다. 하지만 프로세스에 따라 다를 수 있습니다.
이는 특정 시간 제한 내에 각 프로세스에 응답하는 시분할 시스템처럼 작동합니다.

최단 직업 우선

SJF(Shortest Job First)는 실행 시간이 가장 짧은 프로세스를 다음 실행 대상으로 선택하는 스케줄링 알고리즘입니다. 이 스케줄링 방식은 선점형 또는 비선점형으로 구현될 수 있으며, 실행을 기다리는 다른 프로세스의 평균 대기 시간을 크게 줄여줍니다.

SJF 스케줄링의 특징

각 작업에는 완료하는 데 필요한 시간 단위가 연결되어 있습니다.
이 방식에서는 CPU를 사용할 수 있을 때 완료 시간이 가장 짧은 다음 프로세스 또는 작업부터 먼저 실행됩니다.
이는 비선점형 정책으로 구현됩니다.
이 알고리즘은 작업 완료를 기다리는 것이 중요하지 않은 배치 처리 방식에 유용합니다.
이는 처리 시간이 짧은 작업을 먼저 실행함으로써 작업 생산성을 향상시킵니다.

다중 레벨 대기열 스케줄링

이 알고리즘은 준비 큐를 여러 개의 개별 큐로 분리합니다. 이 방법에서는 프로세스 우선순위, 메모리 크기 등과 같은 프로세스의 특정 속성을 기준으로 프로세스를 각 큐에 할당합니다.

하지만 이는 독립적인 스케줄링 알고리즘이 아니며, 작업을 스케줄링하기 위해 다른 유형의 알고리즘을 사용해야 합니다.

다단계 큐 스케줄링의 특징

공통된 특성을 가진 프로세스에 대해서는 여러 개의 큐를 유지해야 합니다.
각 대기열은 고유한 스케줄링 알고리즘을 가질 수 있습니다.
각 대기열에는 우선순위가 할당됩니다.

스케줄링 알고리즘의 목적

스케줄링 알고리즘을 사용하는 이유는 다음과 같습니다.

CPU는 효율성을 높이기 위해 스케줄링을 사용합니다.
이는 경쟁하는 프로세스 간에 리소스를 할당하는 데 도움이 됩니다.
멀티프로그래밍을 통해 CPU 활용도를 극대화할 수 있습니다.
실행될 프로세스들은 준비 대기열에 보관됩니다.

자주 묻는 질문

최적의 알고리즘은 하나로 정해져 있지 않습니다. 최단 작업 우선(Shortest Job First) 방식은 평균 대기 시간이 가장 짧고 최적임이 입증되었지만, 작업 처리 시간(burst time)을 정확히 알아야 하고 작업 처리 시간이 긴 작업은 처리하지 못할 수 있습니다. 라운드 로빈(Round Robin) 방식은 시분할 시스템에서 더 공정한 알고리즘입니다.

기아 현상은 우선순위가 높거나 실행 시간이 짧은 작업이 CPU를 먼저 차지하는 바람에 프로세스가 무한정 대기하게 되는 현상입니다. 이는 우선순위 우선(Priority First) 및 최단 작업 우선(Shortest Job First) 스케줄링 방식에서 흔히 발생하며, 실행 시간이 길거나 우선순위가 낮은 프로세스는 아예 실행되지 못할 수 있습니다.

에이징(Aging)은 오랜 시간 대기한 프로세스의 우선순위를 점진적으로 높이는 기법입니다. 이를 통해 우선순위 기반 스케줄링에서 기아 현상(starvation)을 방지할 수 있는데, 우선순위가 낮은 프로세스라도 결국 실행될 수 있을 만큼 충분히 높은 우선순위를 얻게 되기 때문입니다.

컨텍스트 스위칭은 현재 프로세스의 상태를 저장하고 다른 프로세스의 상태를 해당 프로세스 블록(PCB)에서 불러와 나중에 실행을 재개할 수 있도록 합니다. 이는 프로세스 간 전환 시마다 디스패처가 처리하는 순수한 스케줄링 오버헤드입니다.

장기(작업) 스케줄러는 준비 큐에 들어가는 프로세스 수를 제어하고 멀티프로그래밍 정도를 설정합니다. 단기(CPU) 스케줄러는 준비된 프로세스 중 다음에 실행될 프로세스를 선택하며 훨씬 더 자주 실행됩니다.

리눅스는 커널 6.6에서 CFS(Completely Fair Scheduler)를 대체한 EEVDF 스케줄러를 사용합니다. Windows 각 우선순위 레벨 내에서 라운드 로빈 시간 분할을 사용하는 선점형 우선순위 기반 스케줄러를 사용합니다.

머신러닝 모델은 프로세스 급증 시간을 예측하고 대기 시간과 에너지 사용량을 줄이기 위해 스케줄링 정책을 조정하거나 선택합니다. 이러한 AI 기반 스케줄러는 데이터 센터, 클라우드 서버 및 실시간 시스템에 적용하기 위한 연구가 진행되고 있습니다.

네. GitHub Copilot은 FCFS, SJF, 우선순위, 라운드 로빈 방식의 코드 생성은 물론 간트 차트 및 대기 시간 계산도 지원합니다. 하지만 출력 결과를 신뢰하기 전에 예외 상황, 동점 처리 규칙, 평균 시간 계산 공식 등을 반드시 검증해야 합니다.