[운영체제] CPU 스케줄링

1. CPU 스케줄러

Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합

CPU 스케줄러는 ready queue에 존재하는 프로세스들을 대상으로 다양한 방법으로 실행 순서를 결정한다.

선점형(Preemptive) / 비선점형(Non-Preemptive) 스케줄링

선점형(preemtive) : 현재 수행중인 프로세스 대신에 다른 프로세스가 CPU를 차지할 수 있다.

비선점형(non-preemtive) : 일단 CPU 점유권을 가지면 완료될 때까지 반환하지 않는다. 할당되었던 CPU가 반환될 때만 다음 프로세스가 실행된다.

 

2. 스케줄링 종류

선점형(preemtive) 

• SRTF(Shortest Remaining Time First) : 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU 를 뺏긴다. Starvation이 생길 수 있다.
• Round Robin : 각 프로세스가 동일한 크기의 할당 시간을 가지며 할당된 시간만큼 CPU를 점유하고 나면 다시 큐의 맨 마지막으로 돌아간다. 잦은 컨텍스트 스위칭이 일어난다.

비선점형(non-preemtive) 

• FCFS(First Come - First Served) : 먼저 할당된 프로세스를 먼저 실행한다. 긴 작업이 먼저 할당되면 효율성이 낮아진다.
• SJF(Shortest Job First) : CPU burst time이 짧은 프로세스 순으로 할당한다. 긴 작업에 대해서 starvation 현상이 생길 수 있다.
• Priority Scheduling : 우선순위가 가장 높은 프로세스에게 CPU 를 할당한다. 선점 또는 비선점 방식으로 사용할 수 있다. Starvation 현상이 생길 수 있으며 aging(오래 기다릴 시 우선순위 상승)을 통해 해결할 수 있다.

 

2. 프로세스 동기화

Race condition

여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황

 

Critical Section

멀티 스레딩 등에서 동일한 자원을 동시에 접근하는 작업(공유하는 변수 사용, 동일 파일을 사용 등)을 실행하는 코드 영역

 

critical section의 해결을 위한 3요소

1. Mutual Exclusion (상호 배제) 

 - 이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical Section에 진입하면 안 된다.

 

2. Progress (진행)

 - Critical Section에서 작업 중인 프로세스가 없다면, Critical Section에 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 한다. 

 

3. Bounded Waiting (한정 대기)

 - 프로세스가 Critical Section에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다. 쉽게 말해, Critical Section에 진입하려는 프로세스가 무한정 기다려서는 안 된다. 

 

Deadlock

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

 

Starvation

프로세스가 원하는 자원을 계속 할당받지 못하는 상황.

 

 

참고:

https://rebro.kr/176