이 튜토리얼에서는 CPU 프로세스 스케줄링 알고리즘의 중요한 개념을 배우게 됩니다. 중요한 개념 이름은 First Come First Serve입니다. 이것은 CPU 프로세스 스케줄링 알고리즘의 모든 기본을 이해하기 위해 모든 학생이 배워야 하는 기본 알고리즘입니다.

First Come First Serve는 다른 알고리즘을 이해할 수 있는 길을 열어줍니다. 이 알고리즘에는 많은 단점이 있을 수 있습니다. 그러나 이러한 단점으로 인해 매우 새롭고 효율적인 알고리즘이 탄생했습니다. 따라서 선착순 CPU 프로세스 스케줄링 알고리즘에 대해 배우는 것은 우리의 책임입니다.

칼리 리눅스 명령

중요한 약어

1. CPU - - - > 중앙처리장치
2. FCFS - - - > 선착순
3. AT - - - > 도착 시간
4. BT - - - > 버스트 시간
5. WT - - - > 대기 시간
6. TAT - - - > 처리 시간
7. CT - - - > 완료 시간
8. FIFO - - - > 선입선출

선착순

FCFS라고도 알려진 선착순 CPU 스케줄링 알고리즘은 CPU 프로세스 스케줄링 알고리즘의 첫 번째 알고리즘입니다. 선착순 알고리즘에서 우리가 하는 일은 프로세스가 선형 방식으로 실행되도록 하는 것입니다.

즉, 프로세스에 진입하는 프로세스 중 먼저 준비 대기열에 진입하는 프로세스가 먼저 실행됩니다. 이는 선착순 알고리즘이 FIFO(선입선출) 원칙을 따른다는 것을 보여줍니다.

선착순 알고리즘은 선점형 및 비선점형 방식으로 실행될 수 있습니다. 예제를 살펴보기 전에 CPU 프로세스 스케줄링에서 선제적 접근 방식과 비선점적 접근 방식이 무엇인지 알아보겠습니다.

선제적 접근 방식

이 선점형 프로세스 스케줄링의 경우 OS는 미리 결정된 기간 동안 프로세스에 리소스를 할당합니다. 프로세스는 자원 할당 중에 실행 상태에서 준비 상태로 전환되거나 대기 상태에서 준비 상태로 전환됩니다. 이러한 전환은 CPU가 다른 프로세스에 우선 순위를 할당하고 현재 활성 프로세스를 우선 순위가 더 높은 프로세스로 대체할 수 있기 때문에 발생합니다.

비선제적 접근 방식

이 비선점형 프로세스 스케줄링의 경우 프로세스 실행이 완료되기 전에 프로세스에서 리소스를 철회할 수 없습니다. 실행 중인 프로세스가 완료되고 대기 상태로 전환되면 리소스가 전환됩니다.

선착순 호송 효과(FCFS)

호송 효과는 FCFS(First Come First Serve)라는 스케줄링 알고리즘에서 발생하는 현상입니다. 선착순 스케줄링 알고리즘은 비선점 방식으로 발생합니다.

비선점형 방식은 프로세스나 작업이 실행되기 시작하면 운영 체제가 해당 프로세스나 작업을 완료해야 함을 의미합니다. 프로세스나 작업이 0이 될 때까지 새 프로세스나 작업은 실행을 시작하지 않습니다. 비선점형 스케줄링을 운영체제 측면에서 정의하면 먼저 시작된 프로세스나 작업이 끝날 때까지 중앙처리장치(CPU)를 완전히 전용하고, 이전 프로세스나 작업이 끝난 후에야 새로운 프로세스나 작업을 실행하는 것을 의미한다. 직업.

중앙 처리 장치(CPU)가 너무 많은 시간을 할당하게 만드는 몇 가지 경우가 있을 수 있습니다. 이는 선착순 스케줄링 알고리즘 비선점형 접근 방식에서는 프로세스 또는 작업이 순차적으로 선택되기 때문입니다. 이로 인해 더 큰 프로세스나 작업 뒤에 있는 더 짧은 작업이나 프로세스로 인해 실행을 완료하는 데 너무 많은 시간이 걸립니다. 이로 인해 대기 시간, 처리 시간, 완료 시간이 매우 높습니다.

