참고 자료 : https://hyunah030.tistory.com/4

• 준비큐 있는 프로세스에 대해 CPU 할당하는 방법

스케줄링 알고리즘

• 비선점 스케줄링 [Non-preemptive scheduling]
  • FCFS (First Come First Served)

    • 먼저 CPU를 요청하는 프로세스를 먼저 처리하는 방식

    • 다음과 같은 프로세스 요청이 있다고 하자.

      프로세스	Burst Time	Waiting Time	Turnaround Time
      P1	15	0	15
      P2	5	15	20
      P3	3	20	23

    • P1 → P2 → P3 순으로 프로세스가 CPU를 요청할 때, CPU는 아래와 같이 시간을 쓴다.

    • P3는 P1보다 걸리는 시간(Burst time)이 짧지만, CPU를 늦게 요청했기 때문에 총 걸리는 시간(Turnaround Time)이 길다.

    • 평균 Waiting Time : (0 + 15 + 20) / 3 = 11.7

    • 만약, P3 → P2 → P1 순으로 프로세스가 CPU를 요청할 때, CPU는 아래와 같이 시간을 쓴다.

    • 평균 Waiting Time : (0 + 3 + 8) / 3 = 2.7

    • 즉, CPU를 요청하는 프로세스의 burst time에 따라 평균 waiting time이 나빠진다.

  • SJF (Shortest Job First)

    • 평균 waiting time 을 최소화하기 위해 사용하는 방식

    • 버스트 시간이 짧은 프로세스부터 CPU를 할당한다.

    • 다음과 같은 프로세스가 있다고 하자

      프로세스	Burst Time	Waiting Time	Turnaround Time
      P1	6	3	9
      P2	3	0	3
      P3	8	16	24
      P4	7	9	16

    • SJF에서의 스케줄링 순서는 다음과 같다.

      • P2 → P1 → P4 → P3

    • Waiting time 을 최소화하는 데는 최적이지만, burst time이 긴 프로세스은 오랜 시간 굶주려야 하므로, 위에 언급한 No starvation을 어기게 된다.

• 선점 스케줄링 [Preemptive scheduling]

  • 선점 스케줄링에는 몇가지 룰이 있다.

    • 높은 우선순위를 가지는 프로세스는 항상 먼저 스케줄되어야 한다.

    Dynamic priority scheme : 커널안에서 프로세스의 우선순위는 지속적으로 변한다.

    Fixed priority scheme

    • I/O-bound process는 CPU-bound process 보다 반드시 높은 우선순위에 있어야 한다.

    • Time slice 의 양은 CPU burst time 보다 조금만 더 많아야 한다.

      time slice가 더 적을 경우, 불필요한 context switch가 많이 일어난다.

      time slice가 훨씬 클 경우, I/O가 일어날 때에 CPU를 반납하거나, 다른 프로세스는 CPU에 굶주리는 현상이 일어날 수 있다.

    • Real-time 프로세스는 다른 프로세스에 비해 매우 높은 우선순위를 갖는다.

  • SRT(Shortest Remaining Time)

    • 최단 잔여시간을 우선으로 하는 스케줄링.
    • 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep시키고 짧은 프로세스를 먼저 할당한다.
    • 선점형 SJF 스케줄링이라 불린다.

    프로세스	도착시간	Burst Time	종료시간	Waiting Time	Turnaround Time
    P1	0	8	17	9	17
    P2	1	4	5	0	4
    P3	2	9	26	15	24
    P4	3	5	10	2	7

    P1 → P2 → P3 → P4 순서대로 왔어도 도착시간에서의 잔여 시간을 비교해 CPU를 할당한다.

  • RR(Round Robin)

    • Time Sharing System을 위해 설계된 스케줄링

    • 모든 프로세스가 같은 우선순위를 가진고, time slice를 기반으로 스케줄링한다.

    • Time slice burst가 일어나면 해당 프로세스는 스케줄링 큐의 끝으로 이동한다.

    • Time slice 가 3ms 일때의 RR 스케줄링을 가지는 프로세스는 다음과 같이 동작한다.

      프로세스	Burst Time	Waiting Time	Turnaround Time
      P1	13	10	23
      P2	7	3	10
      P3	3	12	15

      평균 Waiting Time : (10 + 3 + 12) / 3 = 8.3

    • 알고리즘의 성능은 Time slice 크기와 같아진다.

      Time slice 가 심하게 크다면 FCFS와 다를게 없다.

      Time slice 가 너무 작다면 불필요한 Context Switch가 많이 일어난다.

    Priority Scheduling (우선 순위 스케줄링)

    • 우선 순위가 높은 프로세스에 CPU를 우선 할당하는 방식의 스케줄링
    • 우선 순위는 시간 제한, 메모리 요구량, 프로세스의 중요성, 자원사용 비용 등에 따라 달라질 수 있다.
    • 우선 순위가 같을 경우, FCFS와 다를게 없다. (비선점, 선점 둘다 사용된다.)