프로세스 예약

컴퓨터에 준비 상태의 프로세스가 여러 개 있는 경우 어떤 프로세스에 CPU를 할당해야 합니까? 이러한 결정을 내리는 운영 체제의 구성 요소는 스케줄러입니다. 의사 결정 알고리즘을 스케줄링 알고리즘이라고 하며 의사 결정 프로세스는 프로세스 스케줄링 프로세스입니다.

프로세스 스케줄링은 일반적으로 다음과 같은 상황에서 발생합니다.

비선점 스케줄링에서는 프로세스가 실행을 시작한 후 적극적으로 CPU를 포기하거나 차단되지 않는 한 계속해서 실행됩니다. 실행.

선점형 스케줄링에서는 프로세스 실행 중에 우선순위가 더 높은 프로세스가 오면 CPU 사용 권한을 빼앗깁니다. 특히 타임 슬라이스 스케줄링에서는 타임 슬라이스가 아니더라도 CPU 사용 권한을 빼앗깁니다. 소진될 수 있습니다. 그러나 선점은 언제든지 발생할 수 없으며, 설계가 좋지 않으면 우선순위 역전이나 교착상태 문제가 발생할 수 있습니다.

다양한 시나리오에서는 다양한 목표를 달성하기 위해 스케줄링 알고리즘을 평가하는 표준이 다릅니다. 여기서는 일반적으로 사용되는 몇 가지 표준을 소개합니다.

공정성: 각 프로세스에 CPU를 사용할 공정한 기회를 제공합니다.

균형: 시스템의 각 구성 요소가 최대 활용도를 얻도록 허용합니다.

처리량: 단위 시간당 완료된 작업 수

처리 시간: 일반적으로 일괄 처리 시스템에서 일괄 작업 제출과 완료 사이의 시간

CPU Utilization: CPU 사용률

Waiting Time: 프로세스가 준비 대기열에서 기다리는 시간

Response Time: 일반적으로 대화형 시스템에서는 사용자가 작업을 제출하는 시간부터 처음으로 작업을 제출하는 시간까지 응답을 받는 사이의 시간 간격(작업이 완료되지 않을 수 있음)

회의 마감일: 일반적으로 데이터는 손실이나 실패를 방지하기 위해 적시에 실시간 시스템에서 처리됩니다.

다음으로 유형 시스템에서 일반적으로 사용되는 세 가지 스케줄링 알고리즘을 살펴보겠습니다.

1. FCFS: 선착순

비선점형 선착순 알고리즘입니다. 준비된 프로세스 대기열은 하나만 있습니다. 프로세스가 실행 중에 차단되면 블록 큐에 들어가 준비가 된 후 새 프로세스로 준비 큐의 끝에 대기합니다.

장점: 이해하기 쉽고 구현하기 쉽습니다.

단점: 평균 대기 시간이 매우 길어 CPU 집약적인 프로세스와 IO 집약적인 프로세스의 균형을 맞추기가 어렵습니다.

2. SJF : 최단 작업 우선

SJF는 비선점형 스케줄링이기도 하며, 매번 실행을 위해 가장 짧은 작업을 선택합니다.

3. 다음으로 남은 시간이 가장 짧음

SJF의 선점형 버전은 새 작업이 도착하는 한 가장 짧은 남은 시간으로 실행하도록 일정을 변경하고 선택합니다.

SJF와 최단 남은 시간 다음의 문제점은 일반적으로 프로세스의 남은 실행 시간을 판단하기 어렵다는 것입니다. 자주 실행되는 작업이 아닌 이상, 과거 통계 분석을 통해 대략적인 실행 시간 범위를 판단할 수 있습니다.

1. 라운드 로빈 스케줄링

라운드 로빈 스케줄링. 각 프로세스에 동일한 시간 분할을 부여하고 차례로 실행합니다. 일반적으로 20~50msec의 타임 슬라이스를 선택하는 것이 더 적절합니다. 너무 짧으면 프로세스 전환에 시간 낭비가 발생하고, 너무 길면 응답 시간이 길어집니다.

장점: SJF보다 빠른 응답

단점: 처리 시간이 길다

2. 우선순위 스케줄링

