[OS] CPU 스케쥴링 / 기법

위영민(Victor)·2021년 5월 9일
OS
0

사전지식

  • CPU Burst Time & I/O Burst
  • Scheduling Queue

CPU Burst Time & I/O Burst Time

프로세스는 CPU Burst 와 I/O Burst가 왔다갔다 바뀌면서 프로그램을 실행

  • CPU Burst : CPU 명령을 실행하는하는 것
  • I/O Burst : I/O 요청한 다음 기다리는 시간

CPU Burst Time = 10초라고 하면, 이 프로세스가 특정 작업이 완료되기 위해서는 CPU가 10초동안 이 프로세스를 작업해줘야 된다는 의미

Scheduling Queue

  • Job Queue
    • 시스템 안의 모든 프로세스들로 구성
    • 프로세스가 시스템에 들어오면 job queue에 놓여짐
  • Ready Queue
    • 프로세스 상태가 Ready 상태인 프로세스가 들어가는 큐, 보통 연결리스트로 구성

CPU 스케쥴링이란 ?

필요한 이유

  • CPU & I/O Burst가 프로세스마다 긴것도있고 짧은 프로세스도 존재

  • 여러개의 Ready Queue로 들어온 프로세스들 중 누구에게 CPU를 할당할 것인가 ?

즉, 누구한테 주고, 얼마나 쓰게 할 것인가 ? 를 효율적으로 해결하기 위해 프로세스 스케쥴링이 필요

비선점 VS 선점

  • 비선점(Non-Preemtive) : CPU를 받았으면, 본인 작업이 끝날 때까지 보장받는 방식
  • 선점(Preemtive) : CPU를 받아도, Timer Interrupt 등으로, 강제로 CPU를 빼앗길 수 있는 방식

CPU 성능 척도

시스템 입장

  • Utilization(이용료) : 전체시간 중, CPU가 놀지 않고 일한 시간
  • Throughput(처리량) : 주어진 시간 내, CPU가 몇 개의 작업을 처리했는가 ?

프로그램 입장(사용자 입장)

  • Turnaround-Time(소요시간,반환시간) : 프로세스가 CPU를 쓸려고 들어와서, CPU를 다쓰고 I/O 처리하러 나가기까지 총 시간, 즉 CPU Burst 시간

  • Waiting-Time(대기시간) : Ready Queue에서 기다리는 시간

  • Response-Time(응답시간) : Ready Queue에 들어와서, 처음 CPU를 할당 받는 시간

선점방식의 경우

- 대기시간은 프로세스마다 잠깐 사용했다 기다렸다 반복하보면 총 대기시간은 바뀔 수 있음
- 응답시간의 경우는, 그것과 상관없이 맨 처음 CPU를 할당 받는 시간임

프로세서(CPU) 1개

FCFS ( First-Come-First-Served )

= 먼저 온 놈, 먼저 서비스

  • 비선점(Non-Preemtive) 방식

if ) CPU Burst 가 짧은 프로세스가 먼저 들어온다면 ?

Convey Effect

CPU Burst 가 긴 프로세스가 앞에서 서비스를 받아, 전체적인 Wait 시간이 커지는 현상

SJF ( Shortest Job First )

= CPU Burst 가 가장작은 순으로, 먼저 서비스

  • 선점(Preemtive) / 비선점(Non-Preemtive) 방식

  • 선점

    • 이미 서비스를 받고 있는 프로세스가 있어도, 그 시점에서 더 짧은 CPU Burst 인 프로세스가 들어오면, CPU 제어권을 뺐을 수 있음
    • 이러한 방식 == SRTF(Shortest-Remain-Time-First)

  • 비선점

    • CPU Burst 가 짧은 프로세스가 들어와도, 이미 CPU를 사용하고 있는 프로세스가 있다면 기다려야 함

Non-Preemtive SJF

Preemtive SJF

장점

  • SJF Optimal : 주어진 프로세스들에 대해 Minimum Average Waiting Time 을 보장( 선점 방식의 경우 )

단점

  • Starvation (기아현상)

    • CPU Burst 가 비교적 큰 프로세스는 계속되는 짧은 CPU Burst를 가진 프로세가 들어오면, 영원히 CPU 할당을 못 받을 수 있다.

  • CPU 사용시간을 미리 알 수 없음

    • 실제 시스템에서는 여러 분기가 있을 수 있어서, Burst 시간이 짧다고, 실제로 언제, 그 프로세스가 끝날지 모른다. (추정은 가능)

RR( Round-Robin )

= 각 프로세스는 동일한 크기, 할당 시간(Time Quantum, 일반적으로 20~50 msec)을 가짐

  • 선점(Preemtive)
  • Quantum-Time이 다 되면, 프로세스는 선점당하고, Ready Queue에 맨 뒤에 가서 줄은 선다.

