07. CPU 스케줄링 개요

CPU 스케줄링 개요

모든 프로세스들은 실행을 시작하면서부터 자신이 필요로 하는 자원을 경쟁적으로 운영체제에 요구하게 된다. 운영체제는 이들이 요청한 자원을 할당해주어야만 할 것이다.

CPU 입장에서의 자원은 실행시간을 의미하며, 운영체제는 스케줄링이라는 수단을 통해 각 프로세스에 실행시간을 할당한다.

1. CPU 스케줄링

• CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며 CPU 스케줄링은 CPU 스케줄러가 하는 모든 작업을 가리킨다.
• 컴퓨터 시스템의 효율성은 어떤 프로세스에 CPU를 먼저 배정하느냐에 따라 달라지므로 CPU 스케줄링 작업의 형평성과 효율성을 결정하는 중요한 일이다.

2. 스케줄링의 단계

1) 작업 스케줄링(작업 선택) - 승인 스케줄링

• 고수준 스케줄링(장기 스케줄링)이라 부름
• 전체 시스템의 부하를 고려하여 작업을 시작할지 말지를 결정하여 시스템 내의 전체 프로세스 수를 조절하는 것
  • 다중 프로그래밍의 정도를 결정함.

2) 작업 승인과 프로세서 결정 스케줄링(사용권한)

• 중간수준 스케줄링(중기 스케줄링)이라 부름
• 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는 것
  • 전체 프로세스 수를 조절해야 한다면 이미 활성화된 프로세스 중 일부를 보류 상태로 보내고 보류된 프로세스는 처리 능력에 여유가 생기면 다시 활성화 된다.

3) 프로세서 할당 스케줄링(디스패칭)

• 저수준 스케줄링(단기 스케줄링)이라 부름

  • 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 것

3. CPU 스케줄링의 목적

CPU의 스케줄링의 목적은 응답시간이나 처리량, 효율성을 증대시키기 위해 CPU가 다음에 실행할 프로세스를 선택하는 것이라 할 수 있다.

1) 공평성

• 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.

2) 효율성

• 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.

3) 안정성

• 우선순의를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.

4) 확장성

• 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다
• 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야한다.

5) 반응 시간 보장

• 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

6. 무한 연기 방지

• 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

4. 스케줄링 시 고려 사항

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

구분	선점형	비선점형
작업 방식	실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있다	실행 상태에 있는 작업이 완료될 때 까지 다른 작업이 불가능 하다.
장점	프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합하다	CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다
단점	문맥 교환의 오버헤드가 많다	기다리는 프로세스가 많아 처리율이 떨어진다.
사용	시분할 방식 스케줄러에 사용된다	일괄 작업 방식 스케줄러에 사용된다.
중요도	높다	낮다

 

중요도

• 비선점형과 선점형 프로세스가 혼재하는 경우에는 비선점형 프로세스의 중요도를 매우 낮게 설정하여 선점형 프로세스에 영향을 덜 미치도록 한다.

프로세스 우선순위

대부분의 CPU 스케줄러는 우선순위를 사용한다. 우선순위가 있다는 것은 프로세스의 중요도가 다르다는 의미이다.

• 프로세스는 크게 커널프로세스와 일반 프로세스로 나뉜다.

• 커널 프로세스의 우선순위가 일반 프로세스보다 높다

• 시스템에는 다양한 우선순위 프로세스가 공존하며 우선순위가 높은 프로세스가 CPU를 먼저, 더 오래 차지한다.

• 일반 프로세스의 우선순위는 사용자가 조절할 수 있으며 시스템에 따라 높은 숫자가 높은 우선순위를 나타내기도 하고 낮은 숫자가 높은 우선순위를 나타내기도 한다.

CPU 집중 프로세스와 입출력 집중 프로세스

프로세스의 특징

