IT
[OS] CPU 스케줄링
최단비(Sweet_Rain)
2021. 6. 14. 00:02
SMALL
< CPU 스케줄링 알고리즘 >
- FCFS - 비선점
- CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받음
- convoy effect 발생할 수 있음
- 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기 기다리는 것
- SJF (Shortest Job First) - 비선점
- 가장 작은 CPU burst 시간을 가진 프로세스에게 우선적으로 CPU를 할당함
- 비선점이므로 가장 먼저 도착한 p1이 일단 실행하고, 그 다음 burst time이 작은 p3 순으로 실행함
- SRTF (Shortest Remaining Time First) - 선점형
- 먼저 온 프로세스가 CPU를 할당받고 있더라고 남은 처리 시간이 뒤에 온 프로세스의 처리 시간보다 길면 CPU를 빼앗김
- RR (Round Robin) - 선점형
- 프로세스에게 각각 동일한 CPU 시간 할당량 (time quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 하여 선점형으로 동작함
- 만약 할당 시간동안 처리를 다 하지 못하면 CPU를 빼앗고 다른 프로세스에게 넘김
- 규정 시간량이 작으면 문맥 교환을 많이 하므로 평균 반환시간이 더 좋지 않음.
- 빼앗긴 프로세스는 준비 큐의 맨 뒤로 감
- 우선순위 스케줄링
- 선점형 : 새로 도착한 프로세스의 우선순위 > 현재 실행되는 프로세스의 우선순위 -> CPU 선점
- 비선점형 : 준비완료 큐의 머리 부분에 새로운 프로세스를 넣음
- 운영체제 혹은 사용자에 의해 프로세스에 우선순위를 부여하고, CPU는 가장 높은 우선순위를 가진 프로세스에 할당됨
- 문제점
- 높은 우선순위의 프로세스가 계속 들어올 경우, 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생함 (무한 봉쇄, 기아 상태)
- starvation 문제 해결 방안 - 노화 (againg)
- 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜주는 방법
- 문제점
- 다단계 큐 스케줄링
- 여러 개의 준비 큐를 가지는 스케줄링 방법
- 각 큐는 절대적인 우선순위를 가짐
- 우선순위가 높은 큐에 존재하는 프로세스부터 실행, 해당 큐가 비어있어야 그 아래 큐 실행할 수 있음
- 작업이 한 큐에서 다른 큐로 옮겨지지 않음
- 큐 간의 절대적인 우선순위 때문에 starvation이 발생할 수 있음
- 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링
- 프로세스가 큐들 사이에 이동하는 것을 허용함
- 프로세스들을 CPU burst 성격에 따라 구분함
- 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동됨
- I/O 중심의 프로세스와 대화형 프로세스들을 높은 우선순위의 큐에 넣음. (이들은 통상적으로 짧은 CPU 버스트가 특징이다.)
- 마찬가지로 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있다.
- 이 방법으로 startvation 을 예방한다.
- HRN(Highest Response-ratio Next) 스케줄링
- 짧은 작업에 유리한 SJF의 단점을 개선한 기법- 비선점
- 최소작업 우선 스케줄링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평 등을 보완
- 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간
- 시스템 응답 시간 = 대기 시간 + 서비스 시간
- 장점
- 자원을 효율적으로 사용함
- 기아가 발생하지 않음
- 오버헤드 발생할 수 있음 (메모리, 프로세서 낭비)
LIST