[운영체제] CPU Scheduling

🧭 CS Study - 운영체제

🚩 주제 : CPU Scheduling

🎥 강의 : KOCW 운영체제 강의 - 이화여자대학교 반효경 교수님

CPU Scheduling

어떤 프로그램을 실행해도 CPU burst(CPU 명령 실행) - I/O burst(I/O 요청 후 대기 시간)가 실행된다.
프로그램 종류에 따라서 CPU burst와 I/O burst의 빈도, 길이가 다르다. 한 프로그램 내에도 job의 종류가 섞여있다.

• I/O bound job : CPU를 짧게 사용함
• CPU bound job : CPU를 오래 사용함

I/O bound job은 interative한 job이다. 가능하면 사람하고 상호작용하는 job에게 CPU를 우선적으로 할당하는 것이 좋다. 이를 위해서 CPU scheduling을 진행한다. 이때 중요한 것은 CPU를 효율적으로 사용하는 것이다.

CPU Scheduler : Ready 상태의 프로세스들 중에 CPU를 부여할 프로세스를 선택한다.
Dispatcher : CPU 제어권을 프로세스에게 넘긴다. (context switch(문맥 교환))

** CPU Scheduler와 Dispatcher는 하드웨어가 아니라 OS안에서 실행되는 코드이다.

CPU Scheduling이 필요한 경우

• Running -> Blocked : ex)I/O 요청 시스템콜 - nonpreemptive(자진반납)
• Running -> Ready : ex) timer interrupt - preemptive(강제로 빼앗음)
• Blocked -> Ready : ex) I/O완료 후 인터럽트 - preemptive
• Terminate - nonpreemptive

CPU Scheduling의 주요 이슈
1. 누구에게 CPU를 할당할 것이냐?
2. CPU를 중간에 빼앗을 수 있게 할 것이냐?

CPU Scheduling 성능 측정 기준

• CPU 이용률 : 전체 시간 중에 CPU가 일한 시간 : CPU는 가능한 많이 활용해야한다. (시스템 입장에서의 성능 측정)
• 처리량 : 주어진 시간동안 완료한 작업의 개수 (시스템 입장에서의 성능 측정)
• Turnaround time(소요시간) : CPU를 얻어서 사용하고 CPU 나갈때까지의 시간(프로세스 입장에서의 성능 척도)
• Waiting time(대기 시간) : Ready Queue에서 기다리는 총 시간 (프로세스 입장에서의 성능 척도)
• Response time(응답 시간) : Ready Queue에 들어와서 CPU를 처음으로 얻기까지 걸린 시간(프로세스 입장에서의 성능 척도)(선점형 Scheduling의 경우 waiting time과 response time의 차이를 알 수 있다.)

CPU Scheduling Algorithm

크게 preemptive한 방법과 nonpreemptive한 방법으로 나뉜다.
preemptive(선점형) : 강제로 프로세스에게서 CPU를 빼앗는다.
nonpreemptive(비선점형) : 프로세스가 CPU를 스스로 반납할 때까지 빼앗지 않는다.

FCFS(First-Come First-Served)

• 먼저 Queue에 도착한 순서대로 프로세스를 처리한다.
• 비선점형 스케줄링 방식이다.
• CPU를 오래쓰는 프로세스가 제일 먼저 CPU를 할당받으면 뒤에 CPU를 짧게 사용하는 프로세스들이 오래 기다려야한다. 기다리는 시간의 평균이 커진다.
• 반면에 CPU를 짧게 사용하는 프로세스들이 queue의 앞쪽에 위치하면 평균 대기 시간이 짧아진다.
• 앞에 있는 프로세스의 CPU 사용시간에 따라 평균 대기 시간이 달라진다.
• Convoy effect가 발생한다.

** Convoy effect : CPU를 오래 사용하는 프로세스가 먼저 도착해서 CPU를 점유하고 있기 때문에 CPU를 짧게 사용하는 프로세스들이 오래 기다리는 현상

SJF(Shortest-Job-First)

• CPU 사용시간이 짧은 프로세스 먼저 스케줄링 하는 것

• Queue가 전체적으로 빠르게 짧아진다. 그래서 평균 대기 시간이 가장 짧아진다. (Minimum average wating time)

• Nonpreemptive한 방식과 Preemtive한 방식을 생각할 수 있다.

• Nonpreemptive : CPU 사용시간이 더 짧은 프로세스가 도착하더라도 현재 CPU를 사용하는 프로세스가 CPU를 다 사용할 때까지 기다린다.

• Preemptive : CPU 사용시간이 더 짧은 프로세스가 도착하면 현재 CPU를 사용중인 프로세스에게서 CPU를 강제로 빼앗아서 CPU 사용시간이 더 짧은 프로세스에게 할당한다. (Shortest Remaining Time First: SRTF)(평균 대기시간을 최소화하는 알고리즘)

• 문제점1. Starvation이 발생한다.
  : CPU 사용시간이 긴 프로세스는 영원히 CPU를 할당받지 못할 수도 있다.

• 문제점2. CPU 사용시간을 미리 알 수 없다.
  : CPU를 할당받고 나가기 전까지 프로세스가 CPU를 얼마동안 사용할지 알 수 없어서 SJF가 사용될 수 없다. 과거 기록을 통해 CPU burst를 추정한다면 사용가능하다. (exponential averaging으로 추정)

