[운영체제] 이화여대 반효경 교수님 수업 필기 CPU Scheduling 1,2

Event Latency

 

core.ewha.ac.kr/assets/publish/C0101020140328151311578473

반효경 [운영체제] 10. CPU Scheduling 1

 

 

 

컴퓨터에서 돌아가는 process 들은 IO bound job 도 있고 CPU bound job 도 있기 때문에

CPU 스케줄링이 필요함.

 

CPU 스케줄링은 ready queue 에 있는 process 들 중 어떤 process 에게

CPU 제어권을 줄 것인가 결정하는 것을 말 함.

 

모든 process 에게 공평하게 CPU 를 주고싶어서

CPU 를 오래 쓰는 CPU bound job 에게 CPU 를 줘버리면,

CPU 를 조금만 쓰고 나가는 IO bound job 들이 계속 기다려야 함( 기다리는 사용자도 지루해짐 )

그래서 공평한 스케줄링보다는 유연한 스케줄링이 필요.

 

현대엔 preemptive, 즉 강제로 CPU 를 빼앗는 CPU 스케줄링 방법을 주로 사용.

 

 

 

아래는 여러가지 CPU Scheduling Algorithm 임

ㅠㅠ갑자기 projector 화면이 작아져서 알아보기가 힘드네

 

 

 

< FCFS : First Come, First Served >

 

먼저 온 순서대로 먼저 처리함.

무슨 process 인지, 우선순위가 어떤지도 따지지 않고 그냥 먼저 오는 순으로 처리.

이것은 nonpreemptive 스케줄링임. 즉, CPU 를 갖게 되면 자발적으로 내려놓지 않는 이상

CPU 를 빼앗기지 않음.

이것은 비효율적임. CPU 를 길게 쓰는 IO Bound 가 먼저 와서 CPU 점유해버리면

나중에 온 CPU Bound 잡들이 계속 기다리게 되기 때문에 비효율적임.

이렇게 긴 job 때문에 짧은 job 들이 큐에서 기다리는 현상을 Convoy Effect 라고 함.

 

 

 

 

< SJF : Shortest Job First >

 

실행 시간이 짧은 Job 부터 처리함.

스케줄링 기법 중 Job들의 평균 대기 시간(Average Waiting Time) 이 가장 짧음.

근데 긴 Job 이 영원히 기다릴 수 있음(이것을 starvation 현상이라고 함)

preemptive 버전과 nonpreemptive 버전이 있음.

preemptive 버전은, 짧은 job이 CPU 점유하고 있는 와중에 더 짧은 job이 오면 CPU 를 빼앗김.

nonpreemptive 버전은 빼앗기지 않고 다 끝낸 다음에 가장 짧은 job이 CPU 를 얻음.

 

 

 

 

 

 

< Priority >

 

우선순위가 제일 높은 Process 먼저 CPU 를 줌

이 역시 preemptive 버전과 nonpreemptive 버전이 있음.

또한 starvation 현상 역시 발생 가능.

starvation 을 방지하기 위해, Aging 이라는 기법을 사용.

우선 순위가 낮은 Process 가 순서를 빼앗기면서 오래오래 기다리게 되면,

오래 기다린 만큼 우선 순위가 올라가서 CPU 를 점유할 수 있도록 기법.

 

 

 

 

 

< Round Robin >

 

위의 스케줄링에서는 preemptive 가 아닌 이상에야 job 이 끝날 때 까지 CPU 를 선점하지만,

RR 은 CPU 를 줄 때 정해진 시간 만큼만 줘서 job 이 끝나지 않았음에도 CPU 를 강제로 빼앗음(preemptive)

process 들이 CPU 를 최초로 얻기까지 걸리는 시간인 '응답시간 response time' 이 빨라짐.

왜냐면 CPU 를 조금씩 줬다 빼앗었다 하기 때문에.

CPU 를 나눠주는 기준은? 모든 Process 에게 균등하게 기회를 한 번씩 주나봄.

그러면 FCFS 의 time preemptive 버전이라고 볼 수 있을까? 그렇다.

 

RR 의 특징 중 하나는, 

CPU 를 길게 쓰는 process 는 기다리는 시간이 길고 (CPU 기다리는 횟수가 많음)

CPU 를 짧게 쓰는 process 는 기다리는 시간이 짧음 (CPU 기다리는 횟수 적음)

왜냐면 짧은 process 들은 n만큼 기다렸다가 CPU 할당받고 금방 쓰고 나가는데

긴 process 들은 n만큼 기다렸다가 CPU 할당받고 쓰고 빼앗기는 일을 여러번 반복해야 하기 때문에.

 

CPU 를 점유하는 시간을 q 라고 하자.

q를 길게 하면 할수록 FCFS 와 똑같아지고(Convoy Effect)

q를 짧게 하면 CPU 점유하는 process 간 context switching 이 계속 일어나기 때문에 시스템 전체 성능이 떨어짐

적당한 q 가 좋음 ( 대략 10~100 ms 라고 함 )

 

SJF 보다 average turnaround time 이 길지만

