FCFS 스케줄링 알고리즘: 예제 프로그램이란 무엇입니까?
너다니엘 브룩스
선착순 방식이란 무엇입니까?
선착순(FCFS) 대기 중인 요청과 프로세스를 도착 순서대로 자동으로 실행하는 운영 체제 스케줄링 알고리즘입니다. 가장 쉽고 간단한 CPU 스케줄링 알고리즘입니다. 이 유형의 알고리즘에서는 CPU를 먼저 요청하는 프로세스가 먼저 CPU 할당을 받습니다. 이는 FIFO 큐로 관리됩니다. FCFS의 전체 형식은 First Come First Serve입니다.
프로세스가 준비 대기열에 들어가면 해당 PCB(Process Control Block)가 대기열의 꼬리와 연결되고, CPU가 사용 가능해지면 대기열 시작 부분에 있는 프로세스에 할당되어야 합니다.
FCFS 방식의 특징
- 비선점형 및 선점형 스케줄링 알고리즘을 지원합니다.
- 작업은 항상 선착순으로 실행됩니다.
- 구현하고 사용하기 쉽습니다.
- 이 방법은 성능이 좋지 않으며 일반적인 대기 시간이 상당히 높습니다.
FCFS 스케줄링의 예
FCFS 방법의 실제 예는 매표소에서 영화표를 구매하는 것입니다. 이 스케줄링 알고리즘에서는 대기열 방식에 따라 사람에게 서비스가 제공됩니다. 줄을 서서 먼저 도착한 사람이 먼저 티켓을 구매한 후 다음 티켓을 구매합니다. 이는 대기열의 마지막 사람이 티켓을 구매할 때까지 계속됩니다. 이 알고리즘을 사용하면 CPU 프로세스가 비슷한 방식으로 작동합니다.
FCFS는 어떻게 작동하나요? 평균 대기 시간 계산
다음은 서로 다른 시간에 도착하는 XNUMX개 프로세스의 예입니다. 각 프로세스마다 버스트 시간이 다릅니다.
| 방법 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
FCFS 스케줄링 알고리즘을 사용하여 이러한 프로세스는 다음과 같이 처리됩니다.
단계 1) 프로세스는 도착 시간이 4인 P0부터 시작됩니다.
단계 2) 시간=1에 P3이 도착합니다. P4가 아직 실행 중입니다. 따라서 P3은 대기열에 유지됩니다.
| 방법 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
단계 3) 시간= 2에 P1이 도착하여 대기열에 보관됩니다.
| 방법 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
단계 4) 시간=3에 P4 프로세스가 실행을 완료합니다.
단계 5) 시간=4에서 대기열의 첫 번째 P3이 실행을 시작합니다.
| 방법 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
단계 6) 시간 =5에 P2가 도착하고 대기열에 보관됩니다.
| 방법 | 버스트 시간 | 도착 시간 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
단계 7) 시간 11에서 P3은 실행을 완료합니다.
단계 8) 시간=11에서 P1이 실행을 시작합니다. 버스트 시간은 6입니다. 시간 간격 17에 실행을 완료합니다.
단계 9) 시간=17에서 P5가 실행을 시작합니다. 버스트 시간은 4입니다. 시간=21에 실행이 완료됩니다.
단계 10) 시간=21에서 P2이 실행을 시작합니다. 버스트 시간은 2입니다. 시간 간격 23에 실행을 완료합니다.
단계 11) 위 예의 평균 대기 시간을 계산해 보겠습니다.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
평균 대기 시간
= 40 / 5 = 8
FCFS의 장점
FCFS 스케줄링 알고리즘 사용의 장점/이점은 다음과 같습니다.
- 가장 간단한 형태의 a CPU 스케줄링 알고리즘
- 간편한 프로그래밍
- 선착순
FCFS의 단점
다음은 FCFS 스케줄링 알고리즘 사용의 단점/단점입니다.
- 비선점형 CPU 스케줄링 알고리즘이므로 프로세스가 CPU에 할당된 후에는 실행이 완료될 때까지 CPU를 해제하지 않습니다.
- 평균 대기 시간이 높습니다.
- 대기열 뒤쪽에 있는 짧은 프로세스는 앞쪽에 있는 긴 프로세스가 완료될 때까지 기다려야 합니다.
- 시분할 시스템에는 이상적인 기술이 아닙니다.
- 단순성으로 인해 FCFS는 그다지 효율적이지 않습니다.
요약
- 정의: FCFS는 대기 중인 요청과 프로세스를 도착 순서대로 자동으로 실행하는 운영 체제 스케줄링 알고리즘입니다.
- 비선점형 및 선점형 스케줄링을 지원합니다.
- 연산.
- FCFS는 First Come First Serve의 약자입니다.
- FCFS 방법의 실제 예는 매표소에서 영화표를 구매하는 것입니다.
- CPU 스케줄링 알고리즘의 가장 간단한 형태이다.
- 비선점형 CPU 스케줄링 알고리즘이므로 프로세스가 CPU에 할당된 후에는 실행이 완료될 때까지 CPU를 해제하지 않습니다.
