운영체제 레포트 - 운영체제의 작업 스케줄링에 사용되는 자료구조로 큐가 가장 적합한 이유에 대해 설명하시오.

I. 서론

컴퓨터에서 음악을 틀어 놓고 문서를 저장하는 동안 브라우저 탭을 새로 열어도 사용자는 여러 일이 동시에 움직인다고 느낀다. 실제 프로세서는 아주 짧은 시간 간격으로 실행 대상을 바꾸거나 여러 코어에 일을 나눈다. 여기서 운영체제는 "지금 누구를 실행할 것인가"를 계속 골라야 한다. 실행 기회를 기다리는 프로세스가 많아질수록 대상을 보관하는 방식이 중요해진다. 작업 스케줄링에 큐가 잘 맞는 까닭은 줄을 세우기 편해서만이 아니다. 프로세스의 상태 변화와 스케줄링 정책을 자연스럽게 연결하고, 삽입과 제거를 빠르게 처리하며, 여러 종류의 대기 상태를 분리하기 좋기 때문이다.

II. 본론

1) 실행을 기다리는 작업이 줄을 만드는 이유

운영체제에서 프로세스는 계속 CPU를 쓰는 상태로 머물지 않는다. 실행 준비가 되었지만 CPU를 기다릴 때가 있고, 디스크 입출력이나 키보드 입력처럼 어떤 사건이 끝나길 기다릴 때도 있다. 기다리던 사건이 끝나면 다시 실행 후보가 된다. 프로세스의 생애는 실행, 준비, 대기 같은 상태 사이를 오가는 흐름으로 이해할 수 있다. 이때 준비 상태의 프로세스를 모아 두는 준비 큐와 특정 사건을 기다리는 프로세스를 모아 두는 대기 큐가 필요해진다. Silberschatz, Galvin, Gagne의 운영체제 교재도 준비 큐와 대기 큐를 프로세스 스케줄링의 기본 구조로 설명한다.

큐의 핵심 연산은 뒤에 항목을 넣고 앞에서 항목을 꺼내는 것이다. 전형적인 선입선출 큐라면 먼저 들어온 항목이 먼저 나간다. 이 성질은 작업이 도착하고 서비스되는 상황을 표현하기 쉽다. 새로운 프로세스가 실행 준비를 마치면 큐에 들어가고, 스케줄러가 실행할 대상을 정하면 큐에서 하나를 꺼낸다. 실행 중인 프로세스가 입출력을 요청하면 준비 큐에서 벗어나 해당 대기 큐로 이동하고, 입출력이 끝나면 다시 준비 큐에 들어간다. 자료구조의 연산이 운영체제의 상태 전환과 거의 같은 방향으로 움직인다.

배열 하나에 모든 프로세스를 넣어 두고 매번 전체를 훑는 방식도 만들 수는 있다. 문제는 실행할 후보를 찾을 때 불필요한 탐색이 많아진다는 점이다. 연결 구조로 만든 큐는 맨 앞과 맨 뒤 위치를 기억하면 삽입과 제거를 일정한 시간에 처리할 수 있다. 원형 배열 큐도 인덱스만 움직여 비슷한 장점을 얻는다. 스케줄링은 시스템이 켜진 동안 매우 자주 일어나므로 작은 자료구조 연산의 비용도 누적된다. 후보를 넣고 빼는 일이 빠르고 예측 가능하다는 점은 큐의 중요한 장점이다.

큐는 프로세스 제어 블록과도 잘 결합된다. 운영체제는 각 프로세스의 식별 정보, 레지스터 상태, 스케줄링 관련 정보 등을 관리한다. 큐 자체에 프로세스의 모든 내용을 복사해 둘 필요는 없다. 준비 큐에는 프로세스 제어 블록을 가리키는 포인터나 연결 정보만 두고, 실제 상태 정보는 기존 구조에 남겨 둘 수 있다. 프로세스가 큐 사이를 이동할 때 큰 데이터를 반복 복사하지 않아도 된다. 연결 리스트 기반 구현이 운영체제 설명에서 자주 등장하는 이유도 여기에 있다.