[week08] KOCW 운영체제(반효경교수님) - CPU Scheduling 2

CPU Scheduling 2

Multilevel Queue

Ready queue를 여러 개로 분할

• foreground(interactive)
• background(batch - no human interaction)

각 큐는 독립적인 스케줄링 알고리즘을 가짐

• foreground - RR(Round Robin)

• background - FCFS

  • 응답시간이 빠르다고 좋을게 없다. 어짜피 사람이랑 소통 x
  • context switch overhead를 줄이기 위해 FCFS를 사용하는 것도 방법

큐에 대한 스케줄링 필요

• Fixed priority scheduling
  • serve all from foreground then from background
  • starvation 가능성 존재
• Time slice
  • 각 큐에 CPU time을 적절한 비율로 할당
  • ex) 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

그림에서 quantum은 RR의 할당시간을 말한다.

CPU 사용시간이 짧은 process에게 우선순위를 많이 주는 방식

프로세스가 다른 큐로 이동 가능

Aging(노화)을 이와 같은 방식으로 구현 가능

Multilevel-feedback-queue scheduler를 정의하는 파라미터

• Queue의 수
• 각 큐의 scheduling algorithm
• process를 상위 큐로 보내는 기준
• process를 하위 큐로 내쫓는 기준
• 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

이제부터 특이한 case의 scheduling을 배워보자.

Multiple-Processor Scheduling(CPU가 여러개인 경우)

Homogeneous processor인 경우

• Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.

Load sharing

• 일부 CPU(프로세서)에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요

Symmetric Multiprocessing(SMP)

• 각 프로세서가 각자 알아서 스케줄링 결정
• 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

Hard real-time systems

• 정해진 시간 안에 반드시 끝내도록 스케줄링 해야 함

Soft real-time computing

• 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

Thread Scheduling

Local Scheduling

• 사용자 프로세스가 직접 thread 관리, 운영체제는 thread의 존재 모름
• User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정

Global Scheduling

• 운영체제가 thread의 존재를 알고 있음
• Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

Queueing models

• 이론적인 방법

Implementation(구현) & Measurement(성능 측정)

• 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능측정 비교

Simulation(모의 실험)

• 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
  • trace: 시뮬레이션 프로그램의 input으로 들어갈 data