[운영체제 정리] 6.CPU 스케쥴링

개요

 

프로그램의 실행

 

1.프로그램이 실행될때, CPU와 I/O가 반복 사용된다.

CPU를 사용하는 단계를 CPU 버스트, I/O를 사용하는 단계를 I/O 버스트라고 한다.

 

CPU BURST TIME 분포

프로그램 실행시 CPU 바운드 잡, I/O 바운드 잡이 섞여있다. 

(그래프를 보면 CPU 잡과 I/O 바운드 잡이 섞여 있음)

I/O 바운드잡은 사람과의 인터렉티브한 커뮤니케이션을 하기 때문에 CPU잡이 너무 많이 CPU를 갖고 있으면 I/O 바운드가 CPU를 잡지못하므로 사용자가 답답해 할 수 있다. 그래서 CPU 스케쥴이 필요하다.

 

프로세스의 특성 분류

프로세스는 특성에 따라 두가지로 나눔

I/O 바운드 프로세스: 키보드를 많이 칠때...

CPU 바운드 프로세스: 계산을 많이 할때...

 

 

CPU 스케쥴러 & 디스패처

CPU 스케쥴러는 운영체제 안에서 CPU 스케쥴링을 하는 코드를 일컫는다. (누구한테 CPU를 줄지 결정하는 코드다.)

디스패처도 운영체제 안에 존재하는 특정 기능을 일컫는다.(실제로 CPU를 주는 행위를 담당하는 코드다.)

 

디스패처

1. 새롭게 선택된 프로세스가 cpu를 할당 받고 작업을 수행할 수 있도록 환경을 설정하는 커널 모듈을 말한다.

2. 현재 수행중이던 프로세스의 문맥을 그 프로세스의 pcb에 저장하고, 새롭게 선택된 프로세스의 문맥을 pcb로 부터 복원한 후 그 프로세스에게 cpu를 넘기는 과정을 수행한다..

 

디스패처 지연시간

하나의 프로세스를 정지 시키고 다른 프로세스에게 cpu를 전달하기 까지 걸리는 시간

-> 문맥교환 오버헤드에 해당됨.

 

CPU 스케쥴링이 언제 필요한가?

- 한 프로세스가 작업을 하다가 I/O 작업을 할때 자진해서 CPU를 내놓을때 (CPU 자진 반납:논프리미티브)

- 위의 작업이 끝나면 디바이스 컨트롤러가 인터럽트를 걸어서 위의 프로세스의 상태를 레디로 변경시킬때.(강제:프리미티브)(레디상태 : CPU만 얻으면 작동될 수 있는 상태)

- 어떤 프로세스가 CPU를 너무 많이 사용할 때 CPU를 빼앗을때.(강제:프리미티브)(타이머 인터럽트)

- 프로세스가 종료될때.(CPU 자진 반납:논프리미티브)

 

cpu 스케쥴링

출처 : Julia Evans@b0rk 트위터

 

cpu 스케쥴링에는 2가지 이슈가 있다.

1.누구에게 cpu 를 줄것인가?

2.cpu를 특정 프로세스에게 줬을때 언제 빼앗을 것인가?

 

cpu 스케쥴링 알고리즘은 크게 두가지로 나뉜다.

1.논프리미티브 방식(비선점형) : cpu를 자진 반납할때까지 보장해 주는 방법

2.프리미티브 방식(선점형) : 타이머를 두어서 CPU를 강제적으로 뺏는 방법

*cpu 스케쥴링 알고리즘의 성능척도

1.시스템 입장에서 성능 척도 : cpu 하나 가지고 최대한 일을 많이 시키면 좋다. cpu 이용률, 처리률

-cpu 이용률 : 전체 시간중에서 cpu가 놀지 않고 일한 시간의 비율을 나타냄. 전체 시간 중 cpu가 명령을 수행한 시간의 비율

-cpu 처리률 : 주어진 시간동안 몇개의 작업을 처리 했는지를 나타낸다. 주어진 시간동안 cpu 버스트를 완료한 프로세스의 개수. 즉, cpu의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼의 cpu를 사용하고 이번 cpu버스트를 끝내어서, 준비큐를 떠났는지 측정하는 개념

