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

CPU 스케줄링 유형

다음은 두 가지 종류의 스케줄링 방법입니다.

선제적 스케줄링

선점형 스케줄링에서는 작업이 대부분 우선순위에 따라 할당됩니다. 우선순위가 낮은 작업이 계속 실행 중이더라도 우선순위가 낮은 작업을 실행하기 전에 우선순위가 높은 작업을 실행하는 것이 중요한 경우가 있습니다. 우선순위가 낮은 작업은 일정 시간 동안 유지되었다가 우선순위가 높은 작업이 실행을 마치면 다시 시작됩니다.

비선점형 스케줄링

이러한 유형의 스케줄링 방법에서는 CPU가 특정 프로세스에 할당되었습니다. CPU를 계속 사용하는 프로세스는 컨텍스트를 전환하거나 종료하여 CPU를 해제합니다. 다양한 하드웨어 플랫폼에 사용할 수 있는 유일한 방법입니다. 선점형 스케줄링과 같은 특별한 하드웨어(예: 타이머)가 필요하지 않기 때문입니다.

스케줄링이 선점형인가요, 아니면 비선점형인가요?

스케줄링이 선점형인지 비선점형인지 확인하려면 다음 네 가지 매개변수를 고려하세요.

1. 프로세스가 실행 중 상태에서 대기 상태로 전환됩니다.
2. 특정 프로세스가 실행 상태에서 준비 상태로 전환됩니다.
3. 특정 프로세스가 대기 상태에서 준비 상태로 전환됩니다.
4. 프로세스가 실행을 마치고 종료되었습니다.

조건 1과 4만 적용되며 스케줄링을 비선점형이라고 합니다.

다른 모든 스케줄링은 선제적입니다.

중요한 CPU 스케줄링 용어

• 버스트 시간/실행 시간: 프로세스가 실행을 완료하는 데 필요한 시간입니다. 실행시간이라고도 합니다.
• 도착 시간: 프로세스가 준비 상태에 들어갈 때
• 종료 시간: 프로세스가 완료되고 시스템에서 종료될 때
• 다중 프로그래밍: 메모리에 동시에 존재할 수 있는 다수의 프로그램.
• 작업: 어떤 종류의 사용자 상호 작용도 없는 일종의 프로그램입니다.
• 사용자 : 사용자 상호작용이 있는 일종의 프로그램이다.
• 프로세스 : 작업과 사용자 모두에게 사용되는 참조입니다.
• CPU/IO 버스트 주기: CPU와 I/O 활동을 번갈아 수행하는 프로세스 실행의 특징을 나타냅니다. CPU 시간은 일반적으로 I/O 시간보다 짧습니다.

CPU 스케줄링 기준

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

극대화하다

CPU 사용률 :CPU 사용률은 운영 체제가 CPU를 가능한 한 최대한 바쁘게 유지해야 하는 주요 작업입니다. 범위는 0~100%입니다. 그러나 RTOS의 경우 저수준 시스템의 경우 40%, 고수준 시스템의 경우 90%입니다.

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

최소화

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

응답 시간: 첫 번째 응답이 생성될 때까지 요청이 제출된 시간입니다.

처리 시간: 처리 시간은 특정 프로세스를 실행하는 데 걸리는 시간입니다. 메모리에 들어가기 위해 대기하고, 큐에서 대기하고, CPU에서 실행하는 데 소요된 총 시간을 계산한 것입니다. 프로세스 제출 시간부터 완료 시간까지의 기간이 처리 시간입니다.

인터벌 타이머

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

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

디스패처란 무엇입니까?

프로세스에 CPU 제어권을 제공하는 모듈입니다. Dispatcher는 모든 컨텍스트 전환에서 실행될 수 있도록 빨라야 합니다. 디스패치 대기 시간은 CPU 스케줄러가 한 프로세스를 중지하고 다른 프로세스를 시작하는 데 필요한 시간입니다.

Dispatcher가 수행하는 기능:

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

CPU 스케줄링 알고리즘의 종류

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

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

선착순

선착순 서비스는 FCFS의 전체 형태입니다. 가장 쉽고 간단한 CPU 스케줄링 알고리즘입니다. 이러한 유형의 알고리즘에서는 CPU를 요청하는 프로세스가 먼저 CPU 할당을 받습니다. 이 스케줄링 방법은 FIFO 대기열로 관리할 수 있습니다.

프로세스가 준비 대기열에 들어가면 해당 PCB(Process Control Block)가 대기열의 꼬리와 연결됩니다. 따라서 CPU가 사용 가능해지면 대기열 시작 부분에 있는 프로세스에 CPU를 할당해야 합니다.

FCFS 방식의 특징

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

가장 짧은 남은 시간

SRT의 전체 형태는 Shortest 남은 시간입니다. SJF 선점형 스케줄링이라고도 합니다. 이 방법에서는 프로세스가 완료에 가장 가까운 작업에 할당됩니다. 이 방법은 새로운 준비 상태 프로세스가 이전 프로세스의 완료를 보류하는 것을 방지합니다.

SRT 스케줄링 방식의 특징

• 이 방법은 주로 짧은 작업을 우선적으로 처리해야 하는 배치 환경에 적용됩니다.
• 이는 필요한 CPU 시간을 알 수 없는 공유 시스템에서 구현하기에는 이상적인 방법이 아닙니다.
• 각 프로세스와 다음 CPU 버스트의 길이를 연관시킵니다. 그래서 운영 체제는 이 길이를 사용하여 가능한 가장 짧은 시간으로 프로세스를 스케줄링하는 데 도움이 됩니다.

