[혼자 공부하는 컴퓨터구조+운영체제] "chapter11. CPU 스케줄링"

11-1 CPU 스케줄링 개요

CPU 스케줄링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것.

프로세스 우선순위

프로세스마다 우선순위 다름. 우선순위 높은 프로세스는 빨리 처리해야하는 프로세스. (대표적으로 입출력작업)

프로세스들은 CPU와 입출력장치를 모두 사용하며 실행. 실행상태와 대기 상태 반복하며 실행.

 

프로세스 종류마다 입출력 장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이 존재.

입출력 집중 프로세스: 비디오 재생, 디스크 백업 작업 담당 등. 실행상태보다 입출력을 위한 대기 상태에 더 많이 머무름. CPU 많이 사용하지 않는 프로세스. 입출력 버스트가 많은 프로세스.

CPU 집중프로세스: 수학연산, 컴파일, 그래픽 처리 담당 등. 대기 상태보다 실행 상태에 더 많이 머무름. CPU 많이 사용하는 프로세스. CPU 버스트가 많은 프로세스.

 

CPU 버스트: CPU 이용하는 작업.

입출력 버스트: 입출력 장치를 기다리는 작업.

프로세스는 이 둘을 반복하며 실행.

 

모두가 동일한 빈도로 CPU를 사용하는 것은 비합리적.

 

입출력장치가 입출력 작업을 완료하기 전까지 입출력 집중 프로세스는 대기상태. 입출력 집중 프로세스를 먼저 처리하면 다른 프로세스가 CPU 사용 가능.

운영체제는 프로세스마다 우선순위 부여.

각 프로세스의 PCB에 우선순위를 명시, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스 결정.

우선순위 높은 프로세스 더 빨리, 자주 실행.

 

스케줄링 큐

모든 프로세스의 PCB를 뒤적거리는 것 비효율적.

운영체제가 매번 모든 PCB 검사해 먼저 자원을 이용할 프로세스 결정하는 일 번거롭고 오래걸림.

 

스케줄링 큐: CPU 사용하고 싶은 프로세스들을 줄 세우는 것. 이 줄을 통해 구현하고 관리.

큐에는 다양한 종류.

준비 큐: CPU 이용하고 싶은 프로세스들이 서는 줄.

대기 큐: 입출력 장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄.

준비상태에 있는 프로세스들의 PCB는 준비큐의 마지막에 삽입돼 CPU를 사용할 차례 기다림.

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그 중 우선순위 높은 프로세스 먼저 실행.

 

대기 상태에 있는 프로세스도 같음.

같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다림.

입출력이 완료돼 완료 인터럽트 발생시 운영체제는 대기 큐에서 작업이 완료된 PCB 찾고, 준비상태로 변경한 뒤 대기큐에서 제거. 준비큐로 이동.

 

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

CPU를 잘 사용하고 있던 프로세스가 다른 급한 프로세스가 CPU를 당장 사용하길 요청했을 때.

 

선점형 스케줄링: 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식. 자원사용을 독점할 수 없는 스케줄링. 정해진 시간만큼 CPU 사용.

비선점형 스케줄링: 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링. 자원 사용을 독점할 수 있는 스케줄링. 다른 프로세스들은 사용이 모두 끝날때 까지 기다려야 함.

 

장단점

	장점	단점
선점형 스케줄링	한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원 배분	문맥 교환 과정에서 오버헤드 발생
비선점형 스케줄링	문백교환에서 발생하는 오버헤드 적음.	하나의 프로세스가 자원 사용중이면 당장 자원을 사용해야 하는 상황에도 무작정 기다려야 함. 모든 프로세스 골고루 자원 사용 불가능.

 

 

---

 

11-2 CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘의 종류는 매우 다양

 

스케줄링 알고리즘 종류

 

선입선처리 스케줄링(= FCFS 스케줄링)

 

준비 큐에 삽입된 순서대로 프로세스 처리하는 비선점형 스케줄링.

CPU 먼저 요청한 프로세스부터 CPU 할당.

가장 공정해보이지만, 기다리는 시간 매우 길어질 수 있음.

호위효과: 순서대로 진행하기 때문에 짧은 시간을 이용하는 뒷순서 애는 긴시간을 기다리는 현상.

 

최단 작업 우선 스케줄링(= SJF스케줄링)

준비 큐에 삽입된 프로세스 들 중 CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링.

비선점 스케줄링 알고리즘 분류 되지만, 선점형도 가능.

 

라운드 로빈 스케줄링

선입 선처리 스케줄링에 타임 슬라이스 개념 더해진 스케줄링.

타임슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간.

큐에 삽입된 프로세스들 순서대로 정해진 시간만큼 이용, 정해진 시간 모두 사용했음에도 완료되지 않았으면 다시 큐의 맨뒤 삽입.

타임 슬라이스 크기 매우 중요.

 

최소 잔여 시간 우선 스케줄링(= SRT 스케줄링)

최단 작업 우선 스케줄링 알고리즘 + 라운드 로빈 알고리즘 

정해진 타임 슬라이스 만큼 CPU를 사용하되, CPU를 사용할 다음 프로세스로는 남아있는 작업시간 가장 적은 프로세스 선택.

 

우선순위 스케줄링

프로세스들에 우선순위 부여하고, 가장 높은 우선순위 가진 프로세스부터 실행하는 스케줄링 알고리즘.

근본적인 문제 내포.

기아 현상: 우선순위가 낮은 프로세스는 우선순위 높은 프로세스들에 의해 실행이 계속해서 연기.

에이징: 기아현상 방지하기 위한 기법. 오랫동안 대기한 프로세스 우선순위 높이는 방식.

 

다단계 큐 스케줄링

우선순위별로 준비큐를 여러개 사용하는 스케줄링.

우선순위 가장 높은 큐에 있는 프로세스들 먼저 처리, 우선순위 가장 높은 큐가 비어있으면 그다음 우선순위 큐에 있는 프로세스들 처리.

큐를 여러개 두면 프로세스 유형별로 우선순위 구분하여 실행하는 것 편리.

 

다단계 피드백 큐 스케줄링

기아현상 발생 방지.

다단계 큐 스케줄링과 비슷하게 작동, 프로세스 들이 큐 사이를 이동할 수 잇음.

CPU 오래 사용하는 프로세스 우선순위 낮아지고, 적게 사용하는 프로세스들은 우선순위 높은 큐에서 실행.

낮은 우선순위 큐에서 오래 기다리고 있는 프로세스에게 우선순위 높은 큐로 이동시키는 에이징 기법 사용.

CPU 이용 시간 길면 -> 낮은 우선순위 큐로 이동

낮은 우선순위 큐에서 오래 기다리면 -> 높은 우선순위 큐로 이동

 

 

 

---

출처

https://hongong.hanbit.co.kr/%ec%bb%b4%ed%93%a8%ed%84%b0-%ea%b5%ac%ec%a1%b0-%ec%9a%b4%ec%98%81%ec%b2%b4%ec%a0%9c/

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제