[03] Process Scheduling

 

 

1. 스케줄링(Scheduling) 이란?

일반적인 스케줄링이란 처리할 일들의 진행순서를 정하는 일입니다. 이 개념은 컴퓨터에서도 동일하게 적용된다고 보시면 됩니다. 프로세스 스케줄링이란 CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 일을 말하고 디스크 스케줄링은 디스크를 사용하려고 하는 프로세서들 사이의 우선 순위를 관리하는 일들을 말합니다.

스케줄링은 처리율과 CPU 이용률을 증가 시키고 오버헤드/응답시간/반환시간/대기시간 을 최소화 시키기 위한 기법입니다. 즉, CPU가 쉬지않고 계속 열심히 일할 수 있도록 효율적인 계획을 잡아 주는걸 스케줄링이라고 생각하시면 되겠습니다.

 

2. 비선점 스케줄링과 선점 스케줄링

스케줄링의 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있습니다. 비선점형 스케줄링은 프로세스가 실행->대기, 실행->종료로의 상태전이가 있을때 적용되며 선점형 스케줄링은 실행->대기,실행->준비,대기->준비,수행->종료 모든 상태변화에서 적용됩니다. 상태전이는 http://blog.naver.com/bsy9109/130166630482 여기를 참조하시면 됩니다.

비선점 스케줄링은 이미 할당된 CPU를 다픈 프르세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법입니다. 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드도 적습니다. 일관처리 시스템에 적합하고, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점도 있습니다.

선점 스케줄링은 하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법입니다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있으며, 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할수 있습니다.

놀이기구를 탈려고 많은 사람들이 긴 줄을 서 있을때 선점형은 강력한 권한을 가지고 있기 때문에 줄을 서지 않고도 맨 먼저 놀이기구를 탈수 있지만 비선점형은 아무리 급한 사정이 있다 하더라도 권한이 없기 때문에 줄을 서서 기다리고 자기 차례가 되어서야 놀이기구를 탈수 있다고 생각하시면 될꺼 같습니다

 

3. 비선점형 스케줄링 알고리즘 : FIFO, SJF, HRN

-FIFO(First In First Out) : 가장 간단한 방식으로 선입선출의 방식입니다. 먼저 들어오면 먼저 나가는 방식입니다. 아무리 중요한 작업이 있다 하더라고 그 작업 보다 먼저 들어온 작업이 끝나기 전까지는 절때 먼저 실행될수 없는 비효율적인 방식이라고 말할 수 있습니다. FIFO라고도 하고 FCFS(First Come First Served Scheuling)이라고도 합니다.

-SJF(Shortest Remaining Time First Scheduling) : 평균 대기 시간을 최소화 하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식입니다. 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 연기 상태에 빠질수 있다는 단점이 있습니다.

-HRN(Highest Response-ratio Next) : 실행시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식입니다. '우선순위 = (대기시간+서비스시간)/서비스시간' 의 공식을 이용하여 우선순위를 계산하여 우선순위가 높은 것부터 실행하는 방식입니다. 이렇게 프로세스가 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로서 무한연기의 문제를 방지하는걸 에이징(Aging) 기법이라고 합니다.

 

4. 선점형 스케줄링 알고리즘 : SRT, RR, MQ

-SRT(Shortest Remaining Time) : 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법입니다. SJF처럼 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식입니다. 단지 차이점은 선점형으로 바뀌어 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행 시킬수 있는 권한이 생겼다는 것입니다.

-RR(Round Robin) : 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당하는 방식입니다. 보통 시간 단위는 10ms ~ 100ms 정도이고 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 됩니다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하합니다. 할당되는 시간이 클경우 비선점 FIFO 기법과 같아지게 됩니다.

-다단계 큐(MQ, Multi-level Queue) : 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 분비 상태 큐를 사용하는 기법입니다. 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없습니다. 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 합니다.

 

 

 

사진에 보이는 것처럼 Level1,2,3로 큐가 불리 되어 있습니다. 레벨1의 큐가 모두 완료 되어야만 레벨2의 큐로 넘어갈수 있고 레벨2의 큐가 모두 완료되어야 그다음으로 넘어 갈수 있는 방식입니다.

-다단계 피드백 큐(MFQ, Multi-level Feedback Queue) : 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 분배 상태 큐로 이동할 수 없는 다단계 큐 기법을 준비 상태 큐 사이를 이동할 수 있도록 개선한 기법입니다.

[출처] [운영체제] 5. 프로세스(스케줄링)|작성자 보리