Chapter 11 CPU 스케줄링 - goorm-6th-Als/for_study_Algorithm GitHub Wiki

11-1 CPU 스케줄링 개요

프로세스 우선순위

모든 프로세스는 CPU를 필요로 합니다. CPU를 통해서 자원을 얻을 수 있기 때문인데
이러한 CPU 자원을 효율적으로 사용하기 위해 공정하고 합리적으로 배분하는 과정을 CPU 스케쥴링 이라고 합니다.
컴퓨터 성능과 직결되기에 굉장히 중요한 부분입니다.

만약 당장 시작해야되는 프로세스 A와 중요도가 상대적으로 떨어지는 프로세스B가 존재한다면 중요도가 높은 A부터 실행해야겠죠.
이러한 이유로 프로세스에는 우선순위가 존재합니다.

image


  • 대부분 입출력이 큰 프로세스가 우선순위가 높은편입니다.

  • 저희 사용자가 입력한것을 받아와야 다음 로직이나 프로세스가 진행하기 때문이죠.

  • 계산과 입출력 두가지 프로세스중에 계산의 프로세스가 더 우선순위가 높다면

  • 사용자는 입력하는데 답답함을 느낄겁니다. 계산이 아무리 빠르다 한들 입력시간에 딜레이가 생긴다면 불편하니까요.

  • 다만 CPU 자원을 소모하는 양도 서로 상이하기 때문에 우선순위가 달라집니다.

  • 입출력의 경우 자원소모가 작은편이고, 계산과 같은 복잡한 로직이라면 자원소모가 클테니까요.


간단한 입출력 프로세스의 경우 입출력 집중 프로세스 라고 부릅니다.
복잡한 연산이나 영상 재생 등의 CPU 자원이 큰 프로세스를 CPU 집중 프로세스라고 합니다.

정리하자면 입출력 집중은 실행보다는 대기상태에 오래 머무르게 될것이고, CPU 집중 프로세스는 실행 상태에 더 많이 존재하게 됩니다.

따라서 이런 이유로 우선순위가 적용되어야 합니다.
CPU가 올바르게 자원을 배분하도록 운영체제는 PCB에 우선순위를 기록해둡니다.

image

더 효율적이기 위해 운영체제는 프로세스를 큐로 관리한다.

다만 프로세스가 너무나 많기 때문에 하나하나 PCB에 접근하여 다음 순서의 프로세스를 찾는것은 비효율적입니다.
그래서 관리자인 운영체제는 프로세스를 큐로 관리합니다. 이 큐를 스케쥴링 큐로 구현하여 관리합니다. 프로세스가 알아서 줄서있으라고 명령하죠
단 일반적인 큐와 다르게 선입선출 방식을 채택하지 않아도 됩니다. 다양한 이유가 존재하지만 간단하게 설명하자면 유연하게 동작하기 위함입니다.

image image


스케쥴링 큐가 FIFO가 아니어도 되는 이유

  • 준비 큐는 반드시 FIFO가 아니어도 되는데 여러가지 스케쥴링 알고리즘이 존재하기 때문입니다.
  • 유연하게 동작하기 위함이며, 선입선출 큐, 우선순위 큐, 트리, 순서가 없는 연결리스트 등 다양하게 구현할 수 있습니다.

  • 응답 시간 최적화: 대화형 시스템에서 사용자의 요구에 빠르게 응답하는 것이 중요합니다. FIFO 방식은 짧은 작업이 긴 작업 뒤에 도착했을 때 오랫동안 대기해야 하는 문제(호위 효과)를 가질 수 있습니다. 이를 해결하기 위해, 짧은 작업을 우선 처리하는 최소 작업 우선(Shortest Job First, SJF) 같은 스케줄링 알고리즘을 사용할 수 있습니다.

  • 우선순위 기반 처리: 시스템에는 다양한 중요도와 우선순위를 가진 작업들이 있습니다. 중요한 작업이나 긴급한 작업을 먼저 처리해야 할 필요가 있을 때, 우선순위 기반 스케줄링이 사용됩니다. 이 방식은 중요한 작업이 대기열에서 더 빨리 처리될 수 있도록 합니다.

  • 공정성과 자원 공유: FIFO 방식은 모든 프로세스가 동일한 시간 동안 CPU를 사용한다는 가정하에 공정할 수 있지만, 실제로는 다양한 프로세스가 다른 양의 CPU 시간을 필요로 합니다. **라운드 로빈(Round Robin)**과 같은 시간 할당 방식은 각 프로세스가 정해진 시간 동안 CPU를 사용하도록 하여 공정성을 높이고 자원을 공유할 수 있게 합니다.

  • 스레드와 멀티태스킹: 현대의 운영 체제는 멀티태스킹과 멀티스레딩을 지원합니다. 다양한 스레드와 프로세스가 동시에 실행되며, 이들 간의 효율적인 자원 분배를 위해 선입선출보다 더 복잡한 스케줄링 전략이 필요할 수 있습니다.

  • 실시간 처리 요구 사항: 실시간 운영 체제에서는 시간 제약 조건을 만족시키는 것이 중요합니다. 실시간 작업은 종종 높은 우선순위를 가지며, 이러한 작업을 시간 내에 처리하기 위해 특별한 스케줄링 알고리즘이 필요할 수 있습니다.

  • 시스템 부하 조절: 시스템의 부하 상황에 따라 다른 스케줄링 전략이 필요할 수 있습니다. 시스템이 과부하 상태일 때는 특정 유형의 작업을 우선적으로 처리하거나, 반대로 시스템 부하를 줄이기 위해 일부 작업의 실행을 지연시킬 수 있습니다.