2.프로세스 (고객, 손님)입장에서 성능 척도 :  얼마나 빨리 cpu 서비스를 받을 수 있는가?
-턴 어라운드 타임 (소요시간) : cpu 를 기다렸다가, cpu를 얻어서 다쓰고 i/o를 하러 빠져나갈때 까지 걸린 시간. 프로세스가 cpu요청 시점 부터 cpu 버스트가 끝날때까지 걸린 시간. 즉, 준비큐에서 기다린 시간과 실제로 cpu를 사용한 시간의 합.

-웨이팅 타임 : cpu를 순수하게 기다린 시간. 프로세스가 준비큐에서 cpu를 얻기위해 기다린 시간의 합을 말한다. 이때 대기 시간이란 이번 cpu버스트가 끝나기까지 준비큐에서 기다린 시간의 합을 뜻하게 된다.

-리스판스 타임(응답시간) : 레디큐에 들어와서 최초의 cpu를 얻기 까지 걸린 시간. 준비큐에 들어온 후 첫번째 cpu를 획득하기 까지 기다린 시간을 뜻한다.

 

#중국집 비유

내가 주방장을 고용했다.
이용률 : 나의 입장에서는 주방장이 놀지 않고 일을 많이 해야지 좋다.
처리률 : 단위 시간당 몇명의 손님에게 식사를 대접했나?

소요시간 : 손님이 식당에 들어와서 요리를 먹고 나갈때 까지 걸리는 시간.
웨이팅타임: 손님이 밥을 먹은 시간이아니라 밥을 기다린 시간.
리스판스타임: 첫번째 음식이 나올때 까지 기다린 시간.

 

FCFS

출처 :  https://www.ktustudents.in/2017/10/program-for-fcfs-scheduling-in-c-cs331-lab.html

먼저 온 프로세스(고객)을 먼저 서비스 해주는 서비스 방법 , 비선점형이라서 한번 CPU를 얻으면 뺏기지 않는다.

준비큐에 도착한 시간 순서대로 cpu를 할당 받는 방식. 이 방식은 cpu를 먼저 요청한 프로세스에게 cpu를 먼저 할당하고, 그 프로세스가 자발적으로 cpu를 반납할 때까지 cpu를 선점하지 않는다.

 

-문제점

평균 대기 시간이 길어지게 된다.
CPU를 오래 쓰는 프로그램이 도착하면.. CPU를 짧게 쓰는 프로그램이 래디큐에 있어도 계속 기다려야 한다..
앞에서 CPU를 잡고 있는 프로세스가 길게 잡고 있느냐 짧게 잡고 있느냐에 따라서 평균 시간이 길어진다.
(콘보이 이펙트: cpu 버스트가 긴 프로세스가 먼저 도착해서 cpu 버스트가 짧은 프로세스가 오래 기다려야 하는 현상을 콘보이 현상이라고 한다.)

 

 

SJF

CPU 를 사용하는 시간이 제일 짧은 프로세스에게 CPU를 주는 알고리즘.

(CPU버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식.평균대기 시간을 가장 짧게 하는 최적의 알고리즘. )
큐가 전체적으로 짧아 진다. 전체 기다리는 시간이 짧아지기 때문에, 기다리는 평균 시간을 최소화 한다.

2가지 방식
1.선점방식  : 더 짧은 프로세스가 오면 CPU 제어권을 더 짧은 프로세스에게 넘겨준다.(평균 웨이팅 시간을 최소화 함.)
2.비선점방식 : 더 짧은 프로세스가 와도 현재 CPU를 사용하고 있는 프로세스의 CPU 이용권을 보장해준다.

 

-문제점

현실적으로 프로세스의 cpu 버스트 시간을 미리 알 수 없다.

