[운영체제] cpu 스케쥴링

강의: 비전공자를 위한 운영체제

 

cpu 스케쥴링 개요

운영체제는 모든 프로세스에게 cpu를 할당/해제하는데 이를 cpu 스케쥴링이라 함.(이전에 정리한 글: https://lovenewthing.tistory.com/74)

이때 고려해얄 것 두가지가 있는데, 이는 컴터 성능에 매우 큰 영향을 미침.

1. 메모리에 있는 수많은 프로세스 중 어떤 프로세스에게 cpu사용권을 줘야 하는가.

2. cpu를 할당받은 프로세스가 얼마의 시간동안 cpu를 사용해야 하는가.

 

cpu를 할당받아 실행하는 작업: cpu burst.

입출력 작업: I/O Burst

 

다중 큐

이 그림 알징~ 여기서 프로세스가 대기하고 있는 "준비상태"와 "대기상태"는 큐라는 자료구조로 관리됨.

 

실행->준비->실행상태 과정)

프로세스가 실행상태에서 준비상태로 돌아갈 때 운영체제는 해당프로세스의 우선순위를 보고 그에 맞는 준비 큐에 넣음. cpu스케쥴러는 준비상태의 다중큐에 들어있는 프로세스들 중에 적당한 프로세스를 선택해서 실행상태로 전환시킴.

 

실행->대기->실행)

프로세스가 실행상태에서 I/O요청받아 대기상태로 오게 되면 I/O작업 종류에 따라 분류된 큐에 들어가게 됨. 그리고 그 작업이 완료되면 다시 그 해당 큐를 뒤져서 꺼내감.

 

그러나 사실 큐에 넣는건 프로세스를 넣는게 아니라 프로세스 정보를 담고 있는 PCB가 들어가는거임.

 

스케쥴링 목표

1. 리소스 사용률

cpu사용률 또는 I/O디바이스 사용률 높이는 것.

 

2. 오버헤드 최소화

스케쥴링하기 위한 계산이 너무 복잡하거나 컨텍스트 스위칭 너무 자주하면 오히려 안좋을 수 있음.

 

3. 공평성

모든 프로세스에게 공평하게 cpu가 할당되어야 함.

 

4. 처리량

같은 시간내에 더 많은 처리할 수 있도록.

 

5. 대기시간

대기시간 짧도록

 

6. 응답시간

얘도 짧도록

 

그러나 모든걸 다 이룰 순 없음. 처리량을 높이려면 cpu 할당시간이 많아져야 하는데 응답시간을 줄이려면 여러 프로세스에 cpu를 골고루 할당해야 하기 때문에 서로 상반되서 모두 이룰 수 없음. 따라서 목표가 무엇인지 초점을 맞춰서 해야 함.

 

FIFO 알고리즘

단순히 먼저 들어온 순서대로 cpu가 프로세스를 처리하는 것임.

장점은 직관적이란 것.

단점은 다음과 같다.

 

단점1.

빨리 끝날 수 있는 프로세스가 길게 걸리는 프로세스가 다 끝날때까지 기다려야 함.

 

단점2.

I/O작업이 있다면 I/O작업이 끝날때까지 cpu가 쉬어서 cpu사용률이 떨어짐.

 

 

- 평균대기시간

스케쥴링의 성능은 "평균대기시간"으로 평가함. 프로세스 여러개가 실행될 때 이 프로세스들 모두가 실행되기까지 대기시간의 평균을 말함. 

 

FIFO알고리즘은 프로세스 순서에 따라 성능차이가 심하게 나서 현대 운영체제에서는 잘 안쓰인다.(Burst time이 짧은게 먼저 실행되면 평균대기시간이 짧아지고, Burst time이 긴게 먼저 실행되면 평균대기시간이 길어짐!)

 

 

SJF(Shortest Job First)

Burst time이 짧은 거 먼저 실행하기(짧은작업 먼저하기).

이론적으로는 FIFO보다 효율적임. 그러나 문제가 있어.

 

문제1.

실제론 어느 프로세스가 먼저 실행될지 예측하기가 힘들다.

ex) 인터넷브라우저도 키고 뮤직플레이어도 켰어. 근데 노래 한곡만 듣고 끝낼수도 있고 노래 하루종일 들을수도 있어.

따라서 프로세스 종료시간 예측은 거의 불가능

 

문제2.

Burst time이 길면 아예 실행이 안될 수도 있음. 왜냐면 짧은애들 계속 들어오면 긴 애들은 계속 뒤로 밀려나니까.

 

RR(Round Robin)

FIFO에서 단점을 해결하기 위해, 한 프로세스에게 일정시간만큼 cpu를 할당하고 할당시간 지나면 강제로 다른프로세스에게 일정시간만큼 cpu를 할당함. 글고 강제로 cpu뺏긴 프로세스는 큐의 가장 뒤로 밀려남.

 

- 타임슬라이스( 또는 타임 퀀텀)

프로세스에게 cpu 할당하는 일정시간.

 

RR이 FIFO보다 평균대기시간이 짧게 나오겠지만, 둘이 비슷하다면 RR이 더 비효율적인 것임. 왜냐면 컨텍스트 스위칭을 하기 때문에 시간이 더 추가되기 때문임. 

 

RR성능은 타임슬라이스 값에 따라 크게 달라짐.

i)타임슬라이스가 무한대로 큰 경우

FIFO알고리즘과 동일

 

ii)타임슬라이스가 매우 작은경우

웹브라우저와 뮤직플레이어가 동시에 동작하는 것처럼 느껴짐. 그러나 너무 컨텍스트 스위칭이 자주 일어나면, 타임슬라이스에서 실행되는 프로세스의 처리량보다 컨텍스트 스위칭처리하는 양이 훨씬 커져서 "오버헤드가 너무 커짐".

 

그렇다면 최적의 타임슬라이스는 사용자가 느끼기에 프로세스가 버벅거리지 않고 동시에 실행되는 것처럼 느껴지면서 오버헤드가 크지 않은 값을 찾는것임...(윈도우즈는 20ms, 유닉스는 100ms임)

 

 

 

MLFQ(Multi Level Feedback Queue)

오늘날 가장 많이 쓰임. RR의 상위호환임.

이건 다시 정리하자..