따라서 여기서는 첫 번째 프로세스가 크거나 완료 시간이 너무 길기 때문에 First Come First Serve 알고리즘에서 이러한 Convoy 효과가 발생합니다.

Longer Job을 완료하는 데 무한한 시간이 걸린다고 가정해 보겠습니다. 그러면 나머지 프로세스는 동일한 무한 시간을 기다려야 합니다. Longer Job으로 인해 발생하는 Convoy Effect로 인해 대기 프로세스의 기아 상태가 매우 빠르게 증가합니다. 이는 FCFS CPU 프로세스 스케줄링의 가장 큰 단점입니다.

FCFS CPU 프로세스 스케줄링의 특징

FCFS CPU 프로세스 스케줄링의 특징은 다음과 같습니다.

1. 구현은 간단합니다.
2. 사용시 어떠한 인과관계도 일으키지 않습니다.
3. 비선점형, 선점형 전략을 채택하고 있습니다.
4. 수신된 순서대로 각 프로시저를 실행합니다.
5. 도착 시간은 절차 선택 기준으로 사용됩니다.

FCFS CPU 프로세스 스케줄링의 장점

FCFS CPU 프로세스 스케줄링의 장점은 다음과 같습니다.

1. 프로세스를 할당하기 위해 First In First Out 큐를 사용합니다.
2. FCFS CPU 스케줄링 프로세스는 간단하고 구현하기 쉽습니다.
3. FCFS 상황 선점형 스케줄링에서는 프로세스가 고갈될 가능성이 없습니다.
4. 프로세스 우선순위를 고려하지 않기 때문에 공평한 알고리즘이다.

FCFS CPU 프로세스 스케줄링의 단점

FCFS CPU 프로세스 스케줄링의 단점은 다음과 같습니다.

• FCFS CPU 스케줄링 알고리즘의 대기 시간이 길다
• FCFS CPU 스케줄링은 입력 또는 출력 작업보다 CPU를 선호합니다.
• FCFS에서는 호송효과(Convoy Effect)가 발생할 가능성이 있습니다.
• FCFS는 매우 간단하기 때문에 그다지 효과적이지 않은 경우가 많습니다. 연장된 대기 기간은 이와 밀접한 관련이 있습니다. CPU가 시간이 많이 걸리는 주문 하나를 처리하는 데 바쁜 경우 다른 모든 주문은 유휴 상태로 유지됩니다.

선착순 CPU 스케줄링 알고리즘의 문제점

strsep

예

 S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2 

비선제적 접근 방식

이제 비선점형 접근 방식의 First Come First Serve라는 스케줄링 알고리즘을 사용하여 이 문제를 해결해 보겠습니다.

위 예 1의 간트 차트는 다음과 같습니다.

배열 슬라이싱 자바

처리 시간 = 완료 시간 - 도착 시간

대기 시간 = 처리 시간 - 버스트 시간

위 질문에 대한 해결책 예 1

평균 완료 시간은 다음과 같습니다.

평균 CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6

평균 CT = 97 / 6

평균 CT = 16.16667

평균 대기 시간은 다음과 같습니다.

평균 WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6

평균 WT = 66 / 6

평균 WT = 11

평균 처리 시간은 다음과 같습니다.

평균 TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6

순서대로

평균 TAT = 89 / 6

평균 TAT = 14.83334

이것이 Non Pre Emptive Approach에서 FCFS를 해결하는 방법입니다.

이제 Pre Emptive Approach에서 어떻게 해결할 수 있는지 알아보겠습니다.

선제적 접근 방식

이제 선점형 접근 방식의 First Come First Serve라는 스케줄링 알고리즘을 사용하여 이 문제를 해결해 보겠습니다.

선제적 접근 방식에서는 사용 가능한 최상의 프로세스를 검색합니다.

위 예 1의 간트 차트는 다음과 같습니다.

나무와 그래프 이론