정리_

- CPU스케줄러(CPU scheduler)

  CPU가 유휴상태가 될 때마다, 운영체제는 준비 완료 큐(ready queue)에 있는 프로세스들 중 하나를 선택해 실행해야 한다. 선택 절차는 short term(단기) 스케줄러에 의해 수행된다.

* short term scheduler = CPU scheduler

  CPU 스케줄러는 ready queue에 있는 어느 프로세스에게 CPU를 할당할 것인지를 결정하는 문제를 다룬다. 이에는 여러가지 알고리즘들이 존재한다.

1.     선입 선처리 스케줄링(First-Come, First-Served Scheduling)

  비선점 알고리즘이다. 가장 간단한 CPU스케줄링 알고리즘이며 FIFO라고도 한다. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다.

  여기서 각각의 turnaround time은 25, 30, 33이며 평균 대기 시간은 (0+25+30)/3=18.33이다. 이때 프로세스의 순서를 P3, P2, P1순으로 바꾸어주면 (0+3+8)/3=3.66으로 크게 줄어든다.

* convoy effect(호위효과) : 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU가 양도하기를 기다리는 것을 말한다. 호위효과는 작을수록 좋다.

2.     최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

  SJF 스케줄링은 장기 스케줄링에서 자주 사용된다. 이 스케줄링은 선점일 수도 있고 비선점일 수도 있다. CPU의 버스트 길이를 연관시켜 구현하였다.

  평균 대기 시간은 (3+0+16+9)/4=7이다. 하지만 SJF의 어려움은 다음 CPU의 길이를 파악하는 것이다. 다음 burst(프로세스)는 지수 평균한 것으로 예측한다. 아래는 선점형 SJF알고리즘을 통해 구현한 스케줄링이다.

3.     라운드 로빈 스케줄링(Round-Robin Scheduling)

  RR알고리즘은 선점형 알고리즘으로, 시분할 시스템을 위해 설계되었다. FCFS스케줄링과 비슷하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점이 추가된다. 시간 할당량(time quantum) 또는 time slice라는 시간의 '단위'를 정의하여 구현한다. 어떤 프로세스가 이 단위 시간을 지나면 실행을 강제로 다른 프로세스에게 선점시키는 것이다. 일반적으로 time quantum은 10에서 100밀리초 동안이다.

  평균 대기시간은 (0+5+6+9)/4=5밀리초이다. 반응 시간의 정의는 처음 반응한 시간이기 때문에 P2의 반응 시간은 3밀리초이다. RR 알고리즘의 성능은 time quantum(시간 할당량)의 크기에 매우 큰 영향을 받는다. time quantum이 너무 큰 경우에는 FCFS와 같아질 것이며 time quantum이 너무 작아진다면 context switch가 자주 일어나 프로세스의 실행이 느려질 수 있다.

4.     다단계 큐 스케줄링(Multilevel Queue Scheduling)

  다단계 큐 스케줄링 알고리즘은 foreground(대화형) 프로세스와 background(일괄처리) 프로세스들을 구분한다. 이들 두 유형의 프로세스는 응답시간에 대한 요구사항이 다르기 때문에, 스케줄링 요구 또한 다를 것이다. 다단계 큐 스케줄링 알고리즘은 ready queue를 다수의 별도의 큐로 구분하여 각 큐는 자신의 스케줄링 알고리즘을 가지고 있다.

각 큐는 우선순위를 가진다.

     1. 시스템 프로세스

     2. 대화형 프로세스

     3. 대화형 편집 프로세스

     4. 일괄처리 프로세스

     5. 학생 프로세스

  시스템 프로세스가 가장 높은 우선수위를 가지며 학생 프로세스가 가장 낮은 우선순위를 가진다. 높은 우선순위를 가진 프로세스를 위한 큐 들이 비어있지 않으면 다음 우선순위의 큐는 실행될 수 없다. 

  foreground queue는 자신의 프로세스들 사이에서 라운드 로빈 스케줄링을 위해 CPU시간의 80%가 주어지고, background queue는 CPU시간의 20%를 받아 자신의 프로세스들에게 선입 선처리 방식으로 줄 수 있다.

