감 1도 없는 개발자

감 1도 없는 개발자

여행을 꿈꾸는 개발자

운영체제 - 04

Updated:

강의

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

운영체제 - CPU 스케줄링

1. CPU 스케줄링의 이유

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

2. 프로세스의 특성 분류

2.1 I/O bound process

  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 프로세스
  • many short CPU bursts
  • 사람과 관계가 많은 프로세스 (ex: 키보드)

2.2 CPU bound process

  • 계산 위주의 프로세스

  • few very long CPU bursts

3. CPU 스케줄러 & Dispatcher

  • 스케줄러란 운영체제에 있는 한 기능(코드) 부분을 말한다.

3.1 CPU 스케줄러

  • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

3.2 Dispatcher

  • CPU 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 권한 준다.
  • 이 과정을 context switch(문맥 교환)이라고 한다.

3.3 프로세스 상태 변화

  1. Running 에서 Blocked(wait, sleep) (ex: I/O 요청하는 시스템 콜)
  2. Running에서 Ready (ex : time slicing으로 타이머 인터럽트)
  3. Blocked에서 Ready (ex : I/O 완료 후 인터럽트)
  4. Terminate

3.4 스케줄러 종류 나누는 기준

  • 프로세스 상태 변화에서 1,4 스케줄링은 nonpreemptive (강제로 빼앗지 않고 자진 반납)

  • 나머진 preemptive

  • 1의 경우 자기가 필요해서 운영체제에게 시스템 콜을 한 것이다.
  • 4또한 자기가 할일이 끝나서 프로세스를 종료하는 것
  • 그러나 2,3의 경우 자기가 필요한게 아니라 자신에게 할당된 시간이 끝나거나 1에서 block된 프로세스가 I/O가 끝나서 OS가 상태를 바꿔주는 것이다. 따라서 스스로 원한 것이 아닌 외부에서 상태에 영향을 주는 것이기 때문

3.4 스케쥴링 criteria (성능 척도)

  • Performance Index, Performance measure 라고도 부름

3.4.1 CPU utilization (이용률)

3.4.2 Throughput (처리량)

3.4.3 Turnaround time(소요시간, 반환시간)

  • CPU 사용시간, Ready Queue 대기시간 다 합친것

3.4.4 Waiting time(대기 시간)

  • Ready Queue에서 대기한 모든 시간을 합친 것 (응답시간을 모두 합친 것)

3.4.5 Response time(응답 시간)

  • 최초로(처음으로) Ready Queue에 들어와서 대기한 시간

3.5 스케줄링 종류

3.5.1 FCFS (First come First served)

  • 오는 대로 순서대로 CPU 할당
  • 굉장히 비효율적 (Convoy effect : 긴 프로세스 뒤에 짧은 것들이 와서 오래 기다리게 되는 효과)

3.5.2 SJF (Shortest-Job-First)

  • 가장 CPU 사용(CPU burst time)이 적은 process에서 먼저 CPU 할당

  • 두 가지 방식

    1. nonpreemptive : 일단 CPU를 잡으면 끝날 때까지 사용

    2. preemptive : 남은 CPU 사용시간보다 사용 중에 더 짧은 burst time 프로세스가 오면 빼앗음

      (SRTF: Shortest remaining time first 라고 부름)

  • 최소 대기 시간을 보장 (preemptive 방식이 경우 가장 최적(optimal)화 됨. 즉, 극단적 효율적)

  • 그러나 형평성(starvation)에 어긋남. CPU 사용률이 높은 프로세스는 받을 수가 없음
  • 또한 CPU burst time는 사실 알 수 가 없음
  • 예측만이 가능한데 어떻게 알 수 있냐면 이전에 사용했던 흔적을 통해서 추정. (exponential averaging)

