[운영체제] 5. CPU Scheduling

do_large·2021년 2월 6일
0

운영체제강의

목록 보기
5/8
post-thumbnail

CPU-burst Time의 분포


세로축은 빈도, 가로축은 burst duration을 의미함.

프로세스의 특성 분류

프로세스는 그 특성에 따라 다음 두가지로 나눔(위에서 봤던 내용임)

  • I/O-bound process
    - CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job(many short CPU bursts)
    - cpu를 짧게쓰고 중간에 I/O가 끼어드는 종류의 작업
  • CPU-bound process
    - 계산 위주의 job(few very long CPU bursts)
    - cpu를 오래쓰는 종류의 작업

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

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

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(비선점형. 강제로 빼앗지않고 자진 반납)
All other schedulling is preemptive(선점형. 강제로 빼앗음)

Scheduling Algorithms

성능척도(Scheduling Criteria)

스케줄링 알고리즘의 성능을 평가하는 방법

  1. 시스템 입장에서 성능척도(CPU하나로 최대한 많은일을 하는게 좋은거)
    • CPU utilization(이용률)
      전체시간중에서 CPU가 놀지않고 일한 시간
      keep live CPU as busy as possible
    • Throughput(처리량)
      주어진시간동안 얼마만큼의 양을 처리했느냐
  2. 프로그램(고객)입장에서 성능척도(CPU를 빨리얻어서 빨리처리하면 좋은거)
    • Turnaround time(소요시간, 반환시간)
      CPU를 쓰러들어와서 다쓰고 나갈때까지 걸린시간
      (프로세스가 시작되서 종료될때까지의 시간이 아님!!!!)
      CPU를쓰러 들어와서 I/O하러 나갈때까지의 총시간!
    • Waiting time(대기시간)
      CPU를 쓰고자할때 레디큐에서 대기하면서 기다리는시간
    • Response time(응답시간)
      레디큐에 들어와서 처음으로 CPU를 얻기까지 걸린시간
    • 대기시간과 응답시간의 다른점
      대기시간 - 선점형스케줄링인 경우에는 CPU를 얻었다가 뺐겼다가 다시 얻었다가 뺏겼다가를 반복할수도 있는데, 뺏기면 다시 레디큐에가서 기다릴수도 있게되고, 이때 줄서서 기다린 시간을 다 합친것
      응답시간 - 최초의 CPU를 얻기까지 기다린시간

FCFS (First-Come First-Served)

  • 먼저온 고객에게 먼저 서비스를 제공한다.
  • 먼저온 순서대로 처리한다.
  • 비선점형 스케줄링! 앞쪽에있는 프로세스가 시간을 오래쓰면 뒤쪽의 프로세스가 인터액티브한 작업이 힘들다

    P1은 0초, P2는 24초, P3는 27초를 기다린다.(waiting time)


CPU를 짧게쓰는 프로세스가 먼저 도착하면 평균대기시간은 위의 경우보다 더 짧아진다.


FCFS는 프로세스의 순서에 따라 복불복임

Convoy effect : 앞쪽의 긴 프로세스때문에 뒤쪽의 짧은 프로세스들이 기다려야하는 현상

SJF(Shortest-Job-First)

  • 각 프로세스와 다음번 CPU burst time을 가지고 스케줄링에 할당

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

  • Two schemes:

    Nonpreemptive

    일단 CPU를 잡으면 이번 CPU burst가 완료될때까지 CPU를 선점당하지 않음

    예시가 너무 잘되있어서 가져와봤는데,
    P1이 도착한 시점에는 P1밖에없어서 시간이 제일 긴 P1을 실행하지만 P1이 끝난 시점에는 P2, P3, P4 모두 도착해있기때문에 이 중 가장 짧은것부터 실행시킨다.

Preemptive

  • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

  • 이 방법을 Shortest-Remaining-Time-First(SRTF)라고도 부른다

    얘는 실행시키다가 끊고 실행시간이 짧은 것을 실행시킨다!
    Nonpreemptive이랑 비교해보면 평균대기시간이 더 짧다!!!!


  • SJF is optimal
    - 주어진 프로세서들에 대해 minimum average wating time을 보장

그럼 CPU스케줄링에서 이 알고리즘을 쓰는게 제일 좋은가??????

이 스케줄링 알고리즘은 2가지 문제점이 있다

starvation(기아현상) - 극단적으로 CPU사용시간이 짧은 프로세스를 선호한다.
그래서 CPU사용시간이 긴 프로세스를 실행시키지 못하는경우가 발생할 수도있다.

