CPU 스케줄링 정리

본 글은 반효경교수님의 운영체제 수업과 강의를 보고 필요한 부분만 정리되어있으며 제 생각이 적혀있어 정확하지 않을 수도 있습니다.(피드백 주세요:-))

스케줄링 알고리즘

<Quiz>
    1. CPU 스케줄링이 왜 필요할까요?
    2. 스케줄링이 필요한 상황은 언제일까요?
    3. 요즘 운영체제에선 선점형으로 스케줄링 알고리즘을 많이 사용하는데, 이유가 있을까요?
    4. 선점형으로 스케줄링을 하게 된다면 주의할 부분이 있을까요?
    5. 디스패처는 무슨 일을 할까요?
    6. 만약 디스패처 레이턴시가 길다고 하면 라운드 로빈의 어떤 설정을 수정하면 좋을까요?
    7. 스케줄링 성능 지표는 무엇이 있나요?
    8. 스케줄링 알고리즘 알고 있는게 뭐뭐 있나요?
    9. 콘보이 현상은 무엇일까요? 그리고 어디서 나타나나요?
    10. SJF의 단점은 무엇일까요?
    11. 우선순위 스케줄링 알고리즘의 단점은 무엇이고 보완하기 위한 방법이 있나요? 없다면 없다고 말하셔도 됩니다.
    12. 라운드 로빈 알고리즘에서 타임퀀텀이 길 때, 짧을 때 어떤 현상이 일어날까요?
    13. 라운드 로빈의 장점은 뭐라고 생각하세요?
    14. 멀티 레벨 큐에 레디 큐에 고정 우선순위 방식을 사용할 때, 어떤 문제점이 있을까요? 그리고 어떻게 해결할 수 있을까요?
    15. 멀티 레벨 큐와 멀티 피드백 큐를 비교하면서 설명해줄래요?
    16. 다중 처리기 스케줄링에서 고려 해야할만한 현상은 뭐가 있을까요?
    17. 실시간 스케줄링에서 어떤 스케줄링 알고리즘을 사용할까요?
    18. 스케줄링 알고리즘 성능을 평가하기 위한 방법은 무엇이 있나요?
    19. 스케줄링을 만들어본적이 있나요?
    20. 본인이 만약 라운드 로빈 스케줄링 알고리즘을 만든다고 하면 어떤 자료구조를 사용하실껀가요? 그 이유는 뭐죠?
    21. 프로세스 A 에서 커널 모드로 갔다가 다시 프로세스 A 로 CPU를 할당한다면 이를 컨텍스트 스위칭이라고 하나요?
    번외
    1. 메모리에 많은 프로세스가 올라와서 다음 프로세스가 못올라오는 상황일 때, 어떻게 처리 될까요?
    2. 우리는 왜 CPU 스케줄링에 대해서 배워야할까요?
    3. 만약 프로세스가 필요한 데이터가 메모리에 없다면 어떻게 될까요?
    4. SJF와 우선순위 스케줄링 알고리즘의 차이를 비교하면서 설명해주세요
    5. FCFS 알고리즘과 RR 알고리즘은 어떤 관계가 있을까요?
</Quiz>

CPU-IO 버스트 사이클

CPU-IO-Burst

출처 링크

프로세스는 CPU burstIO burst가 번갈아가면서 작업을 처리된다.

CPU Burst

CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계

또는

IO를 수행 후 다음 IO를 수행하기 까지 일련의 작업

IO Burst

IO요청이 발생해 커널에 의해 입출력 작업을 진행하는 단계

또는

CPU 버스트가 끝나고 다음 CPU 버스트 수행까지의 일련의 작업

CPU 바운드 프로세스

IO작업을 거의 수행하지 않아 CPU burst가 길게 나타나는 프로세스

IO 바운드 프로세스

IO요청이 빈번하게 일어나고 CPU burst가 짧게 나타나는 프로세스

