[3장 프로세스 스케줄러]2.스케줄링 큐

Publish Date

프로세스 스케줄링 큐

프로세스 스케줄링 큐는 프로세스의 상태를 효율적으로 관리하고 시스템 자원을 최적으로 배분하기 위한 데이터 구조이다. 시간 순서대로 처리하는 FIFO(First-In-First-Out) 특성을 가진 큐(Queue)를 사용하여 프로세스의 상태 전환을 관리한다. 삽입과 삭제 시간 복잡도

O(1)

으로 빠르고 크기 조정이 용이하다. 큐는 프로세스의 생애 주기와 자원 요청/해제 과정을 반영한다.

프로세스 스케줄링 큐 종류

운영체제는 다양한 상태의 프로세스를 관리하기 위해 여러 유형의 큐를 사용한다. 주요 큐와 그 기능은 다음과 같다.

작업 큐 (Job Queue) ← cpu 스케줄링??

•

시스템에 생성된 모든 프로세스를 관리하는 큐

•

시스템에 생성된 모든 프로세스의 시작점 역할을 합니다.

•

작업 큐는 전체 프로세스 상태를 추적한다. 

•

시스템이 프로세스를 관리하는 초기 단계에서 사용된다. 
프로세스는 작업 큐에 배치된 후 준비(Ready) 큐 또는 대기(wait) 큐로 이동한다. 

준비 큐 (Ready Queue)

•

실행 준비 상태인 프로세스가 대기하는 큐

•

CPU 코어를 할당받기 전까지 대기한다. 

•

연결 리스트로 저장된다. 
준비 큐의 헤더는 리스트의 첫 번째 PCB를 가리키며, 각 PCB는 다음 PCB에 대한 포인터 필드를 가리킨다. 

•

CPU가 프로세스를 할당받기 위해 큐의 첫 번째 프로세스를 선택하는 디스패치(dispatch) 작업이 이뤄진다. 

대기 큐 (Wait Queue)

•

I/O 작업이나 특정 이벤트를 기다리는 대기 상태의 프로세스가 배치되는 큐

•

프로세스가 입출력 장치와 같은 느린 자원과 상호작용할 때, 해당 작업이 완료될 때까지 대기 상태로 유지한다. 

•

I/O 장치별로 별도의 대기 큐를 유지하며, 각 장치가 고유의 대기 큐를 관리한다. ex)프린트 큐

•

대기 중인 프로세스는 작업이 완료되면 준비 큐로 다시 이동한다. 

•

시스템 병목 현상 관리를 돕는 중요한 역할을 한다. 

우선순위 큐 (Priority Queue) ← cpu 스케줄링??

•

프로세스가 우선순위(priority)에 따라 배치되는 큐

•

우선순위가 높은 프로세스가 CPU를 먼저 할당받도록 관리한다.

•

우선순위에 따라 큐를 정렬하거나, 여러 우선순위 레벨에 따라 다중 큐를 유지한다. 

•

선점형 스케줄링에서는 높은 우선순위 프로세스가 현재 실행 중인 프로세스를 중단시키고 CPU를 할당받을 수 있다.

•

비선점형 스케줄링에서는 실행 중인 프로세스가 끝날 때까지 기다린다. 

종료 큐(Termination Queue) ←cpu 스케줄링??

•

실행이 완료된 종료 상태의 프로세스가 배치되는 큐

•

프로세스가 실행을 완료하면 종료 큐에 추가되어 운영체제가 자원을 회수/해제 및 실행 기록(회계 정보) 관리한다. 

•

회계 정보(accounting information)를 관리하며, 디버깅 정보를 유지하거나 후속 작업 기록을 보관한다. 

프로세스 상태 변화와 큐 관리

생성된 프로세스는 준비큐(Ready Queue)에 들어가며, CPU에 실행할 차례를 기다린다. 프로세스가 CPU할당을 받아 실행 중(running)일 때는 다음과 같은 이벤트에 따라 상태와 큐가 변경된다.

프로세스는 실행 중에 준비 큐(Ready Queue)와 다양한 대기 큐(Wait Queue)를 오가며 생애 주기를 이어갑니다. CPU 스케줄러의 역할은 준비 큐에 있는 프로세스 중 하나를 선택하여 CPU 코어를 할당하는 것입니다.

1) I/O 요청

•

프로세스가 I/O 작업(예: 파일 읽기/쓰기)을 요청한다. 

상황	상태변화	큐 이동
I/O 작업 요청 후 요청에 대한 응답을 기다린다.	running → waiting	Ready Queue → I/O Wait Queue
I/O 작업 완료 후 cpu 할당을 준비한다.	Waiting → Ready	I/O Wait Queue → Ready Queue

2)자식 프로세스 생성

•

프로세스가 새로운 자식 프로세스를 생성한다. 

상황	상태 변화	큐 이동
자식 프로세스 종료 기다린다.	Running → Waiting	Ready Queue → Wait Queue
자식 프로세스 종료 exit() 후 CPU 재활성화	Waiting → Ready	Wait Queue → Ready Queue

3)타임 슬라이스 또는 인터럽트 발생

•

프로세스가 주어진 CPU 실행 시간을 모두 사용하거나, 인터럽트가 발생한다. 

상황	상태 변화	큐 이동
타임 슬라이스 만료 또는 인터럽트 발생	Running → Ready	Running → Ready Queue

4)종료(Termination)

•

프로세스가 자신의 작업을 완료하거나 종료 명령(exit)를 실행한다.

상황	상태 변화	큐 이동
작업 완료	Running → Terminated	종료 큐(Termination Queue)로 이동 → 모든 큐에서 제거된다. → 운영체제는 관련 자원을 해제한다.

프로세스는 준비(ready), 실행(running), 대기(waiting) 상태를 반복하며 그에 따라 작업을 수행한다.

작업이 끝나면 모든 큐에서 제거되고, 운영체제는 관련 자원(PCB, 메모리 등)을 해제한다.

이런 상태 전환은 스케줄링과 디스패처(dispatcher)에 의해 관리된다.

마무리

Q&A