[운영체제 4주차] - CPU 스케줄링

반효경 교수님의 운영체제 강의와 Operating System Concepts 10th ed. 를 참고하였습니다.

프로세스 간 협력

• 독립적 프로세스

  • 프로세스는 각자의 주소 공간을 가지고 수행되므로 원칙적으로 하나의 프로세스는 다른 프로세스의 수행에 영향을 미치지 못함

• 협력 프로세스

  • 프로세스 협력 메커니즘을 통해 하나의 프로세스가 다른 프로세스의 수행에 영향을 미칠 수 있음

• 프로세스 간 협력 메커니즘

  • 메시지를 전달하는 방법
    위 그림의 (a)에 해당한다. 각 프로세스가 운영체제의 도움을 받아서 message queue에 메시지를 전달하고, 운영체제가 전달하는 방식으로 통신한다. 직접 주고받으면 direct 방식, 어떤 mailbox와 같은 매개체를 사이에 두고 불특정한 프로세스와 주고받으면 indirect 방식이다.

    Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided. Message passing is also easier to implement in a distributed system than shared memory.

  동시에 접근하면서 발생하는 충돌이 발생할 염려가 없기 때문에(커널이 관여하기 때문) 작은 양의 데이터를 주고받는데 유용하다.

  • 공유 메모리를 사용하는 방법
    위 그림의 (b)처럼 두 프로세스의 주소공간 일부를 공유하는 것이다.

    Shared memory can be faster than message passing, since message-passing systems are typically implemented using system calls and thus require the more time-consuming task of kernel intervention. In shared-memory systems, system calls are required only to establish shared-memory regions. Once shared memory is established, all accesses are treated as routine memory accesses, and no assistance from the kernel is required.

  한 번 공유 메모리 영역이 할당되고 나면, 운영체제의 도움 없이 일반적으로 메모리 접근하듯이 통신이 가능해지므로 메시지 방식에 비해 훨씬 빠르다.

CPU 스케줄링

CPU and I/O Bursts in Program Execution

• 계산량이 많은 작업 등은 CPU 사용시간이 길고, 사용자와 인터랙션을 많이 하는 프로세스는 I/O 작업 비중이 크다.
• CPU bound job vs I/O bound job으로 분류할 수 있다.
• 이렇게 여러 종류의 job이 섞여 있기 때문에 적절한 CPU 스케줄링이 필요하다.
  • Interative job에게 적절한 response 제공 요망
• CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler vs Dispatcher

• CPU Scheduler: Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
• Dispatcher: CPU 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. 이 과정을 context switch라고 한다.

두 자원 모두 운영체제 내부의 소프트웨어 자원이다.

CPU 스케줄링이 필요한 경우

1. 한 프로세스에서 작업 중에 I/O를 하러 System call을 발생시키고 CPU 제어권을 넘겨주는 경우
2. 한 프로세스에서 CPU를 사용하다가 Timer interrupt 등으로 인해 다른 프로세스에게 CPU 점유권이 넘어가는 경우
3. 한 프로세스가 I/O 작업 등을 기다리느라 waiting/blocked 상태에 있다가 완료되어 ready 상태가 된 경우
4. 프로세스가 작업을 마치고 종료되었을 때 다음 프로세스를 정해야 하는 경우

1, 4는 non-preemptive한 스케줄링이라고 부른다. 자기가 자진해서 CPU 점유권을 내놓았다는 말이다. 2,4는 프로세스가 가지고 있는 CPU를 강제로 뺏는 알고리즘으로, preemptive하다고 말한다.

CPU 스케줄링의 척도

• CPU utilization: CPU가 전체 시간 중 일한 시간의 비율 (실제 환경에서 40%~90%로 유지되는 것이 좋다.)
• Throughput: 단위 시간 동안 처리한 프로세스의 수(1 process/h ~ 10 process/sec부터 다양)
• Turnaround time: 메모리에 올라간 다음 완료될 때까지의 모든 시간의 합
• Waiting time: ready queue에서 기다린 시간의 합
• Response time: 프로세스가 ready queue에 들어올 때마다 제어권을 받을 때까지 기다린 시간

CPU 스케줄링 알고리즘

FCFS (First-Come First-Served)

만약 ready queue에 도착한 순서가 아래와 같다고 하자.

그럼, FCFS를 채택한 운영체제에서의 실행순서는 다음과 같다.

만약에, P1이 P2, P3보다 늦게 도착했다면 다음과 같아진다.

도착 순서에 따라 각 프로세스의 대기 시간이 매우 달라진다.
앞의 경우에는 P2, P3가 긴 처리시간의 P1을 기다리기 때문에 평균 waiting time이 길어지고,
뒤의 경우에는 다행히 짧은 시간의 P2, P3가 먼저 처리되므로 평균 waiting time이 짧아진다.