주로 대화형 프로그램에 해당한다.

CPU 스케줄링이 필요한 이유

프로세스마다 CPU를 사용하는 패턴이 상이하기 때문에 효율적으로 CPU자원을 사용하기 위해서

CPU 스케줄러

CPU스케줄러는 준비 상태(레디큐)에 있는 프로세스들 중에서 어떤 프로세스에게 CPU를 사용하게 할 것인지 결정한다.

  • 레디 큐는 여러가지 자료구조로 만들어질 수 있다.(우선순위큐, 트리, 연결 리스트 등)
  • 레디 큐에는 각 프로세스들의 PCB로 연결되어있다.

스케줄링이 필요한 상황

  1. 실행 상태에서 프로세스가 필요에 의해 IO요청으로 인해서 블럭된 상태로 바뀌는 경우
  2. 실행 상태에서 프로세스가 종료되는 경우
  3. 실행 상태에서 타이머 인터럽트가 발생해서 준비 상태로 넘어가는 경우
  4. IO요청으로 블럭 상태에 있던 프로세스의 IO처리가 완료가 되어 인터럽트가 발생되어 기존에 작업되던 프로세스가 준비 상태로 바뀌는 경우

선점(preemptive)과 비선점(nonpreemptive)

비선점은 프로세스가 작업을 완료하는 동안까지는 CPU를 빼앗기지 않는 방식을 말한다.

선점은 비선점과 반대로 CPU를 사용하는 프로세스가 작업 도중 CPU를 빼앗기는 방식을 말한다.

윈도우, 맥, 리눅스 ,유닉스를 포함한 모든 최신 운영체제에서는 대부분 선점 스케줄링 알고리즘을 사용한다.

위에서 말한 1과 2번은 비선점 방식이며, 3과 4번은 선점 방식이다.

선점 방식은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 상태에 들어가게 되면 데이터의 일관성이 무너질 수 있다는 점으로 데이터 동기화를 신경 써줘야한다.

뒤에 동기 문제를 다루는 파트에서 보기로 하자.(mutex)

디스패처

CPU스케줄러에 의해 레디큐에 있던 프로세스를 선택되었다면 기존에 작업하던 프로세스에서 새로운 프로세스로 넘어가는 작업이 필요하다.

이를 디스패처라는 커널 모듈이 해주고 있다.

디스패처는

  1. 현재 수행중이였던 프로세스의 컨텍스트(문맥)을 PCB에 저장을 하고, 새롭게 선택된 프로세스의 컨텍스트(문맥)을 PCB에서 가져온다(문맥 복원 작업)
  2. 커널 모드에서 사용자 모드로 전환하여 프로그램에게 CPU 제어권을 넘기게 되며,
  3. 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동시켜준다.

디스패처 지연시간

기존 프로세스에서 새로운 프로세스로 전환하는 시간을 말한다.

지연시간은 컨텍스트 스위칭으로 인한 오버헤드에 해당된다.

그래서 빈번한 컨텍스트 스위칭이 발생하게 된다면, 성능상 이슈가 발생할 수도 있다.

스케줄링 성능 평가 지표

  1. CPU활용도(CPU utilization)

    • 전체 시간 중 CPU가 명령어를 수행한 시간의 비율
    • CPU 휴먼 상태를 최대한 줄이는 것이 중요한 목표 중 하나
  2. 처리량(throughput)

    • 주어진 시간 동안 CPU burst를 완료한 프로세스의 수
  3. 소요시간(turnaround time)

    • CPU요청 시점부터 시작해서 해당 CPU burst가 끝날 때까지 걸린 시간
  4. 대기시간(waiting time)

    • CPU burst 시간 동안 기다린 총합
    • 처음 이해하기 어려웠던 부분인데, 작업하려고 들어온 양을 다 처리하기 위해서 기다린 시간을 의미
  5. 응답시간(response time)

    • CPU요청 시점부터 처음으로 CPU를 얻을때까지의 시간