운영체제는 대부분의 자원을 큐로 관리하고 이 큐에는 종류가 존재합니다.

준비큐, 대기큐

image

  • 준비 큐 준비큐는 CPU를 이용하고 싶어서 서는 줄이라고 생각하시면 됩니다.

  • 대기 큐 대기 큐는 입출력 장치를 이용하기 위해 대기하는 줄입니다.

프로세스 과정

  1. 준비 상태에 있는 프로세스들의 PCB는 준비 큐 마지막에 삽입되어 차례를 기다립니다.
  2. 운영 체제는 PCB들이 큐에 삽입된 순서대로 하나씩 꺼내 실행하고, 우선순위를 고려해 먼저 실행해줍니다.
  3. 결국 줄을 선 순서보다는 우선순위가 더 중점입니다.

대기상태 예시 이미지

image

상태 다이어그램

image

  • 기존에 알고있었던 상태 다이어그램을 조금 더 고도화 할 수 있게 되었습니다.

image

선점형과 비선점형 스케쥴링

  • 마지막으로 선점형과 비선점형 스케쥴링에 대해 간단히 알아보겠습니다.
  • 말 그대로 남보다 앞서서 차지하는 선점형과 온전히 다른 프로세스가 끝날때까지 끼어들 수 없는 비선점형이 존재합니다.
  • 선점형의 경우 인터럽터를 걸어 빼앗아 오는 경우이죠, 다만 문맥교환이 많기에 오버헤드가 발생할 수 있습니다.
  • 비선점형의 경우 오버헤드가 적지만 당장 사용해야해도 기다려야하는 단점이 존재합니다.

스케쥴링 결정상황

  1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때
  2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(예: 인터럽트 발생)
  3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(예: I/O 종료 시)
  4. 프로세스가 종료할 때

2와 3 상황에서는 선점형이 전환되는 상황에서 뺏을 수 있겠죠,

image

부가 : 스케쥴링 알고리즘 정리

11-2 CPU 스케줄링 알고리즘

스케줄링 알고리즘

(CPU 스케줄링 알고리즘은 매우 다양하고, 운영체제 마다 다른 알고리즘을 사용. 달달 외울 필요 없음. 각 알고리즘의 작동 방식이나 장단점 정도 이해하면 됨.)

선입 선처리 스케줄링

  • FCFS(First Come First Served) 스케줄링
  • 단순히 준비 큐에 삽입된 순서대로 처리하는 비선점 스케줄링
  • 먼저 CPU를 요청한 프로세스 부터 CPU 할당

image

  • 단점 : 앞의 실행시간이 긴 프로세스들이 있을 수록 뒤의 프로세스들이 기다리는 시간이 매우 길어질 수 있음(호위 효과)

최단 작업 우선 스케줄링

  • SJF(Shortest Job First) 스케줄링