3.5.3 Priority Scheduling

  • Priority = 다음 CPU burst 시간을 예측

  • 각 프로세스에 우선순위를 주는 것

  • preemptive : 우선 순위가 높으니 빼앗자. non : 일단 할당 받았으니 그냥 써
  • SJF는 일종의 priority 스케줄링
  • starvation가 문제
  • starvation 해결책 : 기다리는 시간만큼 우선순위를 높여줌

3.5.4 Round Robin (RR)

  • 각 프로세스마다 할당(time quantum)을 가짐
  • 할당 시간을 다 쓰면 다시 대기 큐에 간다.
  • 대기 큐(시간)가 크면 FCFS랑 같아지고
  • 대기 큐(시간)가 작으면 context switch(문맥교환) 오버헤드가 커진다.

  • 그래서 적절한 할당시간을 줘야 한다.

  • 일반적으로 SJF보다는 효율성(평균 대기 시간)은 떨어짐. 그러나 응답 시간은 좋음

3.5.5 Multilevel Queue

  • Ready Queue를 여러 개로 분할, 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • 각 큐에 대해서 우선 순위가 있다. 아래 큐일 수록 우선순위가 떨어짐
  • foreground : interactive –RR
  • background : batch - no human interaction –FCFS
  • 각 큐에 대한 스케쥴링을 주는 기준(방법)
    • Fixed priority 스케줄링
      • serve all from foreground then from background
      • starvation 가능성
    • Time slice
      • 각 큐에 CPU time을 적당한 비율로 할당
      • ex ) 80% to foreground in RR, 20% to background in FCFS
  • 프로세스가 어느 큐에 들어가면 그 큐에 계속 머물러야 한다.

3.5.6 Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동이 가능
  • Multilevel Queue도 starvation 가능성이 있음. 그래서 aging 우선순위로 해결 가능
  • 큐의 이동 기준
    • 큐의 수
    • 각 큐의 스케줄링 알고리즘
    • 프로세를 상위, 하위로 보내는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

3.5.7 Multiple-Processor 스케줄링

  • CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
3.5.7.1 Homogeneous processor인 경우
  • 큐에 한줄로 세워서 각 프로세서가 알아서 꺼내감
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우 문제가 복잡해짐
3.5.7.2 Load sharing
  • 일부 프로세서(processor)에 job(프로세스:process)이 몰리지 않도록 부하를 공유하는 메커니즘 필요

  • 한쪽 프로세서에 오래 걸리는 프로세스가 몰리면 비효율적이 될 수 있음

  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
3.5.7.3 Symmetric Multiprocessing(SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
3.5.7.4 Asymmetric multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

3.5.8 Real - Time 스케줄링

  • Real time 운영체제에서 사용하는 것. deadline이 있음
  • 현 강의에서는 그닥 중요하지 않음
  • 데드라인이 워낙 중요하기 때문에 그때 그때 정하는게 아니라 아싸리 좋은 CPU를 좋은거 씀
3.5.8.1 Hard real time systems
  • 정해진 시간에 반드시 끝나야 함
3.5.8.2 Soft real time systems
  • ex) 동영상

3.5.9 쓰레드 스케줄링

  • 스레드: 프로세스의 작업의 한 단위
3.5.9.1 local 스케줄링
  • 유저 레벨 스레드의 경우 사용자 수준의 스레드 라이브러리에 의해 어떤 스레드를 스케줄할지 결정
Global 스케줄링
  • 커널 레벨 스레드의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 스레드를 스케줄할지 결정

3.6 알고리즘 평가

3.6.1 Queueing models

  • 확률 분포로 주어지는 도착 평균과 서비스 평균등을 통해 각종 성능 인덱스 값을 계산
  • 예전 방식. 이론적

3.6.2 Implementatio(구현) & Measurement(성능 측정)

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

3.6.3 Simulation (모의 실현)

  • 알고리즘을 모의 프로그램으로 작성 후 trace(프로그램이 요청하는 값)를 입력으로 하여 결과 비교

  • trace의 신빙성 있게 만들어야 의미가 있다.

You may also enjoy