소요시간은 해당 CPU burst 시간까지 포함이며, 응답시간은 미포함이다.

그리고

CPU이용률과 처리량을 최대화하고, 처리 시간, 대기 시간, 응답 시간을 최소화하는 것이 바람직하다.

스케줄링 알고리즘

FCFS(Frist Come First Served)

프로세스가 레드 큐에 도착한 순서대로 CPU를 할당하는 방식

제일 이해하기 쉬운 스케줄링 알고리즘이다.

비선점형이다.

대화식 시스템에는 적합하지 않다.

FCFS의 평균 대기시간은 레디 큐에 들어온 프로세스의 버스트타임에 따라서 다르게 나타난다.

2가지 예시

  1. 긴 버스트타임을 가지고 있는 프로세스가 처음 들어온 뒤 짧은 버스트타임을 가지는 프로세스들이 들어왔다고 가정했을 때

    • 먼저 도착한 긴 프로세스를 처리할 때, 뒤에 있는 짧은 프로세스들은 오랜시간 동안 대기하게 된다.- 이에 따라 평균 대기시간이 길어짐을 볼 수 있다.
  2. 짧은 버스트타임의 프로세스들이 있고 맨 뒤에 긴 버스트타임의 프로세스로 처리하게 된다면

    • 평균 대기시간은 첫번째 경우보다 짧아짐을 볼 수 있다.

즉, 괜히 앞에 버스트타임이 긴 프로세스 때문에 뒤에 있는 프로세스들에게 영향을 미친다.

이렇게 버스트타임이 짧은 작업들이 긴 프로세스들보다 늦게 레디큐에 왔다는 이유로 오랜 시간을 기다리게 되는 현상을 콘보이(Convoy effect)현상 이라고 한다.

정리

장점

  • 스케줄링의 이해와 구현이 단순함
  • 레디 큐에 있는 프로세스 모두 실행되기 때문에 기아가 없음

단점

  • 대화식 프로세스엔 부적합함
  • 먼저 긴 프로세스가 들어오면 대기 시간이 늘어남
  • 콘보이 현상이 발생함

SJF(Shortest Job First)

버스트타임이 짧은 프로세스에게 먼저 CPU를 할당하는 방식이다.

SJF는 평균 대기 시간이 가장 짧은 알고리즘으로 최적의 알고리즘으로 불리온다.

하지만, 현실적으로 어떤 프로세스의 버스트타임이 짧은 프로세스인지 파악하기 어려워 구현하기가 어렵다.

그래서 이에 대한 대응으로 CPU burst타임을 예측을 하는 방법을 생각해볼 수 있다.

이전 CPU burst들의 길이를 지수평균을 내서 예측한다.

선점과 비선점

SJF는 선점과 비선점 두가지 방식으로 나눠볼 수 있다.

선점 방식 같은 경우 현재 상태에서 버스트타임이 더 짧은게 있다면 기존에 처리하고 있던 프로세스의 CPU를 빼앗고 더 짧은 프로세스에게 CPU를 주게 된다.

선점의 방식 경우 SRF(Shortest Remaining Time First) 또는 SRTF라고 불린다.

참고로 만약 동일한 시간에 준비 큐에 동일한 버스트타임을 가진 프로세스들이 동시에 온다면 선점 비선점은 동일하게 처리하게 된다.

정리

장점

  • 짧은 작업을 먼저 신속하게 처리함으로 평균 대기시간이 짧음

단점

  • 아무래도 버스트타임이 짧은 프로세스에게 우선권이 부여되어 처리되기 때문에, 버스트타임이 긴 프로세스에게는 기회가 안올 수도 있다. 이런 현상을 기아(starvation)현상이라고 한다.
  • 버스트타임을 예측하기가 어렵기 때문에 사실 실용적이지 못함

우선순위 스케줄링(Priority)

