[운영체제] 프로세스 스케줄링

프로세스 스케줄링이란?

프로세스 스케줄링은 CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업이다. 즉, CPU가 할 일을 적절하게 스케줄링해준다고 볼 수 있다. 예를 들어, CPU가 하나뿐인 시스템인 단일 처리 시스템에서는 운영체제의 CPU 등의 자원을 얻으려는 작업 A와 B가 있을 때, A가 이미 실행 중일때는 이 작업이 끝나야 B작업을 수행할 수 있다. 반면에 CPU가 여러 개인 다중 처리 시스템에서는 운영체제의 스케줄러가 자원을 사용하려는 프로세스들에 자원을 적절히 분배해서 할당한다. 결국 CPU가 놀지 않도록 이거해라 저거해라 해준다는 의미이다.

 

스케줄링을 통해서 우리가 가지는 이점은

 

• CPU의 처리율 증가 : 같은 시간 동안 프로세스를 처리하는 비율 증가
• CPU 이용률을 증가 : 프로세스 실행 중에 입출력 명령 실행등의 원인에 의해 발생할 수 있는 CPU 낭비 시간을 줄이고 순수하게 프로세스가 CPU를 이용하는 비율을 증가. (CPU 수행시간 / 시스템 구동시간 (%))
• 오버헤드 최소화 : 오버헤드를 최소화.
• 응답시간 최소화 : 프로세스들이 입력되어 수행하고 결과 산출까지 걸리는 시간 최소화. 응답시간 = 대기시간 + 수행시간. Response Time / Turnaround Time
• 대기시간 최소화 : 프로세스가 프로세서에 할당 되기까지 (자원을 할당받을 때까지) 대기 큐에 대기하는 시간 최소화. 
• 무한 연기 회피 : 자원을 사용하기 위해 무한정 연기되는 상태를 회피한다.

*수행시간 : 해당 프로세스가 완료까지 실행되는 시간.

 

프로세스의 상태 전이

프로세스의 상태 전이는 하나의 작업이 컴퓨터 시스템에 입력되어 완료되기까지 프로세스의 상태가 준비, 실행 및 대기 상태 등으로 변하는 활동을 말한다. 활동 상태는 프로세스가 기억장치를 할당 받은 상태이고, 지연 상태는 기억장치를 할당 받지 못한 상태이다.

 

• 생성: 프로세스가 생성되는 중인 상태
• 준비: 아직 프로세스가 실행되지는 않지만 CPU를 할당 받으면 실행될 수 있는 상태
• 실행: 현재 프로세스가 실행중인 상태
• 대기: 입출력 발생과 같은 Block 때문에 입출력이 끝날때까지 대기중인 상태
• 완료: 프로세스가 실행 종료된 상태

 

 

프로세스 상태 전이

 

 

프로세스 상태 전이	설명
디스패치 (dispatch)	준비 상태에 있는 여러 프로세스(Ready list) 중 실행될 프로세스를 선택하여 CPU를 할당(dispatching) -> 문맥 교환(Context Switching) 발생. 프로세스는 준비상태에서 실행상태로 전이.
할당시간 초과 (timeout)	CPU를 할당받은 프로세스는 지정된 시간이 지나면 스케줄러에 의해 PCB에 정보를 저장하고, CPU 반납 후 준비 상태로 전이 됨. 프로세스는 실행상태에서 준비상태로 전이. 타임 슬라이스(Time slice) 만료, 선점(Preemption) 시 타임아웃 발생.
입출력 발생 (Block)	실행 상태에 있는 프로세스가 지정된 할당 시간을 초과하기 전에 입출력이나 기타 사건이 발생(block)하면 CPU를 스스로 반납하고 입출력이 완료될 때까지 대기상태로 전이됨. 즉시 실행 불가능한 시스템 콜, I/O 작업 시작, 프로세스간 통신이 Block 발생.
깨움 (Wake-up)	어느 순간에 입출력이 종료되면 대기상태의 프로세스에게 입출력 종료 사실을 wait & signal 등에 의해 알려주고 준비상태로 전이됨.

 

비선점형 스케줄링과 선점형 스케줄링

비선점형 스케줄링 (Non Preemptive Scheduling)

한 프로세스가 CPU를 할당 받으면 작업 종료 후 CPU 반환 시까지 다른 프로세스는 CPU 점유가 불가능한 스케줄링 방식

 

비선점형 스케줄링

 

• 응답시간 예상이 용이하다.
• 모든 프로세스에 대한 요구를 공정하게 처리.
• 짧은 작업을 수행하는 프로세스가 긴 작업 종료 시까지 대기할 수 있음

비선점형 스케줄링 알고리즘에는 우선순위, 기한부, HRN(High Response Ratio Next), FCFS(FIFO), SJF(Shortest Job First) 등이 있다. 보통 처리시간 편차가 적은 특정 프로세스 환경에 사용된다.

 

 

