09. CPU 스케줄링: Chapter 5. CPU Scheduling (Part 1)

CPU 스케줄링

• CPU 스케줄러 : 다중 프로그램 운영체제의 기본
• 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.
  -> 멀티 프로그래밍의 목적 : CPU 이용률을 최대화하기 위해 항상
  실행 중인 프로세스를 가지게 하는데 있다.

CPU 스케줄러

• Ready Queue에 있는 프로세스 중에 CPU를 할당(allocate)할 수 있는 프로세스 선택

• 다음 프로세스를 어떻게 선택 할 것인지?

  → Linked List or Binary Tree
  → FIFO Queue, Priority Queue
  

선점 VS 비선점 스케줄링 (Preemptive and Non-preemptive Scheduling)

• CPU 스케줄링은 4가지 상황에서 발생할 수 있다.

  1. 프로세스가 Running에서 Waiting으로 전환될 때 (I/O 발생)
  2. 프로세스가 Running에서 Ready로 전환될 때 (인터럽트 발생)
  3. 프로세스가 Waiting에서 Ready로 전환될 때 (I/O 종료)
  4. 프로세스가 Terminate할 때

• 비선점 스케줄링

  • CPU가 프로세스에 할당되면 프로세스가 종료(ternimate), Waiting으로 전환 → 운영체제가 실행중인 프로세스로부터 CPU를 회수할 수 없다.(1, 4)
    
  • 필요한 Context Switch만 일어나므로 overhead가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 난다.

• 선점 스케줄링

  • 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽트나 시스템 호출 종료시에 더 높은 우선 순위 프로세스가 발생 → 운영체제가 실행중인 프로세스로부터 강제로 CPU를 회수할 수 있다. (2, 3)
    
  • CPU 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영 가능
  • 잦은 Context Switch가 발생해서 overhead가 커질 수 있다.

디스패처(Dispatcher)

• CPU 스케줄러가 선택한 프로세스에 CPU의 코어를 제어할 수 있는 권한을 주는 모듈입니다. (Context Switch를 해주는 모듈)
• 디스패처의 기능
  • 한 프로세스에서 다른 프로세스로 Context switch
  • user mode로 전환
  • user program의 활동 재개(resume)을 위해 프로세스를 적절한 위치로 이동(jump)
• 디스패처는 가능한 빨라야한다. → Context switch가 일어날 때 마다 호출
  • 디스패치 지연시간(Dispatcher latency) : 프로세스를 멈추고 다른 프로세스를 실행하는데 까지 걸리는 시간

스케줄링 기준

• CPU Utilization(이용률, %): CPU가 수행되는 비율
• Throughput(처리율, jobs/sec): 단위시간당 처리하는 작업의 수(처리량)
• Turnaround time(반환시간): 프로세스의 처음 시작 ~ 종료까지 걸린 시간(CPU, waiting, I/O 등 모든 시간을 포함)
  [반환시간은 짧을 수록 좋다]
• Waiting time(대기시간): CPU를 점유하기 위해서 ready queue에서 기다린 시간을 말한다.(다른 큐에서 대기한 시간은 제외)
• Response time(응답시간): 대화형 시스템에서 입력에 대한 반응 시간

참고 :

Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.

주니온TV@Youtube: 자세히 보면 유익한 코딩 채널