CPU 스케줄링

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

CPU 스케줄링(CPU scheduling)이라고 합니다.

 

프로세스 우선순위

프로세스는 우선순위를 가지고 있는데 우선순위가 높은 프로세스란 빨리 처리해야 하는 프로세스를 의미합니다.

대표적으로 입출력 작업이 많은 프로세스가 우선순위가 높습니다. 그 이유는 CPU 집중 프로세스가 입출력 집중 프로세스 보다 CPU를 많이 사용해야 하는 프로세스인데 이 둘이 동일한 빈도로 CPU를 사용하는 것은 비합리적입니다. 따라서 이 둘이 동시에 CPU 자원을 요구했다고 가정하면 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력 작업을 끝낸 뒤, 그다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적입니다. 프로세스 우선순위는 PCB에 명시되어 있습니다.

 

입출력 집중 프로세스(I/O bound process) : 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스  

CPU 집중 프로세스(CPU bound process) : 복잡한 수학 연산, 컴파일, 그래픽 처리작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스  

 

스케줄링 큐

스케줄링 큐란, 운영체제가 프로세스들을 관리하는 또 다른 방식 중 하나입니다.

운영체제가 매번 모든 PCB를 검사하여 먼저 자원을 이용할 프로세스를 결정하는 일은 비효율적입니다.

따라서, 운영체제는 프로세스들을 각각이 요구하는 자원에 따라 큐에 삽입하여 줄을 세우고 관리합니다.

 

* 자료 구조 관점의 큐와 다르게 선입선출 방식일 필요는 없습니다.

 

대표적으로 준비 큐와 대기 큐가 존재합니다.

 

준비 큐( ready queue) : CPU를 이용하고 싶을 프로세스들이 대기하는 줄

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

동작 흐름

 

준비 상태 프로세스

 

1. 준비 상태 프로세스들의 PCB를 준비 큐의 마지막에 삽입

 

2. 운영체제는 PCB가 큐에 삽입된 순서대로 프로세스 꺼내어 실행

    그중 우선순위가높은 프로세스를 먼저 실행

 

대기 상태 프로세스

 

1. 같은 자원을 요구 한 프로세스들끼리  대기 큐에서 차례 대기

 

2. 입출력 작업이 완료(인터럽트 발생) : 대기 큐에서 작업이 완료된 PCB 찾기

 

3. 해당 PCB를 준비 상태로 변경

 

4. 대기 큐에서 제거

 

5. 준비 큐로 이동 

 

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

선점형 스케줄링(preemptive scheduling)

프로세스가 특정 자원을 사용하고 있더라도 운영체제가 해당 자원을 강제로 빼앗아 다른 프로세스에게 할당할 수 있는 스케줄링 방식입니다. 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식이지요.

 

장점 : 어느 한 프로세스의 자원 독점을 막고 프로세스들에 골고루 자원을 배분 가능

 

단점 : 문맥 교환 과정에서 오버헤드가 발생할 수 있음 

 

비선점형 스케줄링(non-preemptive scheduling)

특정 자원을 사용중인 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식입니다. 다시 말해 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식이라고 할 수 있습니다.

 

장점 : 문맥 교환 과정에서오버헤드가 선점형보다 적음

단점: 모든 프로세스가 골고루 자원을 사용할 수 없음

 

---

스케줄링 알고리즘의 종류

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

• 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 방식
• 비선점형

단점

• 프로세스들의 대기 시간이 길어질 수 있음
• 호위 효과(convoy effect)

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

• 준비 큐에 삽입된 프로세스들 중  CPU 이용 시간의 길이가 가장 짧은 프로세스부터 실행하는 방식
• 비선점형 스케줄링 알고리즘 ( * 선점형으로 구현 가능,SRT )

라운드 로빈 스케줄링

• 선입 선처리 스케줄링 + 타임 슬라이스 개념
  • 타임 슬라이스 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미    
• 자원의 사용이 끝나지 않은 프로세스더라도 타임 슬라이스를 모두 사용 시 다시 큐의 맨 뒤에 삽입 (문맥 교환 발생) 

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

• 최단 작업 우선 스케줄링 + 라운드 로빈
• 최단 작업 우선 스케줄링 하에서 정해진 타임 슬라이스 만큼 CPU를 사용, CPU를 사용할 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선

 

우선순위 스케줄링

• 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘
• 우선 순위가 같으면 선입 선처리

단점 

• 기아 현상 : 우선순위가 높은 프로세스들에 의해 실행이 계속 연기되는 현상, 에이징 기법을 통해 방지

에이징( aging) : 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식 

다단계 큐 스케줄링(multilevel queue scheduling)

• 우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
• 큐별로 타임 슬라이스 여러 개 지정 가능
• 큐마다 다른 스케줄링 알고리즘 사용 가능

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

• 다단계 큐 스케줄링과 다르게 프로세스들이 큐 사이를 이동 가능
• 타임 슬라이스 안에 실행이 끝나지 않으면 다음 우선순위 큐로 삽입
• CPU를 오래 사용해야 할수록  점차 우선순위 감소 
• 에이징 기법을 통해 높은 우선순위 큐로 이동 가능 

 

[참조] : https://hyuntaekhong.github.io/blog/OperatingSystem03/