본 포스팅에서는 큐(Queue)가 여러 개인 경우와 다중 프로세서(CPU)･스레드(Thread) 스케줄링, 실시간(Real-time) 스케줄링에 대한 내용을 다룬다. 멀티레벨 큐(Multilevel Queue) CPU를 기다리는 레디 큐(Ready Queue)가 한 줄이 아닌 여러 줄인 경우 각 큐에는 우선 순위가 존재한다. 아래 이미지는 멀티레벨 큐의 한 예시이다. (단일 CPU인 경우) CPU를 쓸 수 있는 프로세스는 어느 한 줄에서 나온 Job뿐이므로 우선 순위가 낮은 Queue에서는 Starvation 현상이 발생할 수 있다. 각 큐는 독립적인 스케줄링 알고리즘을 갖는다. 따라서 Starvation을 최소화하기 위하여 각 프로세스를 어떤 큐에 넣을 것인지와 개별 큐에 어떤 알고리즘을 선택할 것인지 결정해야 한다. ...
일반적인 CPU 스케줄링 알고리즘에 대한 포스팅이다. 여기서 일반적이라함은 단일 프로세서(CPU)･스레드(Thread), 비실시간(Unreal-time)을 의미한다. FCFS (First-Come First-Served) 가장 쉽게 떠올릴 수 있는 솔루션으로 큐(Queue)에 도착한 순서대로 처리하는 스케줄링이다. 마치 인간 세계에서 은행에 먼저 도착한 사람의 볼 일이 끝날 때 까지 뒤에 있는 사람이 기다려야 하는 것과 같은 방식이다. 순전히 선착순으로 먼저 도착한 프로세스는 볼 일이 끝날 때까지 CPU를 보장받는다. 즉, 비선점형(Non-Preemptive)이다. 문제점 (Problem) 꽤 공정하지만 앞에 어떤 프로그램이 있느냐에 따라 기다리는 시간에 대한 영향이 크기 때문에 그다지 효율적이지 않다. 같은 프로그램들이 실행되어도 도착 순서에 따라서 평균 대기 시간(Averaging waiting time)이 크게 차이 나기 때문이다. ...
프로그램이 실행된다는 것은 CPU 버스트(Burst)1와 I/O 버스트(Burst)가 번갈아 반복되며 실행된다는 것이다. 프로그램이 실행될 때는 이와 같이 여러 종류의 Job(=프로세스)이 섞이기 때문에 CPU 스케줄링이 필요하다. 프로그램 실행 시 CPU 버스트와 I/O 버스트가 반복되며 실행된다. CPU 스케줄링이란(CPU Scheduling) OS는 여러 종류의 Job이 혼재된 상황에서 시스템 자원(Resource)을 골고루 효율적으로 활용하고 유휴 대기 시간을 최소화할 수 있도록 관리하는데 이것을 스케줄링(Scheduling)이라고 한다. 즉, 레디 큐(Ready queue)에 있는 프로세스 중에 어떤 프로세스에게 CPU를 줄 것인지 결정하는 것이다. ...