Convoy effect

There is a convoy effect as all the other processes wait for the one big process to get off the CPU. This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.

하나의 큰 프로세스가 CPU를 가지면 다른 프로세스들이 장시간 실행되지 못하는 현상이다.

SJF (Shortest-Job-First)

• 아, 그럼 짧은 프로세스부터 처리하는 것이 효과적이구나! 하는 생각으로 나온 알고리즘
• 각 프로세스의 다음번 CPU burst time을 가지고 가장 짧은 프로세스를 가장 먼저 스케줄
  (shortest-next-CPU-burst algorithm)
• 두 프로세스가 동일한 CPU burst time을 가진다면 어떻게 할까?
  • Tie braker로 FCFS를 사용
• Preemptive vs Non-Preemptive
  • 현재 CPU burst가 수행중이더라도 더 짧은 CPU burst time의 프로세스가 들어오면 빼앗을 것이냐 아니냐에 대한 문제
  • 빼앗는 형태의 선점형이 min. average waiting time 성능을 보장 (SRTF)

SRTF를 따르는 경우 다음과 같이 프로세스가 도착했다고 하자.

그럼, 도착 순서에 관계없이 가장 CPU burst time이 짧은 프로세스부터 실행된다.

• 그럼 무조건 SJF를 사용하면 되는건가?
  • 물론, 평균 waiting time이 최소가 되므로 좋은 알고리즘이다.
    • 그러나, 형평성이라는 운영체제의 또 다른 기능에서 어긋난다.
    • Burst time이 긴 프로세스는 계속 실행되지 않을 수 있다. (Starvation 문제)
  • 결정적으로, 각 프로세스의 다음 CPU burst time을 알기 힘들다는 어려움이 있다.
    • batch system의 Long-term scheduling에서는 작업의 길이를 사용자가 프로세스를 submit할 때 특정해주므로 판단이 쉽다. 그런 경우에는 유용하다.
    • 하지만, short-term scheduling에서는 알 방법이 없으므로 사용할 수 없는 알고리즘이다. 다만, optimal한 알고리즘의 기준이라는 의미가 있다.
    • 또한, 과거 CPU burst 데이터를 보고 estimation 하는 방법이 있다.

Priority Scheduling

• 어떤 우선순위를 놓고 우선순위가 높은(Priority Integer 값이 낮은) 프로세스부터 처리하는 알고리즘
• 역시 Preemptive vs nonpreemptive 로 나뉜다.
• SJF 또한 일종의 Priority scheduling이다.

우선순위 스케줄링을 하는 시스템에 프로세스가 다음과 같이 도착한다고 하자.

그럼, 우선순위가 높은(Priority 숫자값이 낮은) 프로세스부터 실행된다.

• 우선순위는 어떻게 정할까?
  • (운영체제) 내부 정의 우선순위 vs 외부 정의 우선순위
  • 내부 정의 우선순위: time limits, memory requirements, the number of open files, the ratio of average I/O burst to average CPU burst
  • 외부 정의 우선순위: 프로세스 중요도,
• 이 알고리즘에서도 우선순위가 낮은 프로세스의 Starvation 현상이 발생할 수 있다.
  • 우선순위가 낮은 프로세스가 기다리는 시간에 비례하여 aging을 통해 보정해줄 수 있다.

Round-Robin Scheduling

• 정해진 Time quantum(or time slice)마다 프로세스 간에 switch하면서 실행되는 스케줄링이다.
• 이 때, ready queue는 FIFO 식으로 구현되며, 도착 순서대로 일정 시간동안 실행되고 다시 줄을 서고를 반복한다.
• 단일 프로세스에 대해서는 모두 완료되고 나가는 시간이 길어지지만, 평균적으로 response time이 매우 빨라진다.
  • 즉, Interactive한 job과 CPU bound job이 섞인 heterogeneous한 상태에서 유리하다.
  • 어떤 프로세스도 (n-1)*(time quantum) 이상 기다리지 않는다.

예시를 보면, 아래와 같이 프로세스가 도착했다고 하자.

time quantum을 4ms로 가져가면, 다음과 같이 실행된다.

Multilevel Queue

• Ready queue를 여러 개로 분할한다.
  • foreground (interactive job)
  • background (batch - no human interaction)
• foreground job에 일방적인 우선순위를 부여하여 스케줄링할 수 있다.
  • stavation 문제를 해결하기 위해 각 큐에 적절히 분배할 수 있다.
• 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
  • foreground - RR
  • background - FCFS
    

실제 Windows system의 예시

Multilevel Feedback Queue

• Multilevel queue와 동일하지만, feedback을 통해 queue 간 이동이 가능하다.
• 하나의 예시는 다음과 같다.