CPU 스케쥴링 알고리즘(1) - FCFS

1. CPU Scheduing

CPU 스케쥴링이란 메인 메모리에 올라와 있는 프로세스들이 CPU의 자원을 할당받기 위해 Ready Queue에 줄서있는 것을 말한다.

  1) Preemptive vs Non-preemptive (선점 : 비선점)

실행 중인 프로세스를 도중에 끄고 스케쥴링하는 방법을 Preemptive라 한다. Non-preemptive 이면 하나의 프로세스가 모두 끝날때까지 다른 프로세스들은 계속 기다려야만 한다.

  2) Scheduling criteria

어떤 스케쥴링 방식이 더 좋은가 판단하는 척도에는 다섯 가지가 있다.

• CPU Utilization(CPU 이용률) : CPU가 얼마나 놀지 않고 일하는가
• Throughput(처리율) : 단위 시간당 몇개의 작업을 처리하는가
• Turnaround time(반환 시간) : 어떤 프로세스가 작업을 끝나고 반환되기까지 걸리는 시간
• Waiting time(대기 시간) : CPU 처리를 받기 위해 얼마나 기다렸는가
• Response Time(응답 시간) : 처음 응답이 나올 때까지 걸리는 시간, 주로 대화형 컴퓨터에서 척도로 사용한다.

2. CPU Scheduling 알고리즘 종류

  1) FCFS(First-Come, First-Served)

  2) Shortest-Job-First(SJF)

    - Shortest-Remaining-Time-First

  3) Priority

  4) Round-Robin(RR)

  5)Multilevel Queue

  6) Multilevel Feedback Queue

3. FCFS (First-Come, First-Served)

FCFS란 먼저 온 프로세스를 처리하는 CPU 스케쥴링 방식이다.

• Simple&Fair : 즉, 간단하고 공평하다는 장점이 있다.
• 비선점 (Nonpreemptive scheduling) 이기에 다른 프로세스가 도중에 끼어들 수 없다.

그러나, AWT(Average Wating Time) 평균 대기 시간 면에서 비효율적일 수 있다는 단점이 있다.

 

P1, P2, P3의 처리 시간이 각각 24, 3, 3이라고 가정해보자.

FCFS의 경우 들어온 순서대로 처리하기 때문에 p1,p2,p3 순으로 처리한다. 이 경우 평균 대기시간은 (0 + 24 + 27) / 3 = 17msec 가 나온다. 그러나 p2, p3, p1 순서대로 처리했다면 (0 + 3 + 6) / 3 = 3msec 로 줄어들게 된다.

 

즉, 들어온 순서대로 처리하면 앞 순번의 프로세스가 상대적으로 오래 걸릴 경우 뒷 순번의 프로세스는 계속 기다려야 하기 때문에 평균 대기 시간이 늘어난다는 단점이 있다. 이 모양이 마치 다른 프로세스들이 시중처럼 따라다닌다고 하여 호위효과(Convoy Effect)라고도 한다.

Gantt Chart(간트 차트)