10강 CPU scheduling 1

https://core.ewha.ac.kr/publicview/C0101020140328151311578473?vmode=f 

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

 

cpu 스케쥴링 드디어 시작

지난 수업에 설명했던 내용 일단 쭉 설명이다 -> cpu burst랑 프로그램들의 cpu 흐름들에 대한 설명

 

cpu 스케쥴링:

현재 ready queue에 들어와있는 프로세스들중 어떤 프로세스에게 cpu 를 줄것인가에 대한 메커니즘

 

cpu를 주는데 두가지 이슈가 있다.

1. 누구에게 줄것인가?

2.cpu 점유 시간(중간에 뻇을것인가? 얼마나 줄것인가?)

 

효율적으로 사람과 소통하는 것들에게 주로 주는 방향으로 설계됨 

 

스케 쥴링 알고리즘에는 여러가지가 있음

 

크게 두가지로 나누자면

nonpreemptive 한것 -> cpu 중간에 강제로 뺏어오지 않는것 (비선점형) -> 아 이게 비선점형이구나 미친 코루틴은 비선점형 멀티태스킹이다 와 신기하다.

preemptive 한것 -> cpu 중간에 뻇어오는것(선점형) -> 쓰레드는 선점형 멀티 태스킹이다

이 두가지가 있다. 

 

현대적인 cpu 는 다 선점형 스케쥴링을 사용하고있다.

 

 

그래서 각 스케쥴링 알고리즘이 뭐가 좋은지 판단하려면 성능 척도가 필요할것이다.

 

cpu 스케쥴링을 위한 성능척도는 위의 그림과 같은데

크게 두가지로 나눌수있다.

 

일단 이 성능척도의 단위가 매cpu 버스트 단위이다-> ex) I/O와 I/O 사이 처럼 한번 쭉 cpu 잡고 처리해야하는 일단위 

 

1. 시스템 입장에서 성능 척도 -> cpu를 일을 야무지게 계속 시키는 정도

-cpu 이용률

    -> 전체시간중 cpu가 놀지않고 일하는 시간을 말함 -> cpu는 계속 일을 시켜야함

-처리량

    -> 주어진 시간동안 몇개의 작업을 완료했는가?  -> 주어진 시간동안 처리한 일의 양이 많아야 좋으니까

 

2. 프로그렘 입장에서 성능 척도 -> 프로그램이 얼마나 시간이 빨리 끝날수 있는가?(프로세스 입장)

-소요시간,반환시간(대기시간 + cpu 사용시간)

    -> cpu를 쓰러들어와서 다쓰고 나가는 시간

    I/O가 끝나서 cpu를 쓰러 들어와서 줄서서 기다리는 시간 + cpu 쓰는 시간 + 다음 I/O 하러 나가는 때 까지의 시간

-대기시간

    -> 기다리는 시간을 의미 cpu를 쓰려는데 순수하게 기다리는 시간

-응답시간

    -> ready queue에 들어와서 처음으로 cpu를 얻기까지 걸리는 시간 -> waiting time 이랑 다른점은 선점형의 경우 뻇겼다 다시썻다를 밥먹듯이 하니까 중간에 기다린 시간 다모은 것이고 응답시간은 ready queue 에 들어가고 나서부터 처음으로 얻을때까지 기다린 시간 즉 I/O 같은거 끝나고 cpu 최초로 얻을때까지 기다리는 시간

 

 

이제 스케쥴링 알고리즘 쭉 볼것이다

 

1. fcfs -> 알고리즘이라고 하기도 뭐하다 그냥 먼저온 일 먼저 cpu 주는것이다 -> 비선점형 이다.

    효율적이지 않다. -> cpu 오래쓰는게 먼저 일을 잡으면 응답성이 필요한것들도 기다리게 된다. 

 

이 fcfs 자료에서 두개를 비교해보면 위에것은 오래걸리는 일이 먼저온경우이고 그럼 waiting time 이 평균이든 그냥이든 길어지는데

그에비에 짧게 처리할수있는 일이 먼저오면 waiting time 는 짧아진다.

 

어떤 프로세스가 먼저 들어오냐에 따라서 대기시간이 엄청 차이나게 된다. 

 

앞쪽에 처리시간이 긴 프로세스 들어와서 안좋아지는 상황을 convoy effect 라고 한다.

 

2.sjf

cpu 짧게 쓰는것부터 처리한다

전체적으로 일단 좋은 결과가 나옴

큐가 전체적으로 짧아짐 짧은 일들 일단 처리하고 나가버리니까

sjf 스케쥴링 알고리즘이 average waiting time(평균 대기시간) 부분을 제일 최소화를 보장한다.(선점형 버전이 보장함)

 

이 알고리즘은 선점형 비선점형으로 나뉨

비선점형 : 일단 일을 주면 다 끝날때까지 cpu 를 뻇기지 않음

선점형: 처리시간 더짧은 프로세스 큐에 들어오면 뻇어서 개한테 먼저줌 -> srtf 라고도 부름 현재 남은 시간을 기준으로 주므로

 

 

이게 sjf의 비선점형 예시이다 

보면 0초시점에는 p1만 큐에 들어왔으므로 일단 길어도 그것부터 다 처리하고 그 이후에 큐에 들어와있는 것중 짧은순서로 사용한다