CPU burst time을 미리 알 수 없다 - CPU사용시간을 미리 알수는없지만 추정은 가능하다. 과거의 CPU사용한 흔적을 통해 해당 프로세스의 CPU burst time을 예측한다.

Priority Scheduling

우선순위가 가장 높은 프로세스에게 CPU를 주는 개념

  • 각 프로세스마다 우선순위(정수)가 주어지는데, 값이 작을수록 우선순위가 높음

    • preemtive : 우선순위가 가장 높은 프로세스에 CPU를 줬는데, 우선순위가 더 높은 프로세스가 도착하면 걔한테 CPU를 준다.
    • nonpreemtive : 일단 CPU를 한번 줬으면 더 높은 우선순위가 도착하더라도, 기존의 것을 계속 실행시킴
  • SJF는 일종의 priority scheduling이다
    SJF에서의 우선순위는 예측한 CPU burst time이다.

  • 문제점
    Starvation문제

  • 해결책
    Aging : 기다리는게 길어지면 우선순위를 높여준다.

Round Robin(RR)

현대적인 컴퓨터 시스템에서 사용하는 스케줄링은 RR에 기반하고 있다.

  • 각 프로세스는 동일한 크기의 할당시간을 가짐

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

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

  • 각 프로세스의 응답시간이 빨라진다. 조금씩 CPU를 사용하기 때문에 모든 프로세스가 조금씩 CPU를 사용할 수 있다.

  • q를 크게잡으면 FCFS랑 같음

  • q를 잘게 하면 context swtich가 빈번히 발생한다 = 오버헤드

  • 일반적으로 SJF보다 average turnaround time이 길지만, response time은 더 짧다.

Multilevel Queue


위에있을수록 우선순위가 높음!

프로세스가 줄을 서고, CPU가 하나밖에없다면 여러 줄 중 하나만 빼서 실행할 수 있다.

프로세스를 어느줄에 할당할 것인가를 결정해야함!

계급제도!!

  • Ready Queue를 여러개로 분할
    - foreground(interactive한 job을 넣는다)
    - background(batch - no human interaction 사람과 소통하지않는 job)
  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐
    - foreground - RR
    - background - FCFS

큐에 대한 스케줄링이 필요(여러개의 큐가있으면 어느줄에 cpu를 줄까!)

  • Fixed prioity scheduling
    - serve all from foreground then from background
    - Possilbility of starvation
  • Time slice
    - 각 큐에 CPU time을 적절한 비율로 할당
    - 80% to foreground in RR, 20% to background in FCFS

Multilevel Feedback Queue

계급이 낮아도 계급을 올릴?수 있음
여러 계급을 왔다갔다할 수 있음

처음 들어온 프로세스는 가장 상위의 큐에 들어가고 할당시간을 짧게준다.

그리고 밑으로 갈수록 할당시간은 길어지고 맨 아래의 큐는 FCFS알고리즘이 적용됨

한 프로세스가 가장 상위에서 할당시간내에 일을 처리못하면 그 밑의 큐로 가게됨! 이런식으로 운영된다.


  • 프로세스가 다른 큐로 이동가능
  • 에이징을 이와 같은방식으로 구현할 수 있다.
  • Multilevel-feedback-queue scheduler를 정의하는 파라미터들
    - Queue의 수
    - 각 큐의 scheduling algorithm
    - Process를 상위큐로 보내는 기준
    - Process를 하위큐로 내쫒는 기준
    - 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

위에는 CPU가 하나밖에 없는 시스템이었다!

Multiple-processor scheduling

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

Realtime Scheduling

  • Hard realtime scheduling
    - 정해진 시간안에 반드시 끝내도록 스케줄링해야함
  • Soft realtime scheduling
    - 일반 프로세스에 비해 높은 priority를 갖도록 해야함

Thread Scheduling

  • Local scheduling
    User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
    -운영체제는 스레드를 모름 > 운영체제는 프로세스단위로 cpu를 줄지말지 결정하고 프로세스내부에서 스레드에 cpu를 줄지말지 결정
  • Global scheduling
    - Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
    • 운영체제가 스레드의 존재를 알고있음
    • 프로세스 스케줄링하듯이 스레드에게 cpu를 줄지 결정함!

알고리즘 평가방법

  • Queueing models
    - 확률 분포로 주어지는 arrival rate와 service rate등을 통해 각종 performance index값을 계산

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

0개의 댓글