[OS] 5. CPU 스케줄링

신명철·2022년 5월 31일
OS
0

OS

목록 보기
23/27

CPU 스케줄링

  • CPU는 I/O burst 와 CPU burst를 연속적으로 반복하게 된다.
    • I/O burst: I/O 작업을 기다리는 시간
    • CPU burst: instruction 수행 시간
  • I/O burst 의 발생이 잦아지면서 CPU burst 가 짧아지게 되면서 CPU 효율성을 위해 스케줄링이 필요
  • CPU 와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용할 수 있음
  • 프로세스는 특성에 따라 다음 두 가지로 나눔
    • 1.I/O-bound process: CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job(대부분 CPU burst가 매우 짧음)
    • 2.CPU-bound process: 계산 위주의 job(보통 CPU burst가 매우 긺)

CPU 스케줄러 & Dispatcher

CPU Scheduler

  • Ready 상태의 프로세스 중 CPU를 줄 프로세스를 고르는 역할

Dispatcher

  • CPU 스케줄러가 고른 프로세스에게 CPU 제어권을 넘기는 역할
  • 이 과정을 context switching 이라 함

CPU 스케줄링이 필요한 경우

스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태변화가 있는 경우다

  1. Running -> Blocked (e.g I/O 요청하는 시스템 콜)
  2. Running -> Ready (e.g 할당시간 만료로 timer interrupt)
  3. Blocked -> Ready (e.g I/O 완료 후 인터럽트)
  4. Termianated
  • 1,4 은 nonpreemptive(= 자진 반납) 스케줄링 => CPU를 가지고 있어도 더 이상 수행할 수 없기 때문에 반납하는 경우임
  • 나머지는 preemptive(= 강제로 빼앗음) 스케줄링 => CPU를 번갈아 사용하기 위해서 강제로 빼앗긴 경우임

스케줄링 성능 척도

  • 시스템 입장에서의 성능 척도
    1. CPU utilizaion(이용률)
      • CPU 최대한 오래 바쁘게 유지하는 것
    2. Throughput(처리량)
      • 주어진 시간동안 몇 개의 작업을 완료하는가
  • 프로세스(고객) 입장에서의 성능 척도
    1. Turnaround time(소요 시간,반환 시간)
      • 프로세스가 작업을 처리하는데 걸린 총 시간 (쓴 시간 + 기다린 시간)
    2. Waiting time(대기 시간)
      • 프로세스가 CPU를 기다리는데 걸린 총 시간 (waiting time 의 총량)
    3. Respone time(응답 시간)
      • 처음으로 CPU를 얻는데까지 걸린 시간(time sharing 환경에서 필요함)

스케줄링 알고리즘