장점

  • 응답시간(Response-Time)이 빠름
  • EX) n개의 프로세스가 Ready Queue에 있고, q-Time unit인 경우, 최대 (n-1) * q-Time 단위로 CPU를 할당 받을 것임
    • q-Large = FCFS
    • q-Small = Context-Switching 오버헤드 빈번
    • 즉, 적당히 q-Time을 설정할 것

  • 앞선 SJF 방식보단, Average-Turnaround-Time이나 Waiting-Time은 길어질 수 있으나, Response-Time은 효과적으로 더 짧아짐

Prioirty Scheduling

= 프로세스들을 그룹화 해서 우선순위 클래스를 형성, 우선순위 클래스마다 우선순위를 할당해서 각 클래스 내에서 RR을 사용

HRN(Highest Response-ratio Next) Scheduling

  • 기아현상을 보완하기 위해 등장한 스케쥴링
  • 각 작업의 우선순위로 서비스 해줌
  • 비선점
  • 우선순위측정 : waiting-Time / service-Time

에이징(Aging) 기법

= 아무리, 우선순위가 낮은 프로세스여도, 시간이 지날수록 우선순위를 높여주자.

MuliLevel Queue

= 여러 개의 Ready Queue로 분할(=여러 줄로 CPU를 기다림)

  • 선점(Preemtive)

  • System Process : 시스템 관련 프로세스
  • Interactive Process : 사용자와 인터렉션 프로세스
  • Batch Process : CPU만 많이 잡아먹는 프로세스
  • Student Process

Foreground Queue

= 사용자와 인터렉티브(Interactive)한 작업 프로세스

  • Round-Robin 방식 추구

Background Queue

= 배치(Batch) 작업 프로세스

  • FCFS 방식 추구
  • Context-Switching 최소화 목적

MultiLevel-Feedback-Queue

  • 선점(Preemtive)

MFQ 를 정의하는 파라미터들

  • Queue의 수
  • 각 Queue의 알고리즘
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐롤 보내는 기준
  • Process가 CPU 서비스를 받으려 할 때, 들어갈 큐를 결정하는 기준

보통, 처음 들어오는 큐를 우선순위를 높게함

  • 우선순위를 높게해서, RR 방식으로 q-Time을 가장 짧게 => 점점 크게 => 제일 아래 FCFS로 설정
  • 상위 큐가 끝나면, 다음 하위 큐가 실행되도록 설정

프로세서(CPU) 여러 개

Mutiple-Processor Scheduling

= CPU가 여러 개인 경우, 스케쥴링은 더욱 복잡해짐

  • Homogeneous processor 경우

    • Queue에 한 줄로 세워서, 각 프로세서가 알아서 꺼내감
    • 특정 프로세서에서 반드시 수행되어야 하는 프로세스가 있는 경우, 문제가 더욱 복잡해짐

  • Load Sharing

    • 일부 프로세서에 Job이 몰리지 않도록, 부하를 적절히 공유하는 메커니즘이 필요
    • 별개 Queue VS Multi-Processing

  • Symmetric Multi-Processing (SMP)

    • 모든 CPU가 대등함

  • Asymmetric Multi-Processing

    • CPU가 여러 개인데, 특정 CPU가 대장임, 이 대장 CPU가 나머지 CPU의 작업을 분배

Real-Time Scheduling

= Dead-line이 보장 되어야 함, 미리 스케쥴링할 필요가 있음

  • Hard Real-Time : 정해진 시간 안에 반드시 끝내도록 스케쥴링
  • Soft Real-Time : 어느 정도의 데드라인이 넘는 것은 허용하는 스케쥴링

Thread Scheduling

Local Scheduling

  • User-Level-Thread의 경우, 프로세스에 의해, 어떤 Thread에게 스케쥴할지 결정
  • OS(커널)은 프로세스 내부의, 스레드 존재는 모름, 그래서 각 프로세스가 내부 스레드 스케쥴링

Global Scheduling

  • Kernel-Level-Thread의 경우, 일반 프로세스와 같이, 커널(OS)이 프로세스 스케쥴링하듯이, 프로세스 내부의 Thread들을 스케쥴링

중요한 차이점 : 성능

  • User-Level-Thread Switching은 주의 깊은 사용이 필요
  • Kernel-Level-Thread Switching은 완전한 Context Switching이 필요

참고자료

- https://jhnyang.tistory.com/25 (CPU Burst & I/O Burst)
- OS 수업자료
profile
위영민(Victor)
블로그 이사했습니다 :) 👉 https://www.youngminss-log.com/blog
이전 포스트

[OS] 프로세스 & 스레드

다음 포스트

[OS] 프로세스 동기화 (1)

0개의 댓글