[운영체제] 공룡책(Operating System Concepts) 연습문제 풀기: 5장

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

5장 - CPU 스케줄링

5.1 CPU 스케줄링 알고리즘은 스케줄 된 프로세스의 실행 순서를 결정한다. 하나의 프로세서에서 n개의 프로세스를 스케줄 하면 몇 개의 다른 스케줄이 가능한가?

• 하나의 프로세서에서 n개의 프로세스를 스케줄링하게 되면 가능한 모든 조합으로 다 스케줄링 할 수 있기 때문에 총 n! 개의 다른 스케줄링이 가능하다.

5.2 선점 스케줄링과 비선점 스케줄링의 차이점을 설명하라

• Preemtive 스케줄링은 현재 CPU에 할당된 프로세스가 스스로 작업이 중단되거나 작업을 완료한 후 CPU에서 방출되지 않아도 스케줄러에 의해 강제로 CPU에 할당되는 프로세스가 변경되는 방식이다. 반면에 Nonpreemtive 스케줄링은 현재 CPU를 점유하고 있는 프로세스가 스스로 CPU에서 방출될 때까지 다른 프로세스를 할당하지 못하고 기다려야 한다.

5.3 표시된 시간에 다음 프로세스가 도착한다고 가정하자. 각 프로세스는 나열된 시간동안 실행된다. 질문에 답할 때, 비선점 스케줄링을 사용하고 결정을 해야할 시점에 가지고 있는 정보를 기초로 결정을 내려야 한다.

• FCFS 스케줄링 알고리즘을 사용할 경우 프로세스의 평균 총처리 시간은 얼마인가?

  • 총 처리시간은 대기시간과 실행시간을 모두 포함하기 때문에 총 처리시간은 P1(8) + P2(8 - 0.4 + 4) + P3(8 - 1.0 + 4 + 1) = 30.6 이 된다. 따라서 평균 총 처리시간은 30.6/3 = 10.2 가 된다.

• SJF 스케줄링 알고리즘을 사용할 경우 프로세스의 평균 총 처리시간은 얼마인가?

  • SJF 알고리즘은 잔여시긴을 우선으로 프로세스를 스케줄링 한다. 도착시간을 고려해서 스케줄링을 간트차트로 표현해보면, | P1(8) | P3(1) | P2(4) | 가 된다. 차트를 따라 계산해보면 총 처리시간은 P1(8) + P2(4 + 8 + 1) + P3(1 + 8) = 30 가 된다. 따라서 평균 총 처리시간은 30/3 = 10이 된다.

• SJF 알고리즘은 성능을 향상해야 하지만 두 개의 더 짧은 프로세스가 곧 도착할 것임을 알지 못했기 때문에 시간 0에서 프로세스 P1을 실행하기로 선택했다. CPU가 첫 1 단위동안 유휴상태로 유지된 후 SJF 스케줄링이 사용되는 경우 평군 총 처리시간을 계산하라.

  • 초기 1의 단위시간동안 유휴상태로 둔 채로 스케줄링을 해보면, | idle(1) | P3(1) | P2(4) | P1(8) | 이 된다. idle 상태 동안 P1과 P2가 도착했기 때문에 이들의 대기시간까지 고려해보면 총 처리시간은 P1(1 + 4 + 8 + 1) + P2(1 + 4 + 0.6) + P3(1) = 20.6 이고, 평균 총 처리시간은 20.6/3 = 6.87이 된다.

5.4 CPU 버스트 시간의 길이가 밀리초 단위로 다음과 같은 프로세스 집합을 고려하시오

• 프로세스는 모두 시간 0에서 P1, P2, P3, P4, P5 순서로 도착한 것으로 가정한다.

  • FCFS, SJF, 비선점형 우선순위, RR(양자=2) 을 사용하여 간트 차트를 그려라.
  • FCFS : |P1|P2|P3|P4|P5|
  • SJF : |P2|P1|P4|P5|P3|
  • 비선점 우선순위 : |P2|P1|P5|P4|P3|
  • RR : |P1|P2|P3|P4|P5|P3|P4|P5|P3|P5|P3|
  • 각 스케줄링 알고리즘에 대한 각 프로세스의 처리시간은 얼마인가?
  • 모든 프로세스가 버스트타임과 동일한 처리시간을 가진다.
  • 각 스케줄링 알고리즘에 대한 각 프로세스의 대기시간은 얼마인가?
  • FCFS : P1(0), P2(2), P3(3), P4(11), P5(15)
  • SJF : P2(0), P1(1), P4(3), P5(7), P3(12)
  • 비선점 우선순위 : P2(0), P1(1), P5(3), P4(8), P3(12)
  • RR : P1(0), P2(2), P3(13), P4(9), P5(15)
  • 어떤 알고리즘이 최소 평균 대기시간을 보이는가?
  • SJF 알고리즘. 평균 대기시간은 (0 + 1 + 3 + 7 + 12)/5 = 4.6 이다.

5.5 생략.

5.6 다단계 큐 시스템에서 단계마다 다른 시간 할당량을 지정하는 것은 어떤 이점이 있는가?

• 일반적으로 다단계 큐 스케줄링의 최상단 계층에는 interative 한 프로세스를 우선적으로 처리하기 위해 사용한다. 그리고 또 일반적으로 실시간 반응을 요구하는 프로세스는 burst time이 짧고, 백그라운드 프로세스는 burst time이 길다. 이 점을 사용해서 다단계 큐 스케줄링의 제일 상단에 짧은 time quantum 을 가지는 RR을 배치하고, 그 하위에 상위 RR의 두배가 되는 time quantum을 가지는 RR을 배치하면, CPU Burst 가 짧은 프로세스들은 바로바로 처리될 것이고, 그것보다 조금 긴 프로세스는 중간단계에서 처리되고, 이것보다 더 긴 프로세스는 완전히 우선순위를 낮추어 백그라운드에서 실행될 수 있도록 한다.

5.7 생략.

5.8 CPU 스케줄링 알고리즘이 최근 과거에 가장 적은 프로세서 시간을 사용한 프로세스를 선호한다고 가정한다. 이 알고리즘이 I/O 중심 프로그램을 선호하지만 CPU 중심 프로그램을 영구적인 기아 상태로 만들지 않는 이유는 무엇인가?

5.9 PCS와 SCS 스케줄링을 구분하라

• PCS 스케줄링은 같은 프로세스 내의 스레드들이 CPU를 선점하려고 경정하게 되는 스케줄링이다. 반면에 SCS는 시스템에 존재하는 모든 스레드가 CPU를 선점하기 위해 경정하게되는 스케줄링이다.