[ 살펴보기 ] Operation System - 스케줄링과 동기화

프로세스가 특정 작업을 처리하기 위해선 CPU자원을 필요로 한다. 하지만 모든 프로세스가 동시에 CPU 자원을 점유할 수 없기에 CPU는 어떻게 프로세스에게 자원을 배분할 것인지 스케줄링하여 자원을 배분한다.

그리고 이러한 스케줄링은 크게 선점형 ( Preemptive ) 스케줄링과 비선정형 ( Non-Preemptive )스케줄링으로 나뉜다. 선점형 스케줄링은 현재 프로세스의 처리가 완료되지 않았더라도 특정 조건에 따라 CPU 자원을 다른 프로세스에 할당할 수 있는 스케줄링을 말하며 비선점 스케줄링은 CPU 자원을 사용하고 있는 프로세스의 작업이 완료되거나 대기 상태로 변할 때 까지 해당 프로세스가 CPU 자원을 계속해서 사용하는 방식이다

스케줄링 큐

운영체제는 다양한 스케줄링 큐를 통해 여러 프로세스를 관리하는데 대표적인 스케줄링 큐는 다음과 같다.

Job Queue : 모든 프로세스를 포함하는 Queue,
Ready Queue : CPU 자원을 기다리며 실행준비 중인 프로세스를 포함하고 있는 Queue
Devide Queue : 특정 I/O 작업의 종료를 기다리고 있는 프로세스를 포함하고 있는 Queue.

운영체제의 Scheduler는 이러한 queue를 통해 각 프로세스에 효율적으로 CPU 자원을 할당한다. 각각의 Queue에 적용할 수 있는 스케줄링 방식은 다양하며 대표적인 방식은 다음과 같다

스케줄링 알고리즘

First Come First Served : 비선점형 스케줄링으로서 준비 큐에 먼저 삽입된 순서대로 프로세스를 처리한다. 먼저 들어온 프로세스를 처리하는 시간이 길어지면 다음 프로세스는 먼저 들어온 프로세스가 완료될 때 까지 기다려야한다
Round Robin : First Come First Served 방식에 시간제한 개념을 더한 방식이다. 각 프로세스가 CPU를 사용할 수 있는 시간을 제한하고 그 시간만큼 CPU 자원을 사용하되 시간 내에 완료되지 않으면 준비 큐의 맨 뒤로 밀려난다. 여기서 제한된 시간을 타임 슬라이스라고 한다
Shorted Job First : 준비 큐에 삽입된 프로세스 중 CPU 사용시간이 가장 짧은 프로세스를 먼저 처리하는 방식이다
Shortest Remaining Time First : Shorted Job First에 Round Robin처럼 타임 슬라이스를 적용한 방식이다. CPU 사용 시간이 가장 짧은 프로세스를 먼저 처리하되 타임 슬라이스도 적용한다
Priority Scheduling : 프로세스에 부여되는 우선순위를 기준으로 가장 높은 우선순위 프로세스부터 처리되는 방식이다
Multilevel Queue Scheduling : 여러 개의 queue를 통해 프로세스 스케줄링을 처리한다. 각 queue에도 우선순위가 있어 우선순위가 높은 queue에 있는 프로세스가 먼저 처리된다. 각 queue마다 다른 타임 슬라이스, 스케줄링 방식을 적용할 수 있다
Multilevel Feedback Queue Scheduling : Multilevel Queue Schduling에서 만약 우선순위가 낮은 프로세스가 처리되기 전에 계속해서 우선순위가 높은 프로세스가 생성된다면 우선순위가 낮은 프로세스의 처리는 계속해서 뒤로 밀려날 수 있다. 이러한 문제를 보완한 방법이 Multilevel Feedback Queue Scheduling이다.

CPU 자원을 사용하고 있는 프로세스가 정해진 타임 슬라이스안에 작업을 완료하지 못하면 다음 우선순위를 가진 queue에 삽입하여 우선순위가 낮았던 다른 프로세스도 CPU 자원을 사용할 수 있도록 한다.

동기화

위에서 볼 수 있듯이 프로세스에 자원을 할당하는 여러가지 방식이 존재한다. 그리고 이처럼 여러가지 프로세스가 실행될 때 올바른 동작을 위해 프로세스간의 순서를 제어하고 동시에 여러 프로세스가 접근해서는 안되는 공유 자원에 관한 접근을 관리하는 등 프로세스 동기화가 이루어 져야 한다.

하나의 계좌에 두 명이 동시에 입금하는 상황을 생각해보자. 만약 계좌에 100만원이 들어 있고 P라는 사람이 20만원을 입금할 때 O라는 사람도 동시에 10만원을 입금하는 상황을 프로세스의 입장에서 생각해보자

우선 P라는 프로세스와 O라는 프로세스는 기존 계좌에 있던 금액인 100만원이라는 정보가 필요하다. 그렇기에 100만원이라는 정보는 다른 프로세스가 공유하는 공유자원이다

그렇기에 P 프로세스가 20만원을 입금하는 과정을 마치치 않은 상태에서 O 프로세스가 기존 100만원의 정보를 읽어와서 P 프로세스가 종료된 이후에 O 프로세스가 종료된다면 O 프로세스의 결과 값이 P 프로세스의 결과값을 Override하여 계좌에 최종적으로 업데이트되는 금액은 120만원이 아니라 110만이 될 것이다.

위와 같은 문제를 방지하기 위해 운영채제는 동시에 접근해서 안되는 공유자원에 프로세스가 동시에 접근하지 못하게 프로세스를 관리한다.

여기서 프로세스가 공유 자원에 접근하는 코드영역을 Critical Section이라고 하며 여러 프로세스가 동시에 공유 자원에 접근하여 문제가 발생할 수 있는 상황을 Race Condition이라고 한다.

운영체제는 Mutexes Locks, Semaphores, Monitor와 같은 도구를 통해 Race Condition을 방지한다