SJF와 비슷한 방식이다.(버스트타임 <-> 우선순위)

우선순위에 따라서 프로세스를 처리하는 방식이다.

우선순위 정하는 방법

우선순위를 정하는 방법은 크게 내부적인 요소와 외부적인 요소로 나뉜다.

내부적인 요소로: 메모리 요구, 열린 파일의 수, 평균 IO버스트의 평균 CPU 버스트에 대한 비율, 시간 제한

외부적인 요소로 : 프로세스의 중요성, 컴퓨터 사용을 위해 지불되는 비용의 유형과 양, 정치적인 요소

선점과 비선점

SJF와 동일하게 선점과 비선점 방식을 사용하고 있다.

기아현상 보완

노잉 기법을 사용하는 방법이 있다.

노잉 기법은 기다리는 시간이 길어지면 해당 프로세스에게 우선순위를 높혀주는 기법이다.

정리

장점

  • 우선순위에 따라 프로세스 처리가 가능하다는 점

단점

  • SJF와 동일하게, 기아 현상이 발생함

라운드 로빈(Round Robin)

타임퀀텀 또는 타임슬라이스라는 제한시간 초를 가지고 있다.

보통 레디 큐를 원형 큐로 설계한다.

타임퀀텀 만큼 프로세스가 CPU를 사용하게 해주고 해당 시간이 넘어가면 작업 중인 프로세스는 CPU를 빼았고 레디큐로 넘겨버린다.

즉, 타임퀀텀 2초에 10초의 시간을 쓰는 프로세스가 5개가 있다고 하면 2초 쓰고 다음 프로세스로 넘어가고 2초쓰고 다음 프로세스로 넘어간다.

물론, 타임퀀텀보다 적은 버스트타임이면 그 전에 끝내고 다음 프로세스에게 CPU를 할당한다.

라운드로빈은 모든 프로세스의 다음 CPU를 할당 받는 최대 시간을 알 수 있다.

프로세스 개수가 n이라고 하고, 타임 퀀텀이 q라고 한다면 (n-1)q 시간 이내로 CPU는 무조건 할당받게 되어있다.

라운드로빈은 빠른 응답을 제공해주기 때문에 대화형 프로세스에게 적합하다.

만약에 버스트타임에 따라서 소요 시간이 비례하기 때문에 일부 공정하다고 볼 수 있다.

기본 목적

버스트타임이 짧은 프로세스에게는 빨리 CPU를 제공해줌과 긴 프로세스가 불이익을 당하지 않도록 하기 위함이다.

타임퀀텀

타임퀀텀 시간을 길게 잡을 때랑 짧게 잡을 때 성능상 차이가 있다.

길게 잡는다고 하면, 라운드 로빈은 FCFS와 비슷한 결과를 나타낼 수 있다.

예를들어보자.

타임퀀텀이 100초라고 가정하고,

프로세스 5개가 각각 5초의 부스트타임을 가진다고 한다면 그대로 프로세스 5개가 FCFS처럼 작동할 것이다.

반대로!

짧게 잡는다면,

프로세스에게 CPU를 넘겨주는 작업이 늘어나게 된다. 즉, 컨텍스트 스위칭이 많이 일어나게 된다.

컨텍스트 스위칭은 오버헤드를 초래한다.

그래서 오버헤드가 커지게 된다.

그리고

총 처리 시간은 타임 퀀텀 크기에 따라서 좌우가 된다. 그리고 타임 퀀턴의 크기가 증가하더라도 반드시 개선되지는 않는다.

  • 실제로 대부분의 현대 운영체제들은 타임 퀀텀을 10에서 100밀리초로 할당하고 있다고 한다.
  • 보통 컨텍스트 스윙칭까지 10마이크로초 미만이라고 한다.

정리

장점

  • 모든 프로세스가 공정하게 작업이 부여되며, 기아가 발생하지 않음
  • 짧은 응답시간을 제공한다.
  • 최악의 응답시간을 알 수가 있다.

단점

  • 타임퀀텀을 잘 조절해야한다.
  • 하드웨어 타이머가 필요하다.
  • 평균 처리 시간이 높다. 왜냐하면 타임 퀀텀만큼 프로세스를 실행하게 되기 때문이다.

멀티 레벨 큐(Multi Level Queue)

레디 큐를 여러 개로 분할하여 관리하는 스케줄링 기법이다.

큐가 여러 개 있으니, 프로세스가 들어왔을 때, 어떤 큐에게 보내야되는지 결정하는 메커니즘이 필요하다.

일반적으로는 프로세스 성격에 따라 관리한다.

빠른 응답을 필요로 하는 대화형 작업과 그렇지 않는 작업으로 나눠서 프로세스를 레디큐에 프로세스를 넣는다.

전자를 전위 큐, 후자를 후위 큐라고 불리기도 한다.

전위 큐에서는 응답 시간이 빠르다는 점으로 보통 라운드 로빈 알고리즘을 사용한다.

후위 큐에서는 응답 시간보다 계산 위주이기 때문에 FCFS 알고리즘을 사용해 컨텍스트 스위칭을 줄여 오버헤드를 줄이도록 한다.

보통의 우선순위

  1. 실시간 프로세스
  2. 시스템 프로세스
  3. 대화형 프로세스
  4. 배치 프로세스

각 큐별로 스케줄링

큐 안에서의 스케줄링도 외에도 각 큐별로 스케줄링도 필요하다.

고정 우선순위 방식을 사용할 수가 있다.

고정 우선순위 방식은 각 큐에 우선순위를 고정시켜 놓는다.

그리고 높은 우선순위 큐에 프로세스가 있다면 우선적으로 처리하고, 비어있다면 다음 우선순위가 높은 큐를 처리하는 방식이다.

하지만 이런 방식을 취하게 되면, 우선순위가 낮은 큐는 처리가 안될 위험이 있다.(기아현상)

그래서

타임 슬라이드 방식을 사용할 수 있다.

각 큐별로 CPU사용 시간을 비율로 할당하여 제공한다.

예로 전위 큐 80% 후위 큐 20%를 주어서 기아현상을 방지할 수 있다.

정리

장점

  • 응답이 빠름

단점

  • 여러 개의 준비큐와 스케줄링 알고리즘 때문에 추가 오버 헤드가 발생함
  • 우선순위가 낮은 프로세스는 기아를 겪을 수도 있음

멀티 레벨 피드백 큐(Multi Level Feedback Queue)

이 또한 여러 개의 큐로 구성되어있다.

기존에는 프로세스들이 영구적으로 하나의 큐에만 할당되었지만

멀티 레벨 피드백 큐에서는 프로세스가 다른 큐로도 이동이 가능하다는 것이다.

하지만 큐의 개수나 각 큐를 위한 스케줄링 알고리즘

프로세스 이동 방법 등을 신경쓰며 설계해야하기 때문에 복잡한 알고리즘이다.

정리

장점

  • 프로세스의 다양한 성격을 반영해 구현할 수 있다는 장점이 있다.

    • 예로, 노잉 기법을 구현할 수도 있다.
  • 우선순위가 낮은 큐에서 오래 기다린다면 우선순위가 높은 큐로 프로세스를 이동시켜서 기아 문제를 해결 할 수 있다.

단점

  • 설계와 구현이 매우 복잡하다.

작업 시간이 빠른 프로세스는 더 빠른 서비스가 가능하도록 제공하고, 작업이 긴 프로세스는 문맥 교환 없이 CPU작업에만 열중할 수 있도록 FCFS 방식을 채택하도록 만들 수도 있다.

다중 처리기 스케줄링

CPU가 여러 개인 시스템을 다중 처리기 시스템이라고 한다.

