17_CPU 스케줄링 기본 개념

17_CPU 스케줄링 기본 개념

 

CPU 스케줄링(scheduling)은 다중 프로그램 운영체제의 기본 이다. 운영체제는 CPU를 프로세스들 간에 교환 함으로써 컴퓨터를 보다 생산적으로 만든다.

 

스레드를 지원하는 운영체제에서는 프로세스가 아니라 커널 수준의 스레드를 스케줄링 한다. 그러나 프로세스 스케줄링과 스레드 스케줄링 용어는 상호 교환적으로 사용 되며 일반적인 스케줄링을 논의하는 경우에는 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우에 스레드 스케줄링이라는 용어를 사용한다.

 

단일 처리기 시스템에서는 한 순간에 오직 하나의 프로세스만이 실행 될 수 있다. 다중 프로그래밍의 목적은 CPU 이용률을 최대화 하기 위해 항상 실행중인 프로세스를 가지게 하는데 있다.

 

스케줄링은 운영체제의 기본 기능으로 다중 프로그래밍에서는 CPU의 대기 시간을 활용하기 위해 어느 한 순간에 다수의 프로세스들을 메모리 내에 유지한다. 어떤 프로세스가 대기해야 할 경우 운영체제는 CPU를 그 프로세스로부터 회수하여 다른 프로세스에 할당 한다. 이러한 패턴은 반복되며 하나의 프로세스가 대기해야 할 때마다 다른 프로세스가 CPU 사용을 양도 받을 수 있다.

 

따라서 거의 모든 컴퓨터 자원들은 사용되기 전에 스케줄링 되며 CPU의 스케줄링은 운영체제의 핵심이 된다.

 

[CPU 입/출력 버스트 사이클(CPU I/O Burst Cycle)]

프로세스 실행은 CPU 실행과 입/출력 대기의 사이클로 구성된다. 프로세스들은 이들 두 상태 사이를 교대로 이동 한다. 프로세스 실행은 CPU 버스트(Burst)로 시작된다. 뒤이어 입/출력 버스트가 발생하고 그 뒤를 이어 또 다른 CPU 버스트가 발생하며 이어 또 다른 입/출력 버스트 등으로 진행 된다. 결국 마지막 CPU 버스트가 또 다른 입/출력 버스트가 뒤따르는 대신 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

 

입출력 중심의 프로그램은 전형적으로 짧은 CPU 버스트를 많이 가지며 CPU 지향 프로그램은 다수의 긴 CPU 버스트를 가진다. 이러한 분포는 CPU 스케줄링 알고리즘을 선택하는데 매우 중요 하다.

 

 

[CPU 스케줄러(CPU Scheduler)]

CPU가 유휴 상태가 될 때 마다 운영체제는 준비 완료 큐에 있는 프로세스들 중에서 하나를 선택해 실행 해야 한다. 선택 절차는 단기(short term) 스케줄러(CPU 스케줄러)에 의해 수행 된다.

 

 

스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스들 중에서 선택하여 CPU에 할당 한다.

 

 

준비 완료 큐는 반드시 선입선출(FIIO)방식의 큐가 아니라는 것에 유의하며 순서 없는 연결 리스트로 구현 할 수 있다. 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB)이다.

 

• 프로세스 개념 : http://sqlmvp.kr/140189245176

 

 

[선점 스케줄링(Preemtive Scheduling)]

CPU 스케줄링은 다음 네 가지 상황에서 발생 할 수 있다.

• 한 프로세스가 실행 상태에서 대기 상태로 전환 될 때.(종료되기를 기다리기 위해 wait를 호출 할 때)
• 프로세스가 실행 상태에서 준비 완료 상태로 전환 될 때
• 프로세스가 대기 상태에서 준비 완료 상태로 전환 될 때
• 프로세스가 종료 할 때

 

1,4의 스케줄링 방법을 비선점(Non-preemptive)또는 협조적(coorperative)이라고 하며 2.3번의 스케줄링을 선점(Preemptive)이라고 한다.

 

선점 스케줄링은 공유 자료에 대한 접근을 조정하는 데 필요한 비용을 유발하며 커널 설계에 영향을 준다. 시스템 호출을 처리할 동안 커널은 한 프로세스를 위한 활동으로 바쁠 수 있다. 그러한 활동은 (입/출력 큐와 같은)중요한 커널 자료 변경을 포함 할 수 있다. 만약 이러한 변경 도중에 해당 프로세스가 선점되어 동일한 구조를 읽거나 변경할 경우 혼란이 발생한다.

 

인터럽트는 어느 시점에서든 일어 날 수 있으며 커널에 의해서 항상 무시 될 수는 없기 때문에 인터럽트에 의해서 영향을 받는 코드 부분은 반드시 동시 사용으로부터 보호되어야 한다.

 

운영체제는 항상 인터럽트를 받아들일 필요가 있는데 그렇지 않으면 입력을 잃어버리거나 출력이 겹쳐서 쓰여질 수 있다. 이러한 코드 부분은 다수 프로세스가 병행으로 접근할 수 없도록 그 진입점에서 인터럽트를 불능화 하고 출구에서 인터럽트를 다시 가능화 한다.

 

인터럽트의 불능화 코드는 자주 발생해서는 안되며 아주 적은 수의 명령어들만 포함하여야 한다는 것을 주의하자.

 

[디스패처(Dispatcher)]

디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이며 다음의 작업을 포함한다.

• 문맥을 교환 하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동(jump)하는 일

 

디스패처는 모든 프로세스의 문맥 교환 시 호출 되므로 가능한 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데 소요되는 시간을 디스패치 지연(Dispatch latency)라고 한다.

 

 

[참고자료]

Operating System Concept / 홍릉과학출판사