[OS]CPU Scheduling(CPU/IO Bursts, Scheduler/Dispatcher, Scheduling Algorithm, Algorithm Evaluation)

zzarbttoo·2021년 8월 7일
0

OS(운영체제)

목록 보기
6/12

이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.

이번 챕터에서는 CPU Scheduling에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다


CPU/IO Bursts

CPU Burst : CPU를 실행하는 단계
IO Burst : IO를 실행하는 단계

  • 어떤 프로그램이든 빈도만 다를 뿐 CPU Burst -> IO Burst -> CPU Burst -> ... 의 반복하는 작업을 거치게 된다
  • 사람이 interaction 하는 경우에는 IO 작업이 빈번하게 일어난다(화면 사용률이 높음)

| CPU Burst 분포

CPU Burst time 확률 분포도

  • IO Bound Job: CPU Burst 빈도가 높고, CPU 점유 시간이 적음
  • CPU Bound Job : 계산 위주의 Job으로, CPU 작업만 진득하게 함
  • CPU Bound Job이 오랫동안 CPU를 잡게 되면 IO Bound Job(사람과의 interaction 빈번함)이 CPU를 잡지 못하고 사람은 답답함을 느끼게 된다
  • CPU Scheduling을 통해 IO Bound Job에 CPU를 우선적으로 할당해주게 된다

CPU Scheduler/Dispatcher

| CPU Scheduler
Ready 상태의 프로세스 중 누구에게 CPU를 줄 지 결정한다

| Dispatcher
CPU Scheduler에 의해 선택된 프로세스에 CPU 제어권을 넘겨주는 역할을 하는 것

  • CPU Scheduler, Dispatcher 모두 다 운영체제 내의 코드이다
  • CPU 스케쥴링이 필요한 경우는 다음과 같다
    1) Running -> Blocked(I/O 요청 시스템 콜)
    2) Running -> Ready (Time Interrupt)
    3) Blocked -> Ready (I/O 완료 후 Interrupt)
    4) Terminate
  • 1)의 경우에 I/O를 요청한 프로세스의 우선순위가 가장 높다면 I/O가 끝난 직후 그 프로세스에 CPU를 바로 넘겨줘야 할 수도 있다
  • 1/4번은 nonpreemptive(자진 반납), 2/3번은 preemptive(강제 반납)

Scheduling Algorithms

| FCFS(First-Come First-Served)

  • 먼저 들어온 프로세스를 먼저 처리해주는 것
  • CPU를 오래 사용하는 프로세스가 CPU를 얻게 되면, 대화형 프로세스가 지나치게 오래 기다리는 문제 발생

| Round Robin(RR)

  • CPU 할당할 시간을 미리 세팅해서 그 시간만 CPU를 사용하도록 하고 시간이 지나면 줄 서 있는 프로세스에 CPU를 할당해주는 것
  • 각 프로세스가 동일한 크기의 할당 시간(time quantum)을 가짐
  • 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready Queue의 맨 뒤로 가서 줄을 선다
  • CPU를 기다리는 시간이 CPU를 사용하는 시간과 비례하는 측면에서 공정함
  • Process의 Context를 Save 하고 다시 CPU를 얻었을 때 그 지점부터 재개할 수 있다는 메커니즘을 제공해주기 때문에 가능하다
  • 할당 시간이 커지면 FCFS 방식에 가까워지고, 할당 시간이 너무 작아지면 context switch 오버헤드가 발생하게 된다

| Mulitilevel Queue

  • Ready Queue를 여러개로 분할한다
  • 각 Queue마다 스케쥴링 방식을 달리 한다

예시 : foreground, background

  • foreground Queue의 경우 Round Robin 방식을 이용해 사람과의 interaction을 할 수 있도록 한다
  • background Queue의 경우 context switch overhead를 줄이기 위해 FCFS를 사용한다
  • 큐에 CPU를 줄 때 우선순위에 따라서만 CPU를 준다면 Starvation(우선순위가 낮은 Job은 CPU를 할당받지 못하는 현상)이 발생할 수 있다
  • 각 줄별로 CPU를 나누어 주는 방법을 생각해볼 수 있다(ex 우선순위 높으면 80%, 낮으면 20% 할당)