image

  • CPU 사용 시간이 긴 프로세스는 나중에 실행, 짧은 프로세스 먼저 실행 -> 호위 효과를 방지
  • 선점형(최소 잔여 우선 스케줄링), 비선점형 둘다 구현 가능. 보통은 비선점형으로 구현함

라운드 로빈 스케줄링

(라운드로빈은 CPU 스케줄링 뿐 아니라 CS 전반에서 사용)

  • 선입 선처리 스케줄링에 타임 슬라이스을 더한 개념.

  • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

  • 순서대로 프로세스를 디스패치 하지만 정해진 타임 슬라이스 만큼의 시간 동안만 실행을 제한, 돌아가며 CPU를 차례대로 이용하는 선점형 스케줄링

    -> 일단 큐에 삽입된 순서대로 프로세스들이 CPU를 사용하되 정해진 시간만큼만 이용 -> 정해진 시간을 모두 사용하였는데 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입(문맥교환)

image

-> 타임 슬라이스의 크기가 중요. 타임 슬라이스가 너무 크면 사실상 선입선처리와 비슷해져 호위효과가 생기고, 작으면 문맥교환으로 CPU에 부담이 되고 오버헤드가 발생할 수 있음

최소 잔여 시간 우선 스케줄링

  • SRT(Shortest Remaining Time) 스케줄링

  • 최단작업 우선(작업시간이 짧은 프로세스부터 처리) + 라운드 로빈(정해진 타임 슬라이스 만큼 돌아가며 사용)

  • 정해진 시간만큼 CPU를 이용하되, 다음으로 CPU를 사용할 프로세스로는 남은 작업 시간이 가장 적은 프로세스 부터

우선순위 스케줄링

  • 프로세스에 우선순위를 부여하고 우선순위가 높은 프로세스 부터 실행
  • 우선 순위가 같은 프로세스들은 선입 선처리로 스케줄링

image

  • 문제점 : 기아(starvation) 현상. 우선순위 높은 프로세스만 계속 실행, 낮은건 준비큐에 먼저 삽입돼도 실행 연기

-> aging기법 : 오랫동안 대기한 프로세스의 우선순위를 점차 높임

다단계 큐 스케줄링

image

  • Multilevel queue 스케줄링
  • 우선순위 스케줄링의 발전된 형태
  • 우선순위 별로 준비 큐를 여러개 사용
  • 우선순위가 높은 큐에 있는 프로세스들을 먼저 처리 -> 높은 큐가 비어 있으면 그 다음 순위 큐의 프로세스 처리.

큐를 여러개 두면 좋은 점 : 프로세스 유형별로 우선순위를 구분하는 것이 쉬워짐.

어떤 큐에는 입출력 집중 프로세스들, 어떤 큐에는 CPU집중 프로세스들, 어떤 큐에는 타임 슬라이스를 짧게 조정, 어떤 큐에는 선입 선처리로 어떤 큐에는 라운드로빈으로.. 큐별로 스케줄링을 달리 적용해서 프로세스를 유형별로 처리하기 쉬워짐.

  • 프로세스가 큐 간에 이동이 불가하여 우선순위가 낮은 큐는 기아현상이 발생할 수 있음.

다단계 피드백 큐 스케줄링

  • Multilevel feedback queue 스케줄링

  • 다단계 큐 스케줄링의 발전된 형태

  • 큐 간의 이동이 가능한 다단계 큐 스케줄링 (기아현상 해결)

  • 어떤 프로세스의 CPU 사용 시간이 길어서 실행이 안끝났다면, 우선순위가 낮아지고, 어떤 프로세스가 낮은 우선순위 큐에서 너무 오래 기다리면 우선순위를 높이는 방식

image

  • 자연스럽게 CPU를 많이 써야하는 CPU 집중 프로세스의 우선순위는 상대적으로 점차 낮아지고, CPU를 적게 써도 되는 입출력 집중 프로세스의 우선순위는 상대적으로 높아짐(높은 우선순위에서 실행이 끝나므로)

  • 에이징 기법 적용 가능 (어떤 프로세스는 CPU를 많이 이용해야하는데 낮은 우선순위에서 계속 기다릴 수 있으므로 우선순위를 점차 높여서 기아현상을 예방)

  • 구현이 쉽지 않지만 CPU 스케줄링 방식의 가장 일반적인 형태

⚠️ **GitHub.com Fallback** ⚠️