알고리즘 유형	동작 방식	특징
우선 순위 (Priority)	각 프로세스 별로 우선순위가 주어지고, 우선 순위에 따라 CPU를 할당함. 동일 순위는 FCFS	주요/긴급 프로세스에 대한 우선처리. 설정, 자원 상황 등에 따른 우선순위 선정
기한부 (Deadline)	작업들이 명시된 시간이나 기한 내에 완료되도록 계획	요청에 명시된 시간내 처리를 보장
FCFS (First Come First Service)	프로세스가 대기큐에 도착한 순서에 따라 CPU를 할당함. FIFO 알고리즘이라고도 한다	도착한 순으로 처리
SJF (Shortest Job First)	프로세스가 도착하는 시점에 따라 그 당시 가장 작은 서비스 시간을 갖는 프로세스가 종료 시까지 자원 점유. 준비 큐 작업 중 가장 짧은 작업부터 수행. 평균 대기시간 최소. CPU 요구시간이 긴 작업과 짧은 작업 간의 불평등이 심하면 CPU 요구시간이 긴(작업 시간이 오래걸리는) 프로세스는 기아현상 발생	기아현상 발생 가능
HRN (Highest Response Ratio Next)	대기 중인 프로세스 중 대기시간이 긴 프로세스일 경우 우선순위가 높아지게 하여 우선순위를 결정하는 스케줄링 기법 서비스 시간과 대기 시간을 고려하여 가변적 우선순위 결정. HRN 우선 순위 계산식 = (대기시간 + 서비스시간) / 서비스 시간 즉, 대기시간이 길고 서비스 시간이 짧을 수록 우선순위는 올라간다. 우선 순위 계산식 수치가 가장 높은 것부터 낮은 순으로 우선 순위 부여. SJF의 단점인 기아현상을 보완함. 서비스 시간이 지나치게 긴 작업 과 짧은 작업간의 불평등을 해소	기아 현상 최소화 기법

*기아현상 : 시스템에 부하가 많아서 준비 큐에 있는 낮은 우선순위를 가진 프로세스가 무한정 기다리게되는 현상이다. 기아현상을 해결하기 위해 오래 기다린 프로세스에 우선순위를 높여줌으로써 처리하는 에이징 기법을 사용한다.

 

선점형 스케줄링 (Preemptive Scheduling)

하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식

 

선점형 스케줄링

 

• 비교적 빠른 응답
• 대화식 시분할 시스템에 적합
• 높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래

선점형 스케줄링 알고리즘에는 SRT(Shortest Remaining Time First), 다단계 큐(Multi-level Queue), 다단계 피드백 큐, 라운드 로빈(Round Robin, RR) 등이 있고, 주로 실시간 응답환경, Deadline 응답환경에 사용된다.

 

 

알고리즘 유형	동작 방식	특징
라운드 로빈 (Round Robin)	프로세스는 같은 크기의 CPU시간을 할당(시간 할당량, Time slice), 프로세스가 할당된 시간 내에 완료되지 않으면 준비 큐(원형 큐) 리스트의 가장 뒤로보내지고 CPU는 대기 중인 다음 프로세스로 넘어감	균등한 CPU 점유시간. 시분할 시스템을 사용. 시간 할당량이 너무 작으면 오버헤드 발생할 수 있음
SRT (Shortest Remaing Time First)	가장 짧은 시간이 소요되는 프로세스를 먼저 수행. 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨	짧은 수행시간 프로세스 우선 수행
다단계 큐 (Multi Level Queue)	작업들을 여러 종류 그룹으로 분할, 여러 개의 큐를 이용하여 상위 단계 작업에 의한 하위단계 작업이 선점 당함	독립된 스케줄링 큐
다단계 피드백 큐 (Multi Level Feedback Queue)	입출력 위주와 CPU 위주인 프로세스의 특성에 따라 큐마다 서로 다른 CPU 시간 할당량을 부여. FCFS와 라운드 로빈 스케줄링 기법을 혼합한 것으로, 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동하고 마지막 단계는 라운드 로빈 방식을 적용	큐마다 다른 시간 할당량 마지막 단계는 라운드 로빈 방식 처리

 

다음에는 각 프로세스 알고리즘의 동작에 대해 알아볼 것이다.

 

 

잘못된 내용이 있다면 지적 부탁드립니다.

 

참조

 

도서) 수제비 정보처리기사 필기.

 

https://coding-factory.tistory.com/309

[OS] 운영체제 스케줄링이란 무엇인가?

 

https://medium.com/@plantstoen/%EB%8F%84%EB%B9%84%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81%EA%B3%BC-fcfs-vs-rr%EB%B9%84%EA%B5%90-f20a1a46247f

도비로 알아보는 프로세스 스케줄링과 FCFS vs RR비교