-> 평균 대기시간:4초

 

선점형의 경우이다

일단 마찬가지로 최초에는 큐에 p1만 들어있으므로 cpu를 p1에게 주지만 p2에게 뺏긴다 -> 중간중간 계속 뻇기고 뻇긴다 더짫은거 현재있으면 그냥 뻇어서 줘버린다.

이러면 대기시간 평균 3초가 된다. -> 어떤 알고리즘을써도 이게 최소이다.

 

cpu 스케쥴링이 언제 이루어지는가?

비선점형의 경우 cpu 를 프로세스가 다쓰고 나가는 시점에 스케쥴링을하고

선점형의 경우 대기큐에 프로세스가 들어갈때 마다 새롭게 스케쥴링을한다.

 

이 알고리즘은 두가지 문제점이있다.

1. starvation(기아현상 ㅋㅋㅋㅋ)

    극단적으로 cpu 사용시간이 짧은것들을 선호하므로 cpu 사용시간이 긴것들이 아예 영원히 cpu를 못받을수있다.

    -> 짧은것들만 계속 들어오면 계속해서 순서가 밀리니까

2.cpu 사용 시간을 예측할수가 없다

사용자에게 input 을 받아서 실행하기도하고 각 분기처리에의해 처리코드량이 달라지기도하고 해서

cpu 사용시간을 정확히 예측할수가 없다.

큐에 들어가는 시점에 cpu burst 시간을 예측할수가 없어서 실제로 사용하기 애매하다.

-> 사용시간을 정확히 알수는 없지만 추정은 가능하기에 뭐 이걸 쓰고싶다면 cpu 를 과거에 얼만큼 사용했는가에 따라서 예측해서 그값을 가지고 추정값으로 사용한다(프로그램 대부분 비슷한 패턴을 보이기 때문)

exponential averaging 이방법으로 예측한다는데 뭐 어짜피 이것까지 외울 필요는 없을테니 예측하는 수식이 있다 정도만 알아놓자

비교적 가까운 과거에 가중치를 둬서 예측하는 방법이다.

 

3.priority scheduling (우선순위 스케쥴링)

우선순위가 제일 높은 프로세스에게 cpu를 할당하겠다는 개념이다.

-> 이것도 선점형 비선점형 개념이있다

비선점형: 일단주면 일다끝날때까지 냅둠

선점형: 중간에 우선순위 더 높은애 들어오면 뼷음

 

우선순위를 정의하는 방법을 다루지는 않는데

다양하게 정의할수있다고 한다. 

우선순위를 정수로 대부분 표현하는데 크기가 작을수록 우선순위가 높은것이다. (일반적인 시스템에서 리눅스 같은것)

 

sjf 도일종의 우선순위 스케쥴링이다.(cpu 사용시간이 우선순위인것)

 

우선순위 스케쥴링의 문제점이 

starving 여기서도 나타난다 -> 우선순위가 낮으면 영원히 굶을수있음

 

효율성도 효율성이지만 또 어떤 프로세스가 너무 소외 당하는것은 막아야한다.

 

그래서 starvation 막을 방법으로 aging 기법을 사용한다.

 

Aging:

아무리 우선순위가 낮아도 대기시간이 길다보면 우선순위를 높여주는것이다. -> starvation을 막아준다.

 

4. round robin

현대적인 cpu 스케쥴링은 round robin 에 기반하고 있다.

타이머 시간설정해놓고 주고 이런게 다 round robin 에서 하는 일이다. 

이것은 당연히 선점형 스케쥴링이다.

 

cpu를 줄때 동일한 크기의 할당시간을 주고 할당시간이 끝나면 ready queue 맨뒤에 가서 줄을 선다.

 

가장 좋은 점은 응답시간이 빨라진다 -> cpu 를 조금씩 분할해서 나눠주니까

 

cpu 얼마나 쓰는지 예측도 필요없는게 그냥 조금씩 주니까 조금만 사용하는 것들은 그냥 조금씩 줘도 지 일처리 다하고 나가버림 그래서 장점이다

 

n개의 프로세스가 큐에있으면 적어도 (n-1)할당시간 후에는 무조건 cpu를 한번 얻게된다.

 

대기시간이 cpu 사용시간에 비례해진다 -> 짧게 사용하려는 프로그램은 애초에 짧은 대기시간을 갖고 길게 사용하려는 프로그램은 대기시간도 길어진다. 

짧은 사용량은 짧게 쓰고 나가버리니까 대기시간이 줄어든다

 

round robin 을 극단적으로 적용해보면

할당시간을 미친듯이 길게하면 fcfs 와 같아지게 되고

할당시간을 너무 잘게 짤라버리면 context switch 오버헤드가 커져서 시스템 자체의 성능이 줄어들수있다.

->대충 10~100 ms 를 주는게 평균적이다. 

 

rr을 사용한 예시이다 

rr은 sjf 보다 평균 소요시간이나 대기시간은 길지만 응답시간이 짧다

 

 

round robin 의 경우 cpu 사용시간을 예측하기 힘들때 무작위로 사용하는것에서 강하다.

일정한 시간이 예측되는 경우에는 오히려 안좋을수도있다. 근데 일반적으로는 이럴일이 없으니 round robin 이 좋다.