Processor Scheduling

태그(공백으로 구분): 프로세스 스케줄링 스케줄링 알고리즘 운영 체제

기본 개념

정의
: 운영 체제는 여러 프로세스가 있을 때(또는 여러 프로세스가 발행될 때) 시스템의 제한된 리소스를 관리합니다. 요청)이 이러한 자원을 사용하려면 자원의 제한된 특성으로 인해 특정 원칙에 따라 자원을 점유하기 위한 프로세스(요청)를 선택해야 하며 이를 스케줄링이라고 합니다.

리소스 사용자 수를 제어하고 리소스 사용자 권한을 선택하여 리소스를 점유하거나 리소스를 점유하는 것이 목적입니다. 세 가지 수준의 프로세서 스케줄링:

고수준 스케줄링: 작업 스케줄링, 스케줄링 개체는 작업입니다.
중간 수준 스케줄링: 메모리 스케줄링(기본적으로 메모리 스왑 기능)
낮음- 레벨 스케줄링: 프로세스 스케줄링, 스케줄링 객체는 프로세스 또는 커널 수준 스레드입니다

작업 스케줄링 알고리즘은 프로세스 스케줄링에도 적용 가능합니다

서비스 시간(T_s): 시스템이 걸리는 시간 작업 또는 프로세스에 대한 서비스 제공
처리 시간(T_i) : 작업 또는 프로세스가 시스템에 제출된 시점부터 작업 또는 프로세스가 완료될 때까지의 시간 간격
일반적으로 다음이 포함됩니다.

작업 시간.
프로세스가 준비 대기열에서 프로세스 예약을 기다리는 시간
프로세스가 CPU에서 실행되는 시간
프로세스가 I/O 작업이 완료될 때까지 기다리는 시간

평균 처리 시간:
[T = frac{sum_{i=1}^n T_i}{n}]
가중 처리 시간 포함: 작업 처리 시간과 서비스에 소요되는 시간의 비율 it
[W_i = frac{T_i}{T_s}]
평균 가중 처리 시간:
[W = frac{sum_{i=1 }^n frac{T_i}{T_s}}{n}]

스케줄링 타이밍, 전환 및 프로세스

프로세스 스케줄링 및 전환 프로그램은 운영 체제 커널 프로그램입니다. 스케줄링을 요청하는 이벤트가 발생하면 프로세스 스케줄러가 실행될 수 있으며, 새로운 Ready 프로세스가 스케줄링되면 프로세스 간 전환이 수행됩니다. 이론적으로는 이 세 가지가 순차적으로 실행되어야 하지만 실제 설계에서는 운영체제 커널 프로그램이 실행 중일 때 어느 시점에서 프로세스 스케줄링을 유발하는 요인이 발생하면 스케줄링과 전환이 즉시 불가능할 수도 있다.

현대 운영 체제에서는 다음과 같은 상황에서는 프로세스 스케줄링 및 전환을 수행할 수 없습니다.

인터럽트를 처리하는 과정에서: 인터럽트 처리 프로세스가 복잡하고 구현 시 프로세스 전환을 달성하기 어렵고 인터럽트가 발생합니다. 처리는 시스템 작업의 일부이며 논리적으로 프로세스에 속하지 않으며 프로세서 리소스를 박탈해서는 안 됩니다.
프로세스는 운영 체제 커널 프로그램의 임계 영역에 있습니다. 임계 영역에 들어간 후에는 공유 데이터에 독점적으로 액세스해야 하며, 이론적으로는 다른 병렬 프로그램이 들어가지 못하도록 잠겨야 합니다. 잠금을 해제하기 전에 다른 프로세스로 전환하여 공유 데이터의 릴리스 속도를 높이세요.
잠금, 잠금 해제, 사이트 보호 중단, 복구 및 기타 원자 작업과 같이 인터럽트의 완전한 보호가 필요한 기타 원자 작업입니다. 원자적 프로세스에서는 인터럽트도 마스크되어야 하며 프로세스 스케줄링 및 전환이 수행되어서는 안 됩니다.

위 과정 중 스케줄링을 유발하는 조건이 발생하여 스케줄링 및 전환을 즉시 수행할 수 없는 경우 시스템의 요청 스케줄링 플래그를 설정해야 하며, 위 프로세스가 완료될 때까지 해당 스케줄링 및 전환이 수행되지 않습니다.

프로세스 스케줄링 및 전환이 수행되어야 하는 상황은 다음과 같습니다.

