코드 없는 알고리즘과 데이터 구조 (암스트롱 수베로 지음)
목차
Part 1 - 데이터 구조
Part 2 - 알고리즘
Part 3 - 알고리즘과 데이터 구조를 이해하는데 필요한 지식들
10. 무작위성
11. 스케줄링 알고리즘
📍스케줄러와 스케줄링
모든 운영체제 내부에는 프로세스 스케줄러가 존재
✅역할
- 어떤 태스크가 언제 실행될지 결정
✅디스패처(dispatcher)
- 문맥 전환을 수행하고 프로그램의 실행 흐름을 바꾸는 프로세스 스케줄러의 일부
- 문맥 전환(context switching) : 프로세스 -> 다른 프로세스 혹은 태스크 -> 다른 태스크
✅스케줄링 큐
- 프로세스가 나열된 큐
- 태스크 큐 : 메인 메모리 할당을 기다리는 모든 프로세스가 나열
- 준비 큐 : 메인 메모리에 상주하면서 CPU 점유를 기다리는 모든 프로세스가 나열
- 장치 큐 : 입출력 장치 할당을 기다리는 프로세스가 나열
✅스케줄링 구분
- 선점(preemptive) 스케줄링 : 태스크가 우선순위를 가짐
높은 우선순위를 가진 태스크가 현재 CPU를 점유한 낮은 우선순위의 태스크도 중단할 수 있음
- 비선점(nonpreemptive) 스케줄링 : 종료되거나 입출력을 위해 자발적 문맥 전환이 일어날때 까지 CPU를 점유한 작업이 계속 실행됨
이외에도 다수의 태스크가 CPU 자원을 효율적으로 공유할 수 있도록 스케줄링 알고리즘 들이 고안됨
- 실행시간이 긴 프로세스가 CPU를 독점하지 않도록.. (빨리 끝나는 다른 작업들이 대기해야함..)
📍선착순 스케줄링 알고리즘(first come first serve, FCFS)
- 먼저 도착하는 프로세스를 먼저 실행 (FIFO) 하므로 큐 데이터 구조를 사용
문제
- CPU 점유 시간이 긴 프로세스로 인해 다른 프로세스를 실행할 여지가 거의 없다는 한계 존재
- 이로 인해 유저가 시스템이 멈춰버렸다고 생각할 수 있음
- 우선순위가 낮은 태스크가 CPU를 오랜 시간 점유할 경우, 중요한 태스크가 실행되지 못해 시스템 장애 발생 가능
- 이렇게 병목 현상이 발생하는 것을 호위 상태(convoy effect) 라고 함
📍최단 작업 우선 스케줄링 알고리즘 (shortest job first, SJF)
- 스케줄러가 CPU 점유 시간이 가장 짧은 프로세스부터 우선적으로 할당
SJF 알고리즘의 2가지 유형
✅선점 SJF
- 준비 상태 큐에 도착한 프로세스의 CPU 점유 시간이 실행중인 프로세스의 점유 시간보다 짧다면,
현재 실행중인 프로세스를 멈추고 더 짧은 프로세스를 먼저 수행
✅비선점 SJF
- SJF 이므로 준비 상태 큐에 있는 CPU 점유 시간이 짧은 프로세스가 먼저 큐에서 빠져나오지만,
현재 실행중인 프로세스를 중단하지 않는다
- 이로 인해 starvation이 발생할 수 있다
- starvation : 특정 프로세스의 우선순위가 낮아서 원하는 연산 자원을 계속 할당받지 못하는 것
✅SJF이 FCFS 보다는 낫다
- SJF는 FCFS에 비해 평균 프로세스 대기 시간이 매우 짧다
- 그러나 SJF는 CPU가 작업을 수행하는데 걸리는 시간을 예상해야 한다
- 이는 어려운 작업이며, 대신 수행 시간을 기록해놨다 활용하는 방법이 있지만, CPU 부담을 증가시킨다
📍우선순위 스케줄링 알고리즘
- 스케줄러가 나중에 들어왔어도 우선순위가 더 높은 프로세스를 먼저 처리
✅우선순위 큐 자료구조를 활용
- 우선순위 큐에서는 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 큐에서 삭제된다
(나중에 들어왔어도 우선순위가 높으면 먼저 제거된다)
- 우선순위 스케줄링 알고리즘도 선점, 비선점 유형을 갖는다
- 우선순위가 높은 프로세스가 계속 도착한다면 starvation 이 발생할 수 있다
📍라운드 로빈(round robin) 스케줄링 알고리즘
- 각 프로세스가 CPU 점유시간을 균등하게 공유
✅원리
- 각 프로세스는 CPU 자원을 활용할 수 있는 시간 조각(양자, quantum)을 할당받는다
- 프로세스별 실행 시간을 추적하는 특별한 카운터를 활용한다
✅특성
- 선점 스케줄링 알고리즘이다 (배분된 실행시간이 만료되면 CPU 점유권을 넘겨줘야 함)
- 프로세스별 수행 시간이 극명하게 갈릴 경우 비효율적
📍다단계 큐 스케줄링 & 다단계 피드백 큐 스케줄링 알고리즘
✅다단계 큐 스케줄링
- 각 프로세서의 스케줄링 요구사항을 만족시키는 여러 종류의 준비 상태 큐가 존재
- 각 큐에 우선순위가 주어지고 큐의 성격이 각기 다름 (SJF 일수도 있고, FCFS 일수도 있고..)
✅다단계 피드백 큐 스케줄링
- 다단계 큐 스케줄링의 발전된 버전
- 다단계 큐 스케줄링에서는 프로세스가 하나의 준비 상태 큐에 영구적으로 할당되지만,
- 다단계 피드백 큐 스케줄링에서는 피드백을 활용해 프로세스가 다른 준비 상태 큐로 이동 가능