프로세스별 우선순위 스케줄링 우선순위 지정 우선 순위가 높은 작업을 먼저 실행합니다. 이것은 또한 시간 분할 스케줄링 알고리즘입니다. 우선순위는 정적 또는 동적으로 할당될 수 있으며, 우선순위가 높은 프로세스가 CPU를 점유하는 것을 방지하기 위해 순차적 실행이 완료된 후 해당 우선순위를 낮출 수 있습니다. 라운드 로빈과 같은 다른 스케줄링 알고리즘은 동일한 우선순위의 프로세스 간에 사용될 수 있으며, 다른 스케줄링 알고리즘은 다른 대기열에 사용될 수 있습니다.

장점: 우선순위 도입

3. 다중 대기열

실행 시간이 긴 프로세스의 빈번한 프로세스 전환을 피하기 위해 서로 다른 우선순위 대기열 간에 대기열을 생성할 수 있습니다. 다양한 길이의 시간 조각을 할당합니다. 프로세스는 한 번 실행되고 실행 시간이 더 긴 다른 우선 순위가 할당됩니다. 예를 들어, 프로세스에는 100개의 퀀타가 필요합니다. 첫 번째 실행에는 1개, 다음 실행에는 2개, 다음 실행에는 4, 8, 16, 32, 64개가 할당됩니다. 각각 1개만 할당하는 순수 폴링 알고리즘과 비교됩니다. 시간 프로세스 스케줄링의 수를 줄입니다.

4. 보장된 스케줄링

위에서 언급한 알고리즘 중 어느 것도 프로세스가 얻을 수 있는 CPU 시간을 보장하지 않지만, 어떤 경우에는 프로세스가 얻을 수 있는 기회와 시간을 보장해야 합니다. n과 같은 CPU 사용 여러 사용자가 동시에 로그인하는 경우 일반적으로 각 사용자가 1/n CPU를 얻을 수 있는지 확인해야 합니다. 또는 VPN 서비스를 구매하고 다양한 사용자 수준에 따라 특정 대역폭 보장을 얻습니다. . 이 알고리즘을 보장된 스케줄링이라고 합니다. 구현에서는 약속된 할당과 비교하여 각 프로세스에 할당된 CPU를 추적해야 하며, 비율이 가장 작은 프로세스가 다음 사용 권한을 얻습니다.

5. 복권 예약

복권 예약 알고리즘은 무작위성을 도입하고 각 프로세스에 복권을 발행합니다. 예약은 복권에 당첨된 사람이 리소스를 얻는 것과 같습니다. 우선순위가 높은 프로세스는 여러 티켓을 획득하여 당첨 확률을 높일 수 있습니다.

복권 예약의 흥미로운 점은 프로세스가 서로에게 복권을 줄 수 있다는 것입니다. 예를 들어 프로세스 1이 프로세스 2에서 보류 중인 경우 모든 복권을 프로세스 2에 제공하여 확률을 높일 수 있습니다. 예정되어 있어서. process2가 끝나면 복권을 process1에 반환합니다.

6. Fair-Share Scheduling

다음 상황을 생각해 보세요. 모든 프로세스가 한 사용자에게 속하지 않는 경우가 많습니다. 리눅스 시스템. user1에 99개의 프로세스가 있고 user2에 1개의 프로세스만 있는 경우 이전 알고리즘에 따르면 user1은 CPU의 99%를 가져오는 반면 user2는 1%만 가질 수 있습니다. 사용자 수준에서 공정성을 이루기 위해서는 스케줄링 시 프로세스가 어느 사용자에게 속하는지 고려해야 합니다.

실시간 시스템에는 두 가지 유형이 있습니다.

실제 -시간 시스템, 일반적인 작업 시간은 상대적으로 짧고 스케줄러 모든 프로세스는 마감일 이전에 완료되어야 합니다. 주기적으로 발생하는 이벤트의 경우, 이벤트 발생 주기가 이고, 이벤트 처리 시간(CPU를 점유하는데 소요되는 시간)이 이면 스케줄링이 가능하다.

스케줄링 알고리즘은 운영체제에서만 구현할 수 있나요? 프로세스에서 어떤 스케줄링 알고리즘을 사용할지 결정하나요? 대답은 '예'입니다. 메커니즘과 전략을 분리하여 운영 체제는 여러 구현 메커니즘을 제공하고 사용할 스케줄링 전략을 지정하기 위해 프로세스에서 OS로 매개변수를 전달하는 시스템 호출을 제공합니다.

스레드가 사용자 모드에서 구현되면 2단계 스케줄링이 필요합니다. OS는 프로세스 스케줄링을 담당하고 프로세스는 스레드 스케줄링을 담당합니다.

스레드가 커널 모드에서 구현되면 OS는 스레드가 속한 프로세스에 상관없이 스레드를 직접 예약합니다.