스케줄링 조건이 발생하고 현재 프로세스를 계속 실행할 수 없는 경우 스케줄링 및 전환이 즉시 수행될 수 있습니다. 이런 상황에서 운영체제가 프로세스 스케줄링만 수행한다면, 이는 비박탈 스케줄링이다.
인터럽트 처리나 트랩 처리가 완료되면, 중단된 프로세스의 사용자 모드 프로그램 실행 사이트로 복귀하기 전에 요청 스케줄링 플래그가 설정되어 있으면 프로세스 스케줄링 및 전환이 즉시 수행될 수 있습니다. 이 경우 운영 체제가 실행 스케줄러를 지원하면 박탈 모드 스케줄링이 구현됩니다.

프로세스 전환은 스케줄링이 완료된 직후에 발생하는 경우가 많습니다. 원래 프로세스의 현재 전환점에 대한 현장 정보를 저장하고 예정된 프로세스의 현장 정보를 복원해야 합니다. 컨텍스트를 전환할 때 운영 체제 커널은 원래 프로세스의 컨텍스트 정보를 현재 프로세스의 커널 스택에 푸시하여 저장하고 스택 포인터를 업데이트합니다. 커널은 새 프로세스의 커널 스택에서 새 프로세스의 로컬 정보 로드, 현재 실행 중인 프로세스 공간 포인터 업데이트, PC 레지스터 재설정 및 기타 관련 작업을 완료한 후 새 프로세스를 실행하기 시작합니다.

스케줄링 방법

비선점 방법
프로세서가 프로세스에 할당되면 현재 실행 중인 프로세스의 프로세서는 클록 중단이나 다른 이유로 인해 선점되지 않습니다. 이벤트로 인해 프로세스가 완료되거나 차단된 경우에만 프로세서가 다른 프로세스에 할당됩니다.
선점 모드
이 시스템에서는 스케줄러가 특정 원칙에 따라 실행 프로세스를 일시 중지할 수 있으며 할당된 프로세스는 프로세스의 프로세서가 다른 프로세스에 재할당됩니다.
"선점"할 때 특정 원칙을 따라야 합니다:

우선순위 원칙
단기 프로세스 우선순위 원칙
타임 슬라이스 원리

일반적인 스케줄링 알고리즘

선착순 스케줄링 알고리즘(선착순):

즉, FCFS 스케줄링 알고리즘은 두 가지 작업 스케줄링 모두에 사용할 수 있습니다. 작업이 도착하는 순서에 따라 시스템이 일정을 잡습니다(준비 대기열에서 대기 시간이 가장 긴 작업을 우선시함).
단점: 작업의 긴급성을 고려하지 않고 짧은 작업만 수행합니다. (프로세스)를 순차적으로 실행할 수 있습니다

우선순위 스케줄링 알고리즘(짧은 작업 우선):

대부분의 운영 체제가 짧은 작업이므로 시스템은 작업이 실행될 때 가장 짧은 작업을 선택합니다.

SJF(비선점형): 알고리즘은 작업 길이(작업을 실행해야 하는 시간)를 기준으로 우선순위를 계산합니다.

SPF(선점형): 위와 동일하지만 작업의 우선순위가 높을 경우 리소스를 먼저 점유하여 실행할 수 있습니다.

실행 중입니다. 작업 시간을 미리 예측해야 합니다

작업 프로세스에 해롭다
인간-컴퓨터 상호 작용을 구현할 수 없습니다
작업의 긴급성을 고려하지 않습니다
우선 순위 -스케줄링 알고리즘:

PSA 알고리즘은 작업의 긴급성을 기준으로 작업 우선순위 일정에 따라 해당

우선순위

를 작업에 할당합니다. 다음으로 높은 요청 비율):

HRRN 알고리즘. 작업의 대기 시간과 작업 실행 시간을 모두 고려합니다. 작업이 없는 경우 동적 우선순위를 도입합니다.

우선순위 권리 = (대기 시간 + 요청 서비스 시간) / 요청 서비스 시간

은 다음과 같이 축약될 수 있습니다.

R = 응답 시간 / 요청 서비스 시간

특징:

작업 대기 시간이 동일하면 요청 서비스 시간이 짧을수록 우선 순위가 높아지며 이는 SJF 알고리즘과 유사합니다.