| Multilevel Feedback Queue

  • 프로세스가 다른 큐로 이동 가능하게 한다
  • 오래 대기할 수록 우선순위를 높게 책정하는 방식인 에이징(aging)을 이와 같은 방식으로 구현할 수 있다
  • 큐 설정에 기준들이 많이 필요하다(Queue의 수, 각 큐의 스케쥴링 알고리즘, Process를 상위/하위 큐로 보내는 기준, 프로세스가 CPU 서비스를 받을 때 들어갈 큐를 결정하는 기준)

예시 : 큐의 흐름이 다음과 같은 형태를 지닐 수 있다

  • 처음 들어오는 프로세스는 우선 순위가 가장 높은 큐에 배정을 한다(RR 할당 시간 짧음)
  • 밑으로 갈수록 RR 할당 시간을 길게 준다
  • 마지막에는 FCFS 스케쥴링 방식을 사용하는 큐에 배정한다
  • 할당 시간 내에 처리가 안되면 강등되는 방식으로 운영할 수 있다
  • CPU 시간이 짧은 프로세스에 우선 순위를 더 많이 주고 긴 프로세스는 점점 밑으로 쫓겨나게 된다

| Multiple-Processor Scheduling

  • CPU가 여러 개 있는 시스템에서의 스케쥴링

| Homogeneous Processor

  • Queue에 한 줄로 세워서 처리할 수도 있고, 각각의 CPU마다 별도의 줄을 서도록 할 수 있다
  • 특정 프로세서에 의해 처리되어야 하는 JOB이 있을 경우 복잡한 방식을 사용해야한다

| Load Sharing

  • 특정 CPU에 Job이 몰리지 않도록 부하를 적절하게 공유하는 메커니즘이 필요하다
  • 별개의 큐를 두는 방식, 공동 큐를 사용하는 방식 중 택할 수 있다

| Symmetric Multiprocessing(SMP)

  • 모든 CPU가 대등하기 때문에 각자 알아서 스케쥴링을 결정한다

| Asymmetric multiprocessing

  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다

| Real-Time Scheduling

  • Deadline 이 있도록 하는 스케쥴링
  • 그때그때 스케쥴링 하기 보다는 deadline에 맞게 미리 Job을 배치하는 방식을 사용한다
  • periodic하거나 주기적으로 activated 되어야 하기 때문에 dead line을 보장하는 것이 중요한 스케쥴링

| Hard real-time systems

  • task를 정해진 시간 안에 반드시 끝내도록 스케쥴링

| Soft real-time computing

  • 다른 프로세스와 함께 진행이 되며, 일반 프로세스에 비해 우선순위를 높여 빨리 진행될 수 있도록 한다

| Thread Scheduling

  • 프로세스 안에 CPU 실행단위가 여러 개 있는 것이 스레드
  • User Level Thread : 사용자 process가 스레드 관리
  • Kernel Level Thread : 운영체제가 스레드의 존재를 알고 있음

| Local Scheduling

  • User Level Thread의 경우 사용자 Thread Library에 의해 어떤 Thread를 스케쥴 할지 결정

| Global Scheduling

  • Kernel Level Thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 Thread를 스케쥴 할지 결정

Algorithm Evaluation

알고리즘의 성능을 평가할 수 있는 척도

| Queueing Models

  • 확률분포로 주어지는 arrival rate와 service rate를 통해 각종 performance index 값을 계산
  • arrival rate : Queue에 Job들이 도착해 쌓이게 되는 확률
  • service rate : 도착한 프로세스를 CPU가 처리하고 내보내는 비율
  • 이론적인 방법이라고 할 수 있다

| 구현 후 측정(Implementation&Measurement)

  • 실제 시스템에 알고리즘을 구현해보고 실제 작업에 대해 성능을 측정해보는 것

| 모의 실혐(Simulation)

  • 알고리즘을 모의 프로그램으로 작성한 후 trace를 입력으로 하여 결과 비교
  • 구현 후 측정 방식이 어렵기 때문에 시뮬레이션을 돌리게 된다
  • 실제 burst pattern을 따와서 시뮬레이션 프로그램의 input(trace)로 넣어야 신빙성이 있다
profile
기록하는 것을 좋아하는 사람입니다

0개의 댓글