Priority Scheduling

• 우선순위가 제일 높은 프로세스에게 CPU를 할당한다.
• Nonpreemptive한 방식과 Preemtive한 방식을 생각할 수 있다.
• Nonpreemptive : 우선순위가 더 높은 프로세스가 와도 현재 CPU를 할당받은 프로세스에게서 CPU를 빼앗지 않는다.
• Preemptive : 우선순위가 더 높은 프로세스가 오면 현재 CPU 사용하는 프로세스에게서 CPU를 빼앗아서 우선순위가 더 높은 프로세스에게 할당한다.
• 각 프로세스마다 우선순위를 표현하는 정수값을 부여한다.

문제점1. Starvation이 발생한다.
: Aging이라는 기법을 도입하여 문제를 해결한다. 우선순위가 낮은 프로세스이더라도 오래 기다리면 우선순위를 높여주는 방법이다.

Round Robin(RR)

• 현대적인 CPU 스케줄링 방법이다.
• 선점형 스케줄링이다.
• 프로세스에게 CPU를 할당할 때 동일한 크기의 할당 시간(time quantum)을 부여한다. 해당 시간이 종료되면 timer interrupt에 이해 CPU를 빼앗긴다. 그 뒤에 ready queue의 마지막에 프로세스가 추가되는 방식이다.
• CPU 사용시간과 대기시간이 비례하다. 즉, CPU를 길게 사용하는 프로세스는 대기시간이 길어지고 CPU를 짧게 사용하는 프로세스는 대기시간이 짧아진다. CPU를 길게 사용하는 만큼 대기하는 횟수가 많아지기 때문이다.
• 할당 시간을 크게 부여하면 FCFS와 동일한 알고리즘이 된다.
• 할당 시간을 짧게 부여하면 context switch의 오버헤드가 커진다.
• SJF보다 Response time은 짧아지고, waiting time, turnaround time은 길어진다.
• 효율적이고 공정한 방식이다.
• 프로세스의 context를 저장하는 과정이 있기 때문에 가능한 방식이다.

Multilevel Queue

• queue를 여러줄로 나눠서 CPU를 기다리는 것이다. (위에 있는 방식들은 queue가 1줄로 이루어짐)

• foreground(interactive), background(batch-no human interaction) 큐로 나눈다.

• 각각의 큐마다 독립적인 스케줄링 알고리즘을 사용한다. foreground job queue는 RoundRobin 방식을 사용한다. background job queue는 FCFS 방식을 사용한다.

• 큐에 대한 스케줄링이 필요하다.

• 우선순위가 높고 낮은 프로세스에 따라 다르게 사용하는 queue를 여러개 만든다.

• 프로세스를 어느 줄에 넣을 것인지 결정해야한다.

• 우선순위가 낮은 프로세스는 Starvation을 겪는 문제가 생길 수 있다.

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동할 수 있다.
• 파라미터를 정해야한다.
  - 큐의 수
  • 큐의 스케줄링 알고리즘
  • 프로세스를 상위/하위 큐로 보내는 기준
  • 처음 프로세스가 큐에 들어갈 때 어떤 큐로 들어가는지 결정하는 기준
• 처음 들어오는 프로세스는 우선순위가 가장 높은 큐로 넣어준다.
• 우선순위가 높은 큐의 할당 time quantum 내에 일을 완수하지 못하면 우선순위가 낮은 큐로 들어가고 해당 큐에서도 time quantum 내에 일을 수행하지 못하면 또 우선순위가 낮은 큐로 이동하는 방식이다.
• 우선순위가 가장 낮은 큐는 FCFS 방식을 사용한다.

Multiple Processor Scheduling

• Homogeneous Processor : Queue에 한 줄로 프로세스를 세워서 프로세스가 꺼내가게 한다.
• Load sharing : 프로세스의 job 부하를 적절히 공유하게 하는 구조가 필요하다.
• Symmetric Multiprocessing : CPU가 모두 대등하기 때문에 각자 알아서 스케줄링함
• Asymmetric Multiprocessing : 하나의 프로세서가 시스템 데이터의 접근, 공유를 책임지고 나머지 프로세서는 그에 따른다.

Real-Time Scheduling

• 정해진 시간안에 수행되어야 하는 job이다.
• 반드시 정해진 시간안에 완수되어야 하는 것은 Hard real-time system이다.
• 우선순위만 올려주고 정해진 시간안에 완수하는 것을 보장하지는 않는 것은 Soft real-time computing이다.

Thread Scheduling

• User level thread의 경우 사용자 프로세스 내부에서 어떤 thread에게 CPU를 부여할지 결정한다.
• Kernel level thread의 경우 커널의 스케줄러가 thread에게 CPU 부여를 결정한다.

알고리즘 평가 방법

Queueing model

• CPU로 들어오는 프로세스 도착률과 CPU의 처리율이 주어질 때 performance index를 계산함

Implement & Measurement

• 시스템을 구현하고 성능을 측정한다.

Simulation

• 모의 프로그램 작성 후 결과 비교