동일한 서비스 시간이 필요한 작업의 경우 작업 대기 시간이 대략 길어지고 우선 순위가 높아집니다. 이는 FCFS 알고리즘과 유사하며 긴 작업에 유리합니다. 긴 작업(긴 서비스 시간 필요)은 대기 시간이 충분히 길기 때문에 더 높은 우선순위를 얻을 수도 있습니다. 영원히 기다리지 않을 것입니다.
타임 슬라이스 회전 스케줄링 알고리즘(RR)

원리: 시스템이 정렬합니다. 준비된 모든 프로세스를 FCFS 정책에 따라 준비된 큐에 넣고 일정한 간격으로 순차 인터럽트를 생성하도록 설정하고 시스템의 프로세스 스케줄러를 활성화하여 순차 스케줄링을 완료하고 CPU를 새로운 큐 리더 프로세스(또는 새로 도착한 긴급 프로세스).
프로세스 전환

타임 슬라이스가 모두 사용되지 않고 실행 중인 프로세스가 완료되면 스케줄러가 즉시 활성화되고 실행 큐에서 제거되며 예약 준비 큐에 배치됩니다. 대기열의 헤드 프로세스가 실행되어 새로운 시간 조각을 시작합니다. 시간 조각이 모두 사용되면 타이밍 인터럽트 처리기가 활성화됩니다. 프로세스 실행이 완료되지 않으면 스케줄러는 이를 준비 대기열의 끝으로 보냅니다. 그리고 준비된 대기열의 리더 프로세스를 예약하고 새로운 타임 슬라이스를 시작합니다.

참고

: 타임 슬라이스를 너무 작게 선택하면 빈번한 실행 프로세스 스케줄링과 프로세스 긴 컨텍스트 전환이 시스템 오버헤드를 증가시킵니다. 타임 슬라이스 선택 너무 길면 RR 알고리즘이 FCFS 알고리즘으로 변질되어 짧은 작업 및 대화형 사용자의 요구를 충족할 수 없습니다. 타임 슬라이스는 일반적인 상호 작용에 필요한 시간보다 약간 더 크게 선택해야 합니다. 대부분의 프로세스는 하나의 타임 슬라이스 내에 완료됩니다.

자세히 다단계 피드백 큐 스케줄링 알고리즘(다단계 피드백 큐):
여러 개의 준비 큐를 설정하고 각 큐에 서로 다른 우선순위를 부여합니다. 우선순위 큐가 높을수록 타임 슬라이스는 작아집니다. . 우선 순위가 가장 높은 대기열의 시간 조각이 가장 작습니다. 예약할 대기열을 먼저 입력하세요

대기열 간에는 FCFS 스케줄링 알고리즘이 사용됩니다. 우선 순위가 높은 대기열의 모든 프로세스가 완료되면 다음 대기열이 사용됩니다. cheduled

큐에 있는 프로세스는 순환 알고리즘에 따라 예약됩니다. 새로운 프로세스가 메모리에 들어간 후 우선 순위가 가장 높은 큐에 먼저 들어갑니다

우선 순위가 낮은 큐가 실행될 때 새로운 프로세스가 실행되면 프로세스가 도착하면 이 타임 슬라이스를 실행한 후 새로 도착한 작업에 CPU가 즉시 할당됩니다(선점형).

실시간 시스템의 프로세스 스케줄링 알고리즘

실시간 시스템이란 시스템이 외부 이벤트 요청에 적시에 응답하고 이러한 요청을 적시에 처리할 수 있음을 의미합니다.
실시간 시스템에서는 일반적으로 마감일이 있습니다. 하드 실시간 작업(HRT)은 시작 마감일 전에 실행되어야 하며 종료 전에 완료되어야 합니다. 마감일 소프트 실시간 작업은 위와 동일하지만 엄격하지는 않습니다.
실시간 시스템에는 주목할만한 두 가지 유형의 알고리즘이 있습니다: 가장 빠른 마감일 우선 및 최소 느슨함 우선. 두 가지 유형의 알고리즘 모두 선점형 및 최소 여유분 우선으로 사용할 수 있습니다. 비선점 스케줄링이지만 선점 스케줄링에서는 후자가 자주 사용됩니다.
m 주기 실시간 스케줄링에서는 각 실시간 작업의 처리 시간 (C_i), 주기 시간 (P_i), 프로세서가 1개인 경우 조건을 충족해야 함: $sum_{i= 1}^mfrac{C_i}{P_i} (1개 미만, 다중 프로세서 조건에서는 조건을 충족해야 함)sum_{ i=1}^mfrac{C_i}{P_i} $는 N보다 작습니다. N은 프로세서 수입니다.