프로세스는 생성된 후 준비, 실행, 대기 상태를 거쳐 완료된다. 준비 상태는 CPU를 할당받기 위해 기다리는 상태이므로 실제 작업이 일어나는 것은 실행 상태와 대기 상태이다. 프로세스는 CPU를 사용하여 작업을 하는 실행 상태또는 입출력을 요청하여 완료되기까지 기다리는 대기 상태가 있다.

---

프로세스의 실행은 CPU의 실행과 I/O 대기 사이클로 반복된다

이때 CPU를 할당 받아 실행하는 작업을 CPU burst, 입출력 작업을 I/O burst라 부른다.

CPU Burst

• 프로그램의 수행중에 연속적으로 CPU를 사용하는 단절된 구간
• 스케쥴링의 단위가 된다.

I/O Burst

• 프로그램의 수행중에 I/O작업이 끝날때까지 block되는 구간

---

프로세스 버스트 지속시간 빈도 그래프

• 이러한 분포는 적절한 프로세서 스케줄링 알고리즘을 선택하는 데 매우 중요한 기준이 됨.

---

CPU-bound process(CPU 집중 프로세스)

실행하는 동안 입출력은 자주 수행하지 않으면서 대부분의 시간을 어떤 계산을 하기 위해 CPU를 사용하는 프로세스를 의미한다

• CPU 버스트가 큰 프로세스
• 계산 위주의 작업 수행(CPU 중심 작업)
• 긴 CPU 버스트를 가진다.

I/O-bound process(입출력 집중 프로세스)

실생시간의 대부분을 CPU보다는 입출력을 위한 시간으로 사용하는 프로세스를 일컽는다.

• CPU를 사용하여 계산하는 시간보다 I/O에 많은 시간이 필요함
• 대부분의 대화형 프로세스(입출력 중심 작업)
• 짧은 CPU 버스트를 가진다.

전면 프로세스와 후면 프로세스

전면 프로세스

• GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스

• 현재 입력과 출력을 사용하는 프로세스

• 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 함

후면 프로세스

• 사용자와 상호작용이 없는 프로세스

• 사용자의 입력 없이 작동하기 때문에 일괄 작업 프로세스라고도 함

• 전면 프로세스의 우선순위가 후면 프로세스보다 높음

5. 다중 큐

프로세스는 저마다 중요도가 다르며 프로세스의 중요도는 프로세스 제어블록에 표시된다. CPU 스케줄러는 모든 프로세스 제어 블록을 뒤저셔 가장 높은 우선순위의 프로세스에 CPU를 할당한다. 그러나 매번 모든 프로세스 제어블록을 검색하는 것은 번거로운 일이다.

준비 상태의 다중 큐

• 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입
• CPU 스케줄러는 우선순위가 가장높은 큐의 맨 앞에 있는 프로세스에 CPU 할당

프로세스의 우선순위를 배정하는 방식

1) 고정 우선순위 방식(static priority)

• 운영체제가 프로세스에 우선순위를 부여하면 프로세스는 끝날 때까지 바뀌지 않는 방식
• 프로세스가 작업하는 동안 우선순위가 변하지 않기 때문에 구현이 쉽다
• 시스템의 상황이 시시각각 변하는데 우선순위를 고정하면 시스템의 변화에 대응하기 어려워 작업의 효율이 떨어진다.

2) 변동 우선순위 방식(dunamic priority)

• 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식
• 구현하기 어렵지만 시스템의 효율성을 높일 수 있다.

대기 상태의 다중 큐

• 시스템의 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아 놓음.
  • 시스템 내에는 다양한 종류의 입출력장치가 있기 때문에 한곳에 모아두는 것이 관리하기 더 불편함.

다중 큐 비교

준비 큐

• 한 번에 하나의 프로세스를 꺼내어 CPU를 할당(디스패치)

대기 큐

• 여러 개의 프로세스 제어블록을 동시에 꺼내어 준비 상태로 옮김
• 대기 큐에서 동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료 구조를 사용함

•  

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL