2020-11-3 운영체제 스케줄링 (강의정리)

CPU Scheduling

  • 프로세스는 특성에 따라 I/O-bound process와 CPU-bound process로 나눈다.
  • I/O-bound process : CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 process(many short CPU burst)
  • CPU-bound process : 계산 위주의 job(few very long CPU burst)
  • 프로그램은 cpu burst와 i/o burst의 연속이다.

  • cpu bound job은 빈도는 작지만 한번 쓰면 오래쓰기 때문에 빈도가 작은것이고, i/o bound는 빈도는 많지만 시간을 짧게 쓰기때문에 빈도가 많은거다.
  • 여러종류의 job(process)가 섞여 있기 때문에 CPU 스케줄링이 필요하다.
  • 사용자와 밀접한 Interactive job에 적절하게 우선순위를 준다.
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

  • CPU Scheduler : Ready 상태의 프로세스 중에서 CPU를 줄 프로세스를 고른다.
  • Dispatcher : CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. => context switching
  • CPU 스케줄링이 필요한 경우는 프로세스에 상태변화가 있는 경우다.
    • Running -> Blocked(ex. I/O 요청하는 시스템콜)
    • Running -> Ready(할당시간 만료로 timer interrupt)
    • Blocked -> Ready(I/O 완료 후 인터럽트)
    • Terminate
  • Running-> Blocked, Terminate의 스케줄링은 nonpreemptive(강제로 빼앗지 않고 자진 반납)
  • 다른경우들은 premmptive(강제로 빼앗는다)

Scheduling Criteria(성능척도)

  • CPU utilization(이용률) : 되도록 CPU가 일을 많이해야한다.
  • Throughput(처리량) : 시간당 처리량이 높아야한다.
  • Turnaround time(소요시간, 반환시간) : 각 프로세스 실행 시간의 합
  • Waiting time(대기 시간) : 대기큐에서 기다리는 시간. Preemtive한 job에서도 cpu를 완전히 선점하는게 아니라 중간에 뺏겨서 대기큐로 들어갔다 cpu를 썼다를 반복한다. 대기큐에 들어와서 작업이 완료될때까지 총대기시간을 waiting time이라고 한다.
  • Response time(응답 시간) : 대기큐에서 최초의 CPU 얻기까지 기다리는 시간. 처음으로 CPU를 얻는 시간이 사용자 체감에서 중요해서?

Scheduling Algorithm

FCFS(First-Come First-Served)

  • 비선점형 스케쥴링이다. => Non Preemptive algorithm
  • 먼저 온 순서대로 처리.

  • 효율적인 알고리즘은 아니다. burst time이 가장 긴 P1때문에 P2, P3, P4의 대기시간이 너무 길어져서 평균시간이 매우길어진다.
  • Convoy Effect : 긴 프로세스가 도착해서 짧은 프로세스들이 오래 기다리는 현상

Shortest-Job-First(SJF)

  • CPU Burst-Time이 가장 짧은 프로세스를 제일 먼저 스케줄링한다.
  • SJF에서도 2가지 버전 존재한다.
  • Non-preemtive : 일단 CPU를 선점하면 cpu burst가 완료될때까지 CPU를 선점당하지 않는다. CPU 선점이 끝나면 대기큐에 존재하는 프로세스들 중에 CPU Burst time이 가장 짧은게 다음에 사용된다.
    • 처음에는 P1이 가장 먼저 도착했기때문에 P1이 CPU를 사용하다가 P2가 도착했을때 burst time이 짧기때문에 P1이 뒤로 밀린다.
  • preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지고 있는 새로운 프로세스가 도착하면 CPU를 뺏긴다. => Shortest-Remaining-Time-First(SRTF)라고 부른다.
  • 주어진 프로세스들에 대해 mimimum average waiting time을 보장
  • 배치 시스템에서 사용된다.
  • 문제점
    • Starvation : 극단적으로 CPU Burst time이 짧은걸 선호한다. CPU Burst time이 엄청 긴 프로세스들은 영원히 CPU 할당을 못받을 수도 있다.
    • cpu 사용시간을 미리 알 수 없고 과거 CPU 사용을 보고서 예측한다.

Priority scheduling

  • 우선순위가 높은 프로세스에게 CPU를 준다. 우선순위를 정수로 표현하고 보통은 우선순위가 가장 높은게 0에 가깝다.
  • Preemptive, non-Preemptive 버전이 존재한다.
  • SJF도 일종의 Priority Scheduling이다.
  • starvation문제를 해결하기 위해 aging기법을 도입
  • Aging : 우선순위가 낮은 프로세스라도 오래기다리면 우선순위를 높여준다. starvation 방지

Round Robin(RR)

  • 현대 시스템에서는 대부분 라운드로빈 방식에 기반했다.
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다. 일반적으로 10-100 ms => 응답시간이 빠르다
  • 할당 시간이 지나면 프로세스는 선점당하고 대기큐의 제일뒤에 간다.
  • n개의 프로세스가 대기큐에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다. => **어떤 프로세스도 (n-1) q time unit이상 기다리지 않는다.
  • 성능
    • q large => FCFS와 비슷한 알고리즘이 된다.
    • q small => 라운드로빈 철학에서 보면 좋지만 context switch가 빈번하게 일어나서 오버헤드가 크다.
  • 일반적으로 SJF보다 average turnaround time이 길지만 reponse time은 더 짧다.
  • CPU Burst time이 다 다르면 Round Robin 방식이 좋지만 Burst time이 거의 비슷하면 Round Robin 방식이 비효율적이다.

Reference

  • https://kojunhee.github.io/image/os100602.png => cpu burst
  • https://www.studytonight.com/operating-system/images/fcfs.png => FCFS
  • https://www.studytonight.com/operating-system/images/priority-scheduling.png => Priority scheduling
  • https://www.studytonight.com/operating-system/images/round-robin.png => Round Robin
Written on November 3, 2020