스케줄링
- 스케줄링은 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원을 어떻게 배정할지 결정하는 일을 말한다.
- CPU 스케줄링은 규모에 따라 고수준, 중간, 저수준 스케줄링으로 구분할 수 있다.
고수준 스케줄링
- 어떤 작업을 시스템이 받아들일지 거부할지를 결정하는 단계로, 작업 요청이 오면 스케줄러가 시스템의 상황을 고려하여 승인 여부를 결정한다.
- 고수준 스케줄링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 수가 정해지기 때문에, 고수준 스케줄링은 멀티 프로그래밍 정도를 제어하는 역할을 한다.
중간 수준 스케줄링
- 고수준 스케줄링이 프로세스를 활성화할지 말지를 결정하여 전체 프로세스의 수를 조절하더라도, 프로세스가 활성화 된 후에 여러가지 사정으로 시스템에 과부하가 걸릴 수 있다.
- 중간 수준 스케줄링은 중지와 활성화를 통해 전체 시스템의 활성화된 프로세스의 수를 조절하여 과부하를 막는다.
- 즉, 어떤 프로세스를 보류 상태로 보낼것인지와, 보류 상태의 프로세스 중 어느 것을 다시 활성 상태로 가져올 것인지를 결정한다.
저수준 스케줄링
- 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.
- 오늘날의 CPU 스케줄러는 대부분 중간 수준 스케줄링과 저수준 스케줄링으로 구성되어 있으며, 저수준 스케줄러가 어떤 기준에 따라 프로세스를 선택하느냐에 따라 시스템의 성능에 많은 영향을 미친다.
스케줄링 알고리즘
- 선점형: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식
- 비선점형: 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식
비선점형 | FCFS, SJF, HRN |
선점형 | 라운드 로빈, SRT, 다단계 큐, 다단계 피드백 큐 |
둘 다 가능 | 우선순위 스케줄링 |
- 스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 이용하며, 평균 대기 시간은 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값을 의미한다.
FCFS (Firtst Come First Served)
- 준비 큐에 도착한 순서대로 CPU를 할당받는 비선점형 방식
- 초기의 일괄작업 시스템에서 사용되었으며, 프로세스가 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.
- 단순하고 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리게 되어 시스템의 효율성이 떨어진다. (콘보이 효과)
- 또한, 현재 작업 중인 프로세스가 입출력 작업을 요구하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율이 떨어진다.
SJF (Shortest Job First)
- 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스부터 CPU를 할당받는 비선점형 방식
- 운영체제가 프로세스의 종료시간을 정확하게 예측하기 어렵고 공평하지 못하다는 단점
- 실행 시간이 짧은 프로세스가 계속 준비 큐에 들어오면 실행 시간이 긴 프로세스는 작업이 계속 연기되는데, 이를 아사 현상 또는 무한 봉쇄현상이라고 한다.
- 프로세스가 양보할 수 있는 상한선을 정하는 에이징으로 완화할 수 있지만, 에이징 값을 어떤 기준으로 정할 것인지에 대한 문제 존재
HRN (Highest Response Ratio Next)
- 아사 현상을 해결하기 위해 만들어진 비선점형 스케줄링 방식
- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방식으로, 우선순위를 정할 때 대기시간을 고려해 아사 현상을 완화한다.
- 하지만 여전히 공평성이 위배되므로 많이 사용하지 않는다.
라운드 로빈
- 한 프로세스가 타임 슬라이스 동안 작업하다가 타임 아웃이 발생하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식으로, 우선순위가 적용되지 않은 선점형 스케줄링 방식
- 선점형 알고리즘 중 가장 단순하고 대표적인 방법으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다.
- 프로세스가 CPU를 일정 시간동안 사용한 후 다른 프로세스에게 넘기기 때문에, 앞의 긴 작업을 무작정 기다리는 콘보이 효과가 줄어든다.
- 만약 타임 슬라이스가 너무 커지면 FCFS와 똑같이 동작하게 되고, 너무 작아지면 잦은 문맥교환으로 인한 오버헤드가 발생하므로 적당한 타임 슬라이스를 설정하는 것이 중요하다.
SRT (Shortest Remaining Time)
- SJF의 선점형 버전으로, 프로세스가 도착할 때마다 남아있는 실행 시간을 비교해 더 짧은 프로세스가 선택되는 방식
- 프로세스들의 남은 시간을 주기적으로 계산하고 문맥교환을 하는 추가 작업이 필요하다.
- 운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 발생하기 때문에 잘 사용하지 않는다.
다단계 큐
- 우선순위에 따라 준비 큐를 여러 개 사용하는 방식으로, 프로세스는 우선순위에 따라 해당 우선순위의 큐에 삽입된다.
- 각각의 큐는 라운드 로빈 방식으로 운영되며, 상단에 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.
- 우선순위와 작업 형태를 고려하여 다양한 스케줄링이 가능한 선점형 방식
다단계 피드백 큐
- 우선순위가 낮은 프로세스가 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식으로, 프로세스가 CPU를 할당받아 실행될 때마다 우선순위를 낮춘다.
- 또한 우선순위에 따라 타임 슬라이스의 크기가 다르게 설정하는데, 우선순위가 낮은 프로세스는 CPU를 얻을 확률이 낮기 때문에 타임 슬라이스를 크게 설정하는 것
'Computer Science > Operating System' 카테고리의 다른 글
프로세스 생성 (0) | 2022.04.08 |
---|---|
프로세스 제어 블록과 문맥교환 (0) | 2022.03.15 |
프로세스와 스레드 (0) | 2022.03.15 |
병렬 처리 (0) | 2022.03.15 |
컴퓨터 성능 향상 기술 (0) | 2022.03.14 |