[OSTEP] 7장. 스케줄링: 개요(PPT)

---

☑️ 7. 스케줄링: 개요

해당 게시글은 운영체제 스터디 발표 내용을 정리해서 업로드했습니다.

• 스케줄링 정책은 CPU가 프로세스를 사용함에 있어서 중요한 영향을 끼친다.
  • 스케줄링 정책(Scheduling Policy) : CPU를 어떤 프로세스에게 할당할지 결정하는 정책
• 7장은 과거의 스케줄링 정책들을 설명하는 시간을 가진다.
• 스케줄링 정책을 효과적으로 설명하기 위해서 비현실적인 5가지의 워크로드(Work)를 정의한다.
  1. 모든 작업은 같은 시간 동안 실행된다.
  2. 모든 작업은 동시 도착한다.
  3. 작업이 시작되면 종료될 때까지 CPU에서 동작한다.
  4. 모든 작업은 CPU만 사용한다.
  5. 각 작업의 실행 시간은 사전에 알려져 있다.

 

• 추가로 반환 시간(Turnaround Time)에 대해서도 알아보자.
  • 반환 시간은 작업이 도착하고 완료까지 걸린 시간을 의미한다.
  • Tunaround = Completion - Arrival
  • 5초에 작업이 도착하고 10초에 작업이 완료되었다면, 반환 시간은 5초다.
    • 5 = 10 - 5

 

• 1초의 작업 시간을 가지는 작업 A, B, C, D가 동시에 도착했다고 가정하자.
• 선입 선출(First In First Out)은 먼저 도착한 작업을 우선적으로 처리한다. 
  • 평균 반환 시간은 2.5초가 된다.

 

• 1번 가정을 완화해 보자. 작업은 서로 다른 작업 시간을 가지게 된다.
• 작업 시간 5초를 가지는 작업 A가 먼저 실행된다고 하면, 평균 반환 시간은 6.5초로 증가한다.

 

• 이전과 같이 작업 시간이 긴 프로세스를 기다리게 되는 상황을 콘보이 현상(Convoy Effect)이라고 한다.

 

• 두 번째는 최단 작업 우선(Shortest Job First)이다. 짧은 실행 시간을 가진 작업을 먼저 처리하게 된다.
• 이러면 콘보이 현상을 완화할 수 있을 것 같다. 하지만 2번 가정을 완화해 보자.

 

• 작업 A가 먼저 도착하고 이후에 B, C, D가 도착하게 된다면 다시 콘보이 현상이 발생한다.

 

• 이번에는 최소 잔여시간 우선(Shortest Time-to-Completion First)이 기법은 짧은 작업 시간을 가진 작업을 최우선적으로 처리한다.
  • 이러한 작업이 되기 위해서 3번 가정도 완화하자.
• 작업 A가 CPU를 점유하고 있는 상황에서 작업 B, C, D가 들어온다.

 

• 그러면 CPU는 작업 A를 중단하고 작업 B, C, D를 모두 수행한 후에 다시 작업 A를 수행한다.
• 평균 반환 시간은 3.75로 준수한 성능을 보이게 된다.

 

• 이 시점에서 새로운 평가 기준을 추가하고 살펴보자. 
• 응답 시간(Response Time)은 작업이 도착하고 처음으로 작업이 처리될 때까지 걸린 시간을 의미한다.
• 최단 잔여시간 우선은 평균 응답 시간 1.5초가 걸리게 된다.

 

• 라운드 로빈(Round Robin)은 일정 시간 N초마다 작업을 전환하면서 실행하는 공정한 정책이다.
  • A 실행하고 B 실행하고 C 실행하고... 작업이 종료될 때까지 계속 반복한다.
• 이때, 일정 시간 N초를 타임 슬라이스(Time Slice) 혹은 스케줄링 퀀텀(Scheduling Quantum)이라고 부른다.
  • 포스팅에선 타임 슬라이스로 통일해서 지칭한다.

 

• 타임 슬라이스의 균형적인 설계는 매우 중요하다.
  • 타임 슬라이스의 시간이 긴 경우 : 프로세스의 응답 시간이 오래 걸리게 된다.
  • 타임 슬라이스의 시간이 적은 경우 : 성능에서 오버헤드가 발생한다.
    • 작업의 변환에는 컨텍스트 스위칭이 일어나기 때문이다.

 

• 컨텍스트 스위칭(Context Switching)은 CPU가 실행 중이던 프로세스 혹은 스레드의 상태를 저장하고 다른 프로세스, 스레드로 전환하는 과정을 의미한다.
  • 이때, 프로세스는 다시 실행될 수 있기 때문에 중단 정보를 백업하고 새로운 프로세스, 스레드의 정보도 복원해야 한다.
  • 또 컨텍스트 스위칭을 실시하면 기존 작업에서 유효하던 캐시 데이터가 무효화가 되기 때문에 일시적 성능 저하가 발생한다.
• 그렇기 때문에 타임 슬라이스를 적절하게 설계하는 것은 무척이나 중요한 요소다.

 

• 라운드 로빈은 응답 시간 부분에서는 굉장히 우수한 성능을 가지지만, 반환 시간에서는 처참한 성능을 보여준다.
• 그렇다면 라운드 로빈은 좋지 않은 스케줄링 기법인가?
  • 그것은 아니다.

 

• 우리는 응답 시간과 반환 시간 사이의 트레이드 오프(Trade-Off)를 고민해야 한다.
• 하나의 가치를 얻기 위해서 다른 가치를 포기하는 상황은 프로그래밍에서 자주 발생하는 일이다.

 

• 상황에 맞춰서 트레이드 오프 전략을 사용하자.

 

• 다시 기법으로 넘어와서 4번 가정을 완화해 본다.
• 모든 작업은 CPU만 사용하지 않는다. 앞으로는 입/출력 작업도 같이 병행된다.

 

• 입/출력을 받는 사이에 CPU는 비게 된다. CPU가 쉬는 시간을 가진다면 얼마나 비효율적인가.

 

• 라운드 로빈과 최소 잔여시간 우선을 동시에 사용해 보자. 
• 작업 A가 프로세스 입/출력을 받는 시간에는 작업 B가 실행되도록 해보자.
• 그렇다면 B 프로세스의 종료 시간을 기존 10초에서 8초까지 단축할 수 있게 된다. 
  • 작업 B의 작업 시간은 5초이나, PPT에서는 2초를 누락함.

 

• 이제 마지막 가정 5번에 대해서 생각해 보자.
• 이 모든 가정들이 비현실적임을 알려주는 가장 큰 내용이다.
• 각 작업의 실행 시간은 프로그래머도, 사용자도 알 수 없다.
  • 예측의 영역에서만 어렴풋이 짐작할 뿐이다.
  • 3.42717초 걸리는 작업이 있다는 것을 우리가 어떻게 알 수 있을까.
• 그렇기 때문에 우리가 세웠던 가정들을 무의미하고 비현실적이다.

 

• OSTEP의 8장은 멀티 레벨 피드백 큐(Multi-Level Feedback Queue)를 이야기한다.
• 멀티 레벨 피드백 큐는 작업의 실행 시간을 예측한다는 특징과 여러 정책을 혼합해서 사용한단 특징을 가진다.
• 이 내용은 다음 8장에서 알아보도록 하자.