여러 개의 CPU가 사용 가능하니, 부하를 공유할 수 있다.

여러 CPU가 레디 큐에있는 프로세스를 가져다가 처리하는 방식이다.

알아서 CPU가 처리해주면 좋겟지만,

어떤 프로세스는 특정 CPU에서만 수행되어야 한다고 할때, 문제가 생길 수 있다.

또는 한쪽 CPU에게만 작업이 편중되는 현상이 일어날 수도 있다.

이를 방지하기 위해서 CPU별로 부하를 적절히 분산되도록 부하 분산 매커니즘이 필요하게 된다.

대칭형, 비대칭형 다중 처리

대칭형은 각 CPU가 알아서 스케줄링을 결정하는 방식이며, 비대칭형은 한 CPU가 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 그에 따르는 방식이다.

실시간 스케줄링

쉽게 말해 데드라인이 있는 스케줄링이다.

경성과 연성 실시간 시스템으로 분류할 수 있다.

경성은 미사일 발사라던지, 원자로 제어 등 시간을 꼭 데드라인 시간에 맞게 지켜야하는 시스템을 말한다. 그렇지 않으면 시스템에 큰 문제가 발생하는 시스템이다.

연성은 데드라인은 있지만, 데드라인을 지키지 않아도 큰 문제는 아닌 시스템이다. 보통 VOD나 스트리밍들이 예로 있다.

EDF(Earlist Deadline First)

데드라인이 얼마 남지 않은 요청을 먼저 처리하는 스케줄링이다.

일반 프로세스보다 우선순위가 높게 할당해서 먼저 처리된다.

스케줄링 알고리즘 성능 평가

스케줄링 알고리즘 성능을 평가하는 방법으로 결정론적 모델링, 큐잉모델, 시뮬레이션, 구현 등이 있다.

결정론적 모델링(deterministic)

평가 방법으로 분석적 평가가 있는데

분석적 평가는 작업에 부하를 주어 알고리즘의 성능을 평가하는 방법이다.

분석적 평가 유형 중 결정론적 모델링이 있다.

사전에 정의된 특정한 작업 부하를 가지고, 각 알고리즘의 성능을 평가하는 방법이다.

결정론적 모델링은 단순하고 빠르다는 장점이 있다.

하지만, 정확한 값을 원하면 정확한 입력이 필요하고, 응답 결과도 해당 입력 데이터에 대한 경우에만 적용된다.

그래서 주로 스케줄링 알고리즘을 설명하고 예를 제공하는데 사용한다고 한다.

큐잉 모델

어렵네..

내 언어로 해석하자면..

CPU와 IO burst의 분포의 데이터를 가지고 특정 CPU 버스트의 확률을 나타내는 수학적인 공식을 만들 수가 있다.

그 공식과 프로세스들이 시스템에 도착하는 시간의 분포를 통해 평균 처리량, 이용률, 대기 시간을 계산하는 것이 가능하다는 의미로 이해함!

간단하게 프로세스들의 도착 시간과 CPU 처리율의 입력값을 통해 확률 분포와 같은 수학을 이용하여 각종 성능 지표(평균 처리량, 이용률, 대기 시간)를 구하는 방식이다.

큐잉 모델은 각 스케줄링 알고리즘을 비교할 때 유용하지만, 사용 가능한 알고리즘에 제한이 있고 분포의 부류가 상당히 제한되어있으며, 복잡한 알고리즘은 수학적 분석이 어렵다고 한다.

시뮬레이션

실제 시스템에 구현해서 수행하는 것이 아니라 가상으로 CPU 스케줄링 프로그램을 통해서 입력값에 따라 결과를 수집하고 통계를 내어 측정하는 방식이다.

구현

실제로 시스템에 CPU 스케줄링을 적용하여 실행 시간을 측정하는 방법이다.

하지만, 비용이 많이 든다.


@kwonmory
성장을 위해 노력하고 있는 모리입니다.

깃허브