#15 스케줄링 알고리즘 - FIFO(First In First Out) / 평균 대기 시간
2023.02.05 - [자료구조 및 알고리즘] - #7 큐(Queue) - 개념(FIFO : First In First Out)
#7 큐(Queue) - 개념(FIFO : First In First Out)
- 큐(Queue)도 Stack과 같이 단순한 규칙을 가지고 있는 리스트이다. - 규칙 : FIFO(First In First Out) - 즉, 먼저 들어간 데이터가 가장 먼저 나온다는 의미로서 먼저 들어간게 가장 나중에 나오는 Stack과
radderveloper.tistory.com
● FIFO
- CPU 스케줄링 알고리즘(FIFO, SJF, RR, MLFQ) 중 하나인 FIFO에 대해 알아보자
- FIFO(First In First Out) : 먼저 들어온 작업이 먼저 처리된다.(나간다.) 즉, 프로세스가 스케줄링 Queue에 들어온 순서대로 CPU를 할당 받는 방식이다.
- FIFO 방식은 먼저 들어온 프로세스가 완전히 끝나야 다음 프로세스가 실행될 수 있다.
[장점]
- 단순하고 직관적
[단점]
- 하나의 프로세스가 완전히 끝나야 다음 프로세스가 시작될 수 있기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 먼저 도착한 프로세스의 작업을 기다려야한다.
- 만약 프로세스에 I/O 작업이 있으면 CPU는 I/O 작업이 끝날 때까지 쉬고 있기 때문에 CPU 사용률도 떨어진다.● 평균 대기 시간
- 스케줄링의 성능은 평균 대기 시간으로 평가한다.
- 평균 대기 시간 : 여러개의 프로세스가 실행될 때 해당 프로세스들이 모두 실행되기까지의 대기 시간의 평균
- 위의 그림의 경우 대기 시간이 왼쪽에서부터 5초, 4초, 0초 이므로 평균 대기 시간은 9 / 3 = 3초이다.
- 조금 더 자세한 예로 알아보자
- 프로세스1의 작업 시간(Burst Time)은 25초이다.
- 프로세스2의 작업 시간(Burst Time)은 5초이다.
- 프로세스3의 작업 시간(Burst Time)은 4초이다.
- 프로세스1이 먼저 도착했기에 가장 먼저 실행된다.
- 이때 프로세스1은 기다림 없이 바로 실행되기 때문에 프로세스1의 대기 시간은 0초이다.
- 프로세스1이 25초 동안 실행을 한 후 바로 프로세스2가 실행된다.
- 이때 프로세스2는 프로세스1의 작업 시간(25초) 동안 기다렸으므로 프로세스2의 대기 시간은 25초이다.
- 프로세스2가 5초 동안 실행을 한 후 바로 프로세스3이 실행된다.
- 이때 프로세스3은 프로세스1의 작업 시간(25초)과 프로세스2의 작업 시간(5초) 동안 기다렸으므로 프로세스3의
대기 시간은 30초이다.
- 3개의 프로세스의 평균 대기 시간 = (0 + 25 + 30) / 3 = 18.3초이다.- 이번에는 Burst Time이 짧은 순서대로 프로세스를 실행 시켜보자
- 프로세스3이 먼저 도착했기에 가장 먼저 실행된다.
- 이때 프로세스3은 기다림 없이 바로 실행되기 때문에 프로세스3의 대기 시간은 0초이다.
- 프로세스3이 4초 동안 실행을 한 후 바로 프로세스2가 실행된다.
- 이때 프로세스2는 프로세스3의 작업 시간(4초) 동안 기다렸으므로 프로세스2의 대기 시간은 4초이다.
- 프로세스2가 5초 동안 실행을 한 후 바로 프로세스1이 실행된다.
- 이때 프로세스1은 프로세스3의 작업 시간(4초)과 프로세스2의 작업 시간(5초) 동안 기다렸으므로 프로세스3의
대기 시간은 9초이다.
- 3개의 프로세스의 평균 대기 시간 = (0 + 4 + 9) / 3 = 4.3초이다.- 이렇게 프로세스의 실행 순서만 바꿨을 뿐인데 평균 대기 시간의 차이가 많이 난다.
- FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능 차이가 크게 나기 때문에 오늘날의 OS에서는 잘 쓰이지 않고 일괄 처리 시스템에서 사용된다.
