Scheduling in Interactive Systems

인터렉티브 시스템에서는 한 프로세스가 cpu를 독점하지 않도록 해야한다.

그러기 위해서 퀀텀이라는것을 사용한다.(퀀텀 == 한프로세스에게 할당된 cpu시간)

Round Robin Scheduling

배치 시스템의 스케쥴링 알고리즘중 SJF와 약간 구조는 비슷하다.

SJF에서는 차례대로 들어오는 프로세스를 무조건 처리할때까지 cpu를 할당하지만 RR에서는 일정시간 cpu를 퀀텀동안 할당해주고 그 다음 프로세스를 차례대로 실행시키며 퀀텀을 다쓴 프로세스는 큐의 맨 뒤로 보내진다.

퀀텀을 얼만큼 할당해야 하는가?

너무 짧은 경우 : process switch(context switch)가 많이 발생 해서 cpu 효율이 떨어진다. (오버헤드가 커진다)

너무 긴 경우 : 반응시간이 안 좋아진다. 다른 프로세스들의 대기시간이 길어지므로 사용자가 답답해 할 수 있다.

Priority Scheduling

각각의 프로세스에 우선순위가 할당된다. 우선순위가 제일 높은게 젤 먼저 실행된다.

우선순위 높은 프로세스 혼자 cpu를 독점하는것을 막아야 한다.

-> 클럭이 튈때마다 우선순위를 깎아준다. 언젠가는 우선순위가 낮아져 다음 우선순위에 있는 프로세스가 실행될것이다.

우선순위로 스케쥴링하므로 퀀텀은 줄수 있는 만큼 최대한으로 많이 준다.

우선순위 할당하는법

정적 우선순위 할당 - 유저가 누구냐 가격이 얼마냐에 따라 프로세스에 높은 우선순위 미리 정함.

동적 우선순위 할당 - I/O bound 프로세스에게 높은 우선순위를 준다. 

- 우선순위 계산법 : 1/f 

- f = cpu 사용시간/ 퀀텀

- cpu 사용시간이 적은 i/o bound 프로세스는 분자가 작으므로 역수를 취하게 되면 우선순위는 커지게 된다.

- 즉 I/O bound 프로세스에게 더 높은 우선순위가 할당되게 된다.

Round Robin + Priority Scheduling

멀티플 큐 - CTSS(Compatible Time Sharing System)

Priority 1,2,3,4라는 클래스들끼리는 우선순위 스케쥴링을 하고 각 클래스 내에서는 라운드 로빈 스케쥴링을 해준다.

우선순위 클래스가 낮아질수록 퀀텀이 더 길어지게 된다. 

이렇게 되면 실행시간이 적은 i/O 바운드 프로세스들이 높은 우선순위를 받는 대신 퀀텀이 적고 

cpu 바운드 프로세스들은 낮은 우선순위를 가지는 대신 긴 퀀텀을 갖는다.

Priority4의 맨처음 프로세스부터 실행되게 되는데 만약 그 프로세스가 퀀텀을 전부다 사용하면 우선순위가 낮아진다.

P4의 프로세스가 퀀텀을 다 사용시 P3클래스로 강등되게 된다.

만약 퀀텀을 다 사용하지 않으면 그 프로세스는 다시 실행 되더라도 원래의 우선순위(원래의 클래스)로 다시 실행된다.

만약 100 퀀텀이 필요한 프로세스가 있다고 치자

라운드 로빈 알고리즘으로 이 프로세스를 실행시키면 컨텍스트 스윗칭이 100번이 일어난다. (오버헤드가 크다)

그런데 이 CTSS알고리즘을 사용하면 최상위 우선순위에서 1퀀텀 그다음 우선순위에서 2퀀텀 ,그다음에서 4퀀텀, 8퀀텀, 16...

각 클래스에서 사용되는 퀀텀을 합쳐보면 1+2+4+8+16+32+64 7번의 컨텍스트 스윗칭만 일어나면 프로세스의 실행을 완료 시킬수 있다.

CTSS알고리즘은 프로세스의 너무 빈번한 Context Switching 문제를 해결한 것이다.

그냥 라운드 로빈 알고리즘만 썼을때 보다 CTSS가 더 좋은점

-> 오버헤드가 줄어들었다.(Context Switching)

질문

그냥 우선순위 알고리즘만 썼을때 보다 CTSS가 더 좋은점??

CTSS알고리즘은 비선점형 알고리즘인가??

우선순위가 낮은 프로세스들이 굶어 죽을수 있다는 문제점이 있다.