response time (최초로 CPU 를 받는 데 걸리는 시간) 은 짧다. 

응답 시간이 짧다는 것이 중요한 장점!

 

실행 시간이 모두 100s 로 똑같은 job 이 5개가 있다고 하자.

RR 의 q가 1초라면, 5개의 job 들은 1초씩 번갈아가며 CPU 를 할당받다가, 500초가 될 때

5개의 job 들이 차례대로 끝이 나게 된다.

이 말은, 500초 동안 어떤 job들도 끝나지 않는다는 말.

차라리 q를 100으로 두어서, 100초에 job 하나 끝내고, 200초에 job 하나 끝내고...

하는 편이 먼젓번의 예보다는 나음.

일반적으로는 긴 process 와 짧은 process 가 섞여있기 때문에 위의 일이 많이 일어나지 않음 

이런 특수한 상황도 있다는 걸 알아두자.

 

 

 

 

< Multilevel Queue >

 

 

Multilevel Queue 는 우선순위가 각기 다른 레디큐를 여러개 두는 것임.

위에 이미지에서 보는 것 처럼, 가장 위에 system 이 1순위,

그 다음 interactive 가 2순위, ,,, 마지막 student 가 5순위임.

이렇게 계급별로 나눠진 큐에 각 process 들이 들어가서 기다림.

CPU 는 하나뿐이기 때문에, 1순위 큐에 있는 process 들이 먼저 CPU 를 사용함.

1순위 큐가 비면 2순위 큐의 process 들이 CPU 를 사용하고....

이렇게 큐의 계급을 따라서 CPU 를 사용하게 됨.

 

여기서 우선순위의 기준은 무엇인가?

또한 하나의 큐에서 CPU 를 사용하는 기준은 또 무엇인가?

전자와 후자의 기준은 상황에 따라 다를 수 있음.

process 들은 전자의 기준에 따라 들어가는 큐가 달라지게 될 것임.

여기서 말하는 상황이라는 것을 아래 예를 들어 이해해보자.

 

 

위의 이미지와 같이, 두 개의 큐 (foreground, background) 가 있다고 하자.

이 두 개의 큐의 우선순위는 foreground 가 높다.

forground 큐에서 process 를 선출할 때는 RR 방식을 이용(왜냐면 interactive 한 process 이기 때문에

응답 시간이 빨라야 하므로)

background 큐에서 process 를 선출할 때는 FCFS 방식을 이용(왜냐면 batch job 이라서

응답시간이 빠를 필요없이 천천히 진행해도 괜찮기 때문)

 

근데 forg 에 process 가 계속 쌓이면 우선순위가 낮은 backg 내의 process 들이 영원히 처리되지 않는

startvation 현상이 빚어질 수 있기 때문에, time slice 를 둠.

8:2 로 두어서, 적어도 단위 시간의 20%는 backg 가 쓸 수 있도록 함.

 

 

 

 

Multilevel Feedback Queue 도 있는데, 복잡해서 여기 설명은 적지 않고 그냥 넘어가겠음.

 

 

 

 

 

여태까지 CPU 가 하나인 상황에서의 스케줄링 기법에 대해 알아봄.

이제는 CPU 가 여러개일 때의 스케줄링 기법에 대해 알아보자.

 

 

위에 써 있는 것처럼, CPU 가 여러개면 스케줄링이 더욱 복잡해짐.

자세히 다루지는 않음.

 

 

 

 

< Real-Time Scheduling >

 

Hard Real-Time system : 반드시 정해진 시간 내에 task 를 끝내도록 스케줄링해야 함.

정해진 task 처리 시간을 넘기면 실패하는 경우 (자동차의 air-bag 등)

 

Soft Real-Time system : 일반 프로세스에 비해 높은 priority 를 갖고 task 를 실행함

정해진 task 처리 시간을 넘기면 성능이 감소하는 경우 (streaming video 등)

(그래서 최대한 빨리 끝낼 수 있도록. dead line 이 있긴 하지만 조금 넘어도 상관 없음)

 

이벤트가 발생하고 나서부터 응답 할 때까지의 시간을 Event Latency 라고 함

 

 

 

< Thread Scheduling >

 

User level thread : process 내부에서만 thread 의 존재를 알고 있음. 커널은 몰라.

 사용자 process 가 직접 thread 를 관리.

Kernel level thread : 커널이 process 내부의 thread 존재를 알고 있음.

 

Local Scheduling : 사용자 Process 가 CPU 를 잡고 있을 때,

Process 가 직접 어떤 thread 에게 CPU 를 나눠줄지 스케줄링하는 것.

커널은 이 Process 에게 CPU 만 줄 뿐 thread 관리 측면에서는 전혀 손대지 않음.

 

Global Scheduling : 커널이 thread 의 존재를 알고 있고 직접 thread 를 관리하고 CPU 스케줄링함.

커널이 특정 스케줄링에 의해 Process 에게 CPU 주듯이

thread 에게도 특정 스케줄링에 의해 CPU 를 나눠줌.