CPU Scheduling - hochan222/Everything-in-JavaScript GitHub Wiki

바로가기
바로가기

CPU and I/O Bursts in Program Execution

• 여러 종류의 job(=process)가 섞여 있기 때문에 CPU 스케줄링이 필요하다
  • interactive job에게 적절한 response 제공 요망
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

프로세스의 특성 분류

• 프로세스는 그 특성에 따라 다음 두가지로 나눔
  • I/O bound process
    • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
    • (many short CPU bursts)
  • 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(=강제로 뺴앗지 않고 자진 반납)
다른건 강제로 뺏음 preemptive

Scheduling Criteria

• CPU utilization (이용료)
  • keep the CPU as busy as possible
• Throughput (처리량)
  • of processes that complete their execution per time unit
• Turnaround time (소요시간, 반환시간)
  • amount of time to execute a particular process
• Waiting time (대기시간)
  • amount of time a process has been waiting in the ready queue
• Response time (응답 시간) (최초 CPU얻기까지 시간)
  • amount of time it takes from when a request was submitted until the first response is produced, not output

Scheduling algorithm

• FCFS (First-Come First-Served)
  • nonpreemptive
  • Convoy effect
• SJF (Shortest-Job-First)
  • 주어진 프로세스들에 대해 minimum average waiting time 보장
  • Nonpreemptive
    • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
  • Preemptive
    • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
    • 이 방법을 Shortest-Remaining-Time-First(SRTF)이라고도 부른다.
  • 문제
    • long process starvation (시간 긴거는 아에 못 쓸수 있음)
    • CPU burst time을 미리 알 수 없음
    • 과거의 CPU burst time을 이용해서 추정
• Priority Scheduling
  • Preemptive
  • Nonpreemptive
  • 문제
    • starvation 특정 프로세스 차별
  • => aging 오래 기달리게되면 우선순위를 높여주자.
• Round Robin (RR)
  • 각 프로세스는 동일한 크기와 할당 시간을 가짐.
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다
  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
  • Perfomance
  • q large => FCFS
  • q small => context switch 오버헤드
• Multilevel Queue
  • forground (interactive, RR)
  • background (batch - no human interaction, FCFS)
• Multilevel Feedback Queue
  • 프로세스가 다른 큐로 이동 가능
  • 에이징을 이와 같은 방식으로 구현할 수 있다.
• Multiple -Processor Scheduling
  • CPU가 여러개인 경우 스케줄링은 더욱 복잡해짐
  • Homogeneous processor인 경우
    • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘
    • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  • symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케줄링 결정
  • Asymmetric multiprocessing
    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
• Real-Time Scheduling
  • Hard real-time Scheduling
    • 반드시 정해진 시간안에 끝내도록 스케줄링 돼야함
  • Soft real-time Scheduling
    • 일반 프로세스에 비해 높은 priority를 갖게함
• Thread Scheduling
  • Local Scheduling
    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
    • 운영체제는 thread의 존재를 모름
  • Global Scheduling
    • Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation

• Queueing models
• Implementation(구현) & Measurement(성능 측정)
  • 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
• Simulation(모의 실험)
  • 알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교