우선순위 기반 스케줄링

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

우선순위 스케줄링은 OS가 우선순위 할당을 포함하도록 도와줍니다. 우선순위가 높은 프로세스가 먼저 수행되어야 하며, 우선순위가 동일한 작업은 라운드 로빈 또는 FCFS 기반으로 수행됩니다. 우선순위는 메모리 요구사항, 시간 요구사항 등에 따라 결정될 수 있습니다.

라운드 로빈 스케줄링

라운드 로빈은 가장 오래되고 가장 간단한 스케줄링 알고리즘입니다. 이 알고리즘의 이름은 라운드 로빈 원리에서 유래되었는데, 각 사람이 차례로 무언가를 동등하게 나눠 갖는 것입니다. 주로 멀티태스킹 스케줄링 알고리즘에 사용됩니다. 이 알고리즘 방법은 프로세스의 기아 없는 실행에 도움이 됩니다.

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

• 라운드 로빈은 시계 구동 방식의 하이브리드 모델입니다.
• 처리할 특정 작업에 할당되는 시간 조각은 최소여야 합니다. 그러나 프로세스에 따라 다를 수 있습니다.
• 특정 시간 내에 이벤트에 대응하는 실시간 시스템입니다.

최단 직업 우선

SJF는 (Shortest job first)의 완전한 형태로 실행 시간이 가장 짧은 프로세스를 선택하여 다음에 실행하는 스케줄링 알고리즘입니다. 이 스케줄링 방법은 선점형이거나 비선점형일 수 있습니다. 실행을 기다리는 다른 프로세스의 평균 대기 시간을 크게 줄입니다.

SJF 스케줄링의 특징

• 완료하는 데 걸리는 시간 단위로 각 작업과 연결됩니다.
• 이 방법에서는 CPU를 사용할 수 있을 때 완료 시간이 가장 짧은 다음 프로세스나 작업이 먼저 실행됩니다.
• 비선점형 정책으로 구현됩니다.
• 이 알고리즘 방법은 작업이 완료될 때까지 기다리는 것이 중요하지 않은 배치 유형 처리에 유용합니다.
• 먼저 실행해야 하는 더 짧은 작업을 제공하여 작업 출력을 향상시키며, 대부분 처리 시간이 더 짧습니다.

다중 레벨 대기열 스케줄링

이 알고리즘은 준비 대기열을 다양한 개별 대기열로 분리합니다. 이 방법에서는 프로세스 우선순위, 메모리 크기 등과 같은 프로세스의 특정 속성을 기반으로 프로세스가 대기열에 할당됩니다.

그러나 이것은 작업을 스케줄링하기 위해 다른 유형의 알고리즘을 사용해야 하므로 독립적인 스케줄링 OS 알고리즘이 아닙니다.

다중 레벨 대기열 스케줄링의 특징

• 일부 특성을 가진 프로세스에 대해서는 여러 대기열을 유지해야 합니다.
• 각 대기열에는 별도의 스케줄링 알고리즘이 있을 수 있습니다.
• 각 대기열에 우선순위가 부여됩니다.

스케줄링 알고리즘의 목적

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

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

제품 개요

• CPU 스케줄링은 다른 프로세스가 보류 중인 동안 실행을 위해 CPU를 소유할 프로세스를 결정하는 프로세스입니다.
• 선점형 스케줄링에서는 작업이 대부분 우선순위에 따라 할당됩니다.
• 비선점형 스케줄링 방식에서는 특정 프로세스에 CPU를 할당합니다.
• 버스트 시간은 프로세스가 실행을 완료하는 데 필요한 시간입니다. 실행시간이라고도 합니다.
• CPU 사용률은 운영 체제가 CPU를 가능한 한 최대한 바쁘게 유지해야 하는 주요 작업입니다.
• 단위 시간당 실행을 완료하는 프로세스 수는 처리량으로 알려져 있습니다.
• 대기 시간은 특정 프로세스가 준비 대기열에서 기다려야 하는 시간입니다.
• 첫 번째 응답이 생성될 때까지 요청이 제출된 시간입니다.
• 처리 시간은 특정 프로세스를 실행하는 데 걸리는 시간입니다.
• 타이머 중단은 선점과 밀접한 관련이 있는 방법이다.
• 디스패처는 프로세스에 CPU 제어권을 제공하는 모듈입니다.
• 2가지 유형의 프로세스 스케줄링 알고리즘은 다음과 같습니다. 선착순 스케줄링(FCFS), 최단 작업 우선 스케줄링(SJF) 스케줄링, 최단 남은 시간 스케줄링, 우선순위 스케줄링, 라운드 로빈 스케줄링, 다중 레벨 큐 스케줄링.
• . 선착순 방식, CPU를 요청한 프로세스가 먼저 CPU 할당을 얻습니다.
• 가장 짧은 남은 시간 동안 프로세스는 완료에 가장 가까운 작업에 할당됩니다.
• 우선순위 스케줄링에서는 스케줄러가 우선순위에 따라 작업할 작업을 선택합니다.
• 라운드 로빈 스케줄링 각 사람이 차례로 무언가를 동등한 몫으로 얻는 원칙에 따라 작동합니다.
• 가장 짧은 작업을 먼저 선택하고 다음으로 실행하려면 가장 짧은 실행 시간을 선택해야 합니다.
• 다중 레벨 스케줄링 방법은 준비 대기열을 다양한 개별 대기열로 분리합니다. 이 방법에서는 특정 속성을 기반으로 프로세스가 대기열에 할당됩니다.
• CPU는 효율성을 높이기 위해 스케줄링을 사용합니다.