sjf 알고리즘이 평균 대기 시간을 최소화하는 알고리즘이기는 하지만 시스템에서 평균을 줄이는 것이 항상 좋은 방식이라고는 말할 수 없다. 계속 cpu 버스트가 짧은 프로세스에게만 cpu를 할당할 경우 cpu 버스트가 긴 프로세스는 준비 큐에서 줄 서서 무한정 기다려야 하는 문제가 발생할 수 있다.( 기아현상)

-선점방식은 요구 시간이 긴 프로세스가 요구 시간이 짧은 프로세스에게 항상 양보되어 기아 상태가 발생할 수 있다
-대기 상태에 있는 프로세스의 요구시간에 대한 정확한 자료를 얻기 어렵다는 문제점이 있다.
-단기 스케줄링 보다는 장기 스케줄링에 유리하다

 

우선순위 스케쥴링

우선순위가 높은 프로세스에게 cpu를 주는것. 

1.선점형: 지금 cpu를 얻은 프로세스 보다 우선순위가 더 높은 프로세스가 들어오면 그 프로세스에게 cpu를 준다.

2.비선점형: 지금 cpu를 얻은 프로세스 보다 우선순위가 더 높은 프로세스가 들어와도 그 프로세스에게 cpu를 주지않는다.

 

- 문제점: 우선순위가 낮은 프로세스는 cpu를 얻지 못하고 계속 기다려야 하는 상황이 발생한다.

 

- 해결법 : 에이징. 아무리 우선순위가 낮아도 오래 기다리면 우선순위를 조금씩 높여주는 기법.(예 경로 사상..)

 

라운드로빈 스케쥴링 (현대 cpu)

시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케쥴링 방식.

라운드로빈 스케쥴링에서는 각 프로세스가 cpu를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 이 프로세스로 부터 cpu를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 cpu를 할당하게 된다.

할당시간이 길면 , 라운드 로빈 스케쥴링은 FCFS와 같은 결과를 나타낸다.

할당 시간이 짧으면 cpu를 사용하는 프로세스가 너무 빈번하게 교체되어 문맥교환의 오버헤드가 커지게 된다.

라운드 로빈 스케줄링은 일반적으로 sjf 방식보다 평균 대기시간은 길지만 응답시간은 더 짧다.

라운드로빈 스케쥴링의 기본적인 목적은 cpu 버스트 시간이 짧은 프로세스가 빨리 cpu를 얻을 수 있도록 하는 동시에, cpu 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다. 선점형 스케쥴링이다. cpu를 줄때 시간을 줘서 시간이 다 되면 cpu를 뺏어서 레디큐 맨뒤에 가져다 놓고 그 다음 프로세스에게 cpu를 할당한다.

 

-장점: cpu를 얻는 시간이 빠르다. 응답시간이(리스판스타임)빠르다. 레디큐에서 기다리기만 하면 어떤 프로세스든 cpu을 얻을 수 있다. 

또한 컨텍스트 스위치가 동작하기 때문에 프로세스가 cpu를 뺏겨도 어디까지 실행되었는지 알 수 있다.

 

-주의점 : 할당 시간을 크게 잡으면 fcfs 알고리즘과 같아진다. 할당시간을 짧게 잡아놓으면 컨텍스트 스위치가 많이 발생해서 오버헤드가 너무 자주 발생한다(시스템 성능 저하)

 

FCFS와 비교

FCFS에서는 cpu를 먼저 쓰고 나가는 프로세스의 소요시간 및 대기 시간이 짧아지는 반면 라운드 로빈 스케줄링에서는 cpu를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 소요 시간 및 대기 시간이 가장 오래 기다린 프로세스에 맞춰 지게 된다.

따라서 라운드 로빈 스케줄링이 FCFS에 비해 평균 대기 시간 및 평균 소요 시간이 거의 두배가 된다. 

이는 동일한 cpu 버스트 시간을 가지는 프로세스들에 대해 라운드 로빈 스케줄링을 적용할 경우 평균대기시간 및 평균 소요시간이 더 길어진다는 의미가 된다. 그라나, 이 경우에도 평균 응답 시간은 더 짧아지게 된다.

 

 

참고: 이화여대 반효경 교수님 운영체제 강의정리