다중 프로그램 시스템은 CPU의 사용을 최대화 하기 위한 시스템이다. 다중 프로그램 운영체제의 기본은 CPU스케줄링이다. CPU를 프로세스들 간에 교환함으로써, 컴퓨터를 생산적으로 만든다. 이 다수의 프로세스들을 교환할때 필요한 것이 CPU스케줄링이다.

CPU-입출력 버스트 사이클(CPU-I/O Burst Cycle)

• 버스트란 특정 기준에 따라 한 단위로서 취급되는 연속된 신호나 데이터의 모임을 말한다. 즉, 입출력 요청을 위해 CPU 사용을 사용했다가 쉬었다가를 반복한다.

• 프로세스가 CPU를 사용할 때를 CPU버스트, 입/출력을 기다릴 때를 입/출력 버스트라고 한다.

• CPU 버스트 : CPU에 해당하는 접근이 많은 것이다. running 안에 들어가 있는 시간이 많다. 프로그램 수행 중에 연속적으로 CPU를 사용하는 단절된 구간을 말한다. 즉, CPU명령을 실행하는 것을 말한다.

• I/O 버스트 : I/O에 해당하는 접근이 많은 것이다. waiting 안에 들어가 있는 시간이 많다.

• 프로세스의 실행은 CPU 버스트를 시작으로 뒤이어 입출력 버스트가 발생하는 식으로 두 버스트의 사이클로 구성된다. 마지막 CPU버스트는 또 다른 입출력 버스트가 뒤따르는 대신에 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

• 입출력 중심의 프로그램은 CPU 버스트 시간이 짧을 것이다. 반대로 CPU 지향 프로그램은 CPU 버스트 시간이 길 것이다.

Preemptive Scheduling(선점 스케줄링)

• 수행되고 있는 프로세서의 권한을 가지고 올 수 있다.

• 빠른 응답시간을 요구하는 대화식 시분할 시스템에 사용한다.

• 선점으로 인해 많은 오버헤드를 초래할 수 있다.

• 선점을 위해 인터럽트 타이머 클럭이 필요하다.

• 종류 : 선점 우선순위, RR(Round Robin), 다단계 큐, 다단계 피드백 큐 알고리즘 등

non-Preemptive Scheduling(비선점 스케줄링)

• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없다.

• 한 프로세스가 실행 상태에서 대기 상태로 전환될 때, 프로세스가 종료할 때 비선점 스케줄링을 사용한다.

• 응답시간 예측이 쉽다.

• 협조적(cooperative)이며 모든 프로세스를 공정하게 처리한다.

• 종류 : FCFS, SJF, 우선순위, HRN, 기한부 알고리즘 등

Dispatcher(디스패처)

• CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다. 즉, ready에서 running으로 넘어갈 때 스케줄러에 의해 선택되는 것을 말한다.

  • context switch가 일어나는 일

  • 사용자 모드로 전환하는 일

  • 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

• 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 dispatch latency(디스패치 지연)라고 한다. 이는 ready queue에서 running queue로 넘어갈 때 PCB에 복사해 주는 시간을 말하며, 시스템 효율을 결정한다.

CPU스케줄링 알고리즘은 다양한 특성을 가지고 있다. 그에 따라 다섯 가지로 기준을 나눌 수 있다.

<기억합시다>

① utilization(CPU 이용률) : CPU를 최대한 바쁘게 유지하는 것이 좋다.

② throughput(처리량) : 단위 시간 당 완료된 프로세스의 개수를 말한다.

③ turnaround time(총 처리 시간) : 프로세스를 실행하는 데 소요된 시간을 말한다. 프로세스의 제출 시간과 완료 시간의 간격을 말한다.

④ waiting time(대기시간) : 프로세스가 ready/waiting queue에서 대기하는 시간을 말한다.

⑤ response time(응답시간) : 응답이 시작되는 데까지 걸리는 시간을 말한다. 처음 반응한 시간을 말한다.

** turnaround time(총 처리 시간) - running에 있는 시간 = waiting time(대기 시간)