[OS] CPU Scheduling

CPU and I/O Bursts

• CPU 버스트 : CPU만 연속적으로 사용
• I/O 버스트 : I/O를 실행하고 있을 때

프로그램은 CPU 버스트 + I/O 버스트 조합으로 구성되어 있지만, 프로그램마다 그 빈도는 다르다.

CPU 버스트 시간 분포

여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다.

• Interactive job 에게 적절한 response 제공 요망
• CPU와 I/O 장치 등 시스템 자원을 골구루 효율적으로 사용

프로세스의 특성 분류

• 프로세스는 특성에 따라 다음 두 가지로 나뉜다.
  • I/O-bound process
    • CPU를 잡고 계산하는 시간 보다 I/O에 많은 시간이 필요한 job
    • (many short CPU burst)
  • CPU-bound process
    • 계산 위주의 job
    • (few very long CPU bursts)

CPU Scheduler & Dispatcher

• CPU Scheduler
  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
• Dispatcher
  • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
  • 이 과정을 context switch 이라 한다.
• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
  1. Running → Blocked (I/O 요청 시스템 콜)
  2. Running → Ready (할당 시간 만료, timer interrupt)
  3. Blocked → Ready (I/O 완료후 인터럽트)
  4. Terminate
• 1번, 4번 스케줄링은 nonpreemptive(비선점 - 강제로 빼앗지 않고 자진반납)
• 2번, 3번 스케줄링은 preemptive(선점 - 강제로 배앗음)

Scheduling Algorithms

• FCFS(First-Come-First-Served)
• SJF(Shortest-Job-First)
• SRTF(Shortest-Remaining-Time-First)
• Priority Scheduling
• RR(Round Robin)
• Multilevel Queue
• Multilevel Feedback Queue

Scheduling Criteria(Performance Measure, 성능 척도)

• CPU utilization(이용률) - 시스템 입장 성능 척도
  • 가능한 CPU를 바쁘게 유지
• Throughput(처리량) - 시스템 입장 성능 척도
  • 주어진 시간에 얼마나 일을 처리하였는가
• Turnaround time(소요 시간, 반환 시간) - 프로그램 입장 성능 척도
  • 대기 시간 + 실행 시간
• Waiting time(대기 시간) - 프로그램 입장 성능 척도
  • 오로지 준비큐에 있는 시간 모두 합친 것
• Response time(응답 시간) - 프로그램 입장 성능 척도
  • 최초 CPU를 얻기 위해 대기한 시간

FCFS(First-Come First-Served)

먼저 온 순서대로 프로세스를 처리한다.

비선점형 스케줄링이다.

먼저 온 프로세스의 실행 시간이 평균 대기시간에 영향을 많이 끼친다.

Convoy effect : 긴 프로세스 떄문에 짧은 프로세스들이 오랫동안 실행 못하는 현상

SJF(Shortest-Job-First)

각 프로세스의 다음번 CPU burst time(사용 시간)을 가지고 스케줄링에 활용한다.

CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄 한다.

비선점형 방식과 선점형 방식이 있다.

• Nonpreemptive
  • 일단 CPU를 잡으면 CPU burst 가 완료될 때 까지 CPU를 선점(preemption) 당하지 않는다.
• Preemptive
  • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗긴다.
  • 위 방법을 Shortest-Remaining-Time-First(STRF)라고 부른다.

SJF는 모든 알고리즘 중 가장 짧은 평균 대기시간을 보장한다.

비선점형은 CPU 사용이 끝나면, 스케줄링을 진행하여 어떤 프로세스를 사용할지 정하고, 선점형은 준비큐에 프로세스가 들어올 때, 현재 실행하고 있는 프로세스의 남은 실행 시간과 비교한다.

SJF 알고리즘은 2가지 문제점이 존재한다.

• 다음 CPU Burst time을 알 수 없다.
• 추정만 가능하다. → 과거의 CPU Burst time 을 이용해서 추정한다.

Priority Scheduling

각 프로세스마다 우선순위 숫자가 할당된다.

높은 우선순위를 가진 프로세스에게 CPU를 할당한다. → 숫자가 작을수록 높은 우선순위이다.

선점형, 비선점형 구현이 모두 가능하다.

SJF는 일종의 Priority Scheduling 이다. 우선순위를 다음 CPU burst time 으로 잡는 것이다.

• Starvation(기아 현상) : 낮은 우선순위(실행 시간이 긴) 프로세스가 실행되지 않는 현상

SJF도 일종의 우선순위 스케줄링이기 때문에 같은 기아현상이 발생한다.

Starvation 해결 방법 → Aging 기법

• Aging 기법은 프로세스의 우선순위를 높여주는 방법이다.
• 즉 기아현상이 발생하지 않도록 해준다.

Round Robin(RR)

현대 운영체제의 스케줄링 알고리즘은 라운드 로빈에 기반한다.

각 프로세스는 동일한 크기와 할당 시간(time quantum)을 가진다.(일반적으로 10~100 milliseconds)

할당 시간이 지나면 프로세스는 선점(preempted) 당하고, ready queue의 제일 뒤에서 가서 다시 줄을 선다

n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit 인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

라운드 로빈 스케줄링은 응답 시간이 짧아진다.

• q 시간이 너무 크면 FCFS 스케줄링
• q 시간이 너무 짧으면 Context switching 비용이 커져 오버헤드가 커진다.

일반적으로 SJF 보다 평균 대기 시간은 길지만, 응답 시간은 더 짧아진다. → 여러 프로세스들이 시간을 조금씩 돌아가면서 쓰기 때문에 대기시간이 길어질 수도 있다.(모든 프로세스의 실행 시간이 같을 시에만), 기본적으로는 실행 시간을 정확히 모르기 때문에 효율적이다.

Multilevel Queue

• Ready Queue를 여러개로 분할
  • foreground(interactive)
  • backgroud(batch-no human interaction)
• 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
  • foreground - RR
  • background - FCFS
• 큐에 대한 스케줄링이 필요
  • Fixed Priority Scheduling
    • serve all from foreground then from background
    • Possibillity of starvation
  • Time slice
    • 각 큐에 CPU time을 적절한 비율로 할당
      • 예시 : 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능하다.
• 어떤 기준으로 정의할지
  • Queue의 수
  • 각 큐의 scheduling alogorithm
  • process를 상위 큐로 보내는 기준
  • process를 하위 큐로 내쫓는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
• 하위 큐 갈수록 time quantum 이 짧아지는 구조
  • 새로 들어오는 프로세스는 젤 상위 큐로 들어가고
  • CPU time quantum 의 시간을 다 쓰게 되면, 다음 큐로 내려간다.

Multiple-Processor Scheduling

• CPU가 여러 개인 경우 스케줄리은 더욱 복잡해진다.
• Homogeneous processor 인 경우
  • Queue를 한줄로 세워서 각 프로세스가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세스에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 복잡해진다.
• Load sharing
  • 일부 프로세스에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing(SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• Hard real-time systems
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링 해야한다.
• Soft real-time computing
  • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야함

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할지 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

• Queueing Models
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
• Implementation(구현) & Measurement(성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교
• Simulation(모의 실험)
  • 알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교

http://www.kocw.net/home/search/kemView.do?kemId=1046323