Single-Processor Scheduling

  1. FCFS(First-Come First-Served)
  • 선입선출, 도착한 순서로 CPU 할당(Nonpreemtive 방식임)
  • Convoy effect 가 발생
    • 긴 프로세스 때문에 짧은 프로세스들이 오래 기다려야 하는 현상
  1. SJF(Shortes-Job-First)
  • CPU burst time이 가장 짧은 프로세스에게 CPU 할당
  • 주어진 프로세스들에 대해서 minimum average waiting time 을 보장함
  • 두 가지 문제점이 존재
    • starvation 문제가 발생함 => 짧은 프로세스들이 계속 들어오면 영원히 할당받지 못하는 프로세스가 발생할 수 있음
    • CPU burst time 을 알 방법이 없음 => 과거 CPU burst time을 이용해 추정(estimate)만 가능함
  • 두 가지 설계 방법이 존재
    • 1.Nonpreemtive
      • 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
    • 2.Preemtive
      • 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 프로세스가 도착하면 CPU를 빼앗는 방법
      • SRTF(Shortest-Remaining-Time-First)라고도 부름
      • Nonpreemtive 방식보다 average waiting time이 짧음
  1. Priority
  • 프로세스마다 우선 순위를 정해서 가장 높은 우선순위의 프로세스에게 CPU 할당
  • SJF 는 일종의 Prirorty Scheduling 임
  • starvation 문제가 존재함 -> Aging 으로 해결할 수 있음
  • Aging 기법
    • 시간이 흐름에 따라 우선 순위를 조금씩 높여주는 방법
  • 두 가지 설계 방법 존재
      1. Nonpreemtive
      • 더 높은 우선순위가 들어와도 빼앗지 않음
      1. Preemtive
      • 더 높은 우선순위가 들어오면 빼앗음
  1. Round Robin (RR)
  • 대부분의 현대적인 CPU 스케줄링이 RR에 기반하고 있음
  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
    • q 가 너무 크면 => FCFS와 같아짐
    • q 가 너무 작으면 => context switching 오버헤드가 커짐
  • 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤로 가서 대기함
  • response time이 빨라지는 것이 장점임 => n 개의 프로세스들 중 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음
  • response time은 프로세스의 CPU burst time 과 비례하게 됨
  • 일반적으로 turnaroung time 은 SJF 보다 길지만 response time 은 더 짧음
  • 단적인 예
    • cpu burst time 이 길며 똑같은 프로세스들이 ready queue 에 있는 경우, 각각의 프로세스들 중 먼저 빠져나갈 수 있는 프로세스가 없기 때문에 turnaround time 이 길어지고 waiting time도 길어지는 상황이 생길 수 있음
    • Round Robin 의 장점인 짧은 response time 이 발휘되지 못하는 경우
  1. Multilevel Queue

  • 맨 윗줄이 우선순위가 높고, 맨 아래가 우선순위가 낮음
  • 프로세스의 용도에 따라서 우선순위가 정해지고 극복할 수 없음
  • Ready queue를 여러 개로 분할/ 각 queue는 독립적인 알고리즘을 가짐
    • foreground(interactive) -> RR
    • background(batch - no human interactive) -> FCFS
  • queue에 대한 스케줄링이 필요함
    • Fixed priority scheduling
      • foreground가 비어 있을때만 background 할당
      • starvation 발생할 수 있음
    • Time slice
      • 각 queue에 CPU time을 적절한 비율로 할당
      • e.g) 80% to foreground in RR, 20% to background in FCFS
  1. Multilevel Feedback Queue

  • 프로세스다 다른 queue로 이동할 수 있음
  • aging을 이와 같은 방식으로 구현할 수 있음
  • 동작 방식
    • 새로운 프로세스가 Q0 로 들어감
    • CPU를 할당받아서 8ms동안 수행, 다 끝내지 못하면 Q1으로 내려감
    • 기다리다가 할당받아서 16ms동안 수행, 다 끝내지 못하면 Q2으로 쫓겨남

Multiple-Processor Scheduling

  • CPU가 여러개면 스케줄링은 더 복잡해짐
  1. Homogeneous processor
    • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있으면 문제가 더 복잡해짐
  2. Load Sharing
    • 일부 프로세서에 job이 몰리지 안혿록 부하를 적절히 공유하는 매커니즘 필요
    • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
  3. Symmetric Multiprocessing(SMP)
    • 모든 CPU가 대등함
    • 각 프로세서가 알아서 스케줄링 결정
  4. Asymmetric Multiprocessing
    • 하나의 CPU가 시스템 데이터의 접근과 공유를 책임지고 나머지 CPU는 거기에 따름

Real-Time Scheduling

  • 정해진 시간에 반드시 처리되어야 함 (Deadline이 보장되어야 함)
  1. Hard real-time systems
    • Hard real-time task는 정해진 시간에 반드시 끝내도록 스케줄링해야 함
  2. Soft real-time systems
    • Soft real-time task는 일반 프로세서에 비해 높은 priority를 갖도록 해야함

Thread Scheduling

  1. Local Scheduling
    • User level thread인 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할 지 결정
    • OS가 관여하지 않고 프로세스 내부에서 결정
  2. Global Scheduling
    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
    • OS가 thread의 존재를 알고 있고, OS가 프로세스를 스케줄링하듯 thread를 스케줄링함

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

profile
신명철
내 머릿속 지우개
이전 포스트

[OS] 4. 프로세스 관리와 프로세스 간 협력

다음 포스트

[OS] 6. 프로세스 동기화

0개의 댓글

관련 채용 정보