Week3 CPU Scheduling
CPU 스케줄링
기아 상태가 뭔가요?
우선순위 기반 스케줄링 시스템에서 우선순위가 낮은 프로세스가 계속해서 자원을 할당받지 못하는 상태
기아 상태를 어떻게 해결할 수 있나요?
에이징(Aging) 기법: 오랫동안 자원을 할당받지 못한 프로세스의 우선순위를 점진적으로 증가시
라운드 로빈: 공정한 CPU 사용 기회
CPU 스케줄링에 대해 설명해주세요.
시스템의 CPU 자원을 효율적으로 관리하고 프로세스의 성능을 극대화하기 위해, 여러 프로세스 중에서 어떤 프로세스가 CPU를 사용할지 결정하는 과정
처리량(Throughput)을 극대화 응답시간(Response Time) 최소화, CPU 자원의 효율적 사용
FCFS, SJF, 라운드 로빈, 우선순위 스케줄링
스케줄러의 종류는 무엇이 있나요?
단기 스케줄러: CPU에서 어떤 프로세스를 실행할지 결정
Ready 상태에 있는 프로세스들 중에서 다음 프로세스 실행 결정(CPU 스케줄링 알고리즘)
중기 스케줄러: 메모리에서 프로세스를 스왑 인/아웃하여 메모리 자원 관리
메모리 관리 역할. 프로세스가 과부하 상태 또는 메모리 부족일 경우, 프로세스를 일시적으로 디스크로 swap-out 하는 역할. 자원이 충분해지면 다시 swap-in
장기 스케줄러: 디스크에 있는 작업을 메모리로 가져와 실행할지 결정하는 역할
새로운 프로세스를 시스템에 진입시킬지 여부를 결정.
다중 프로그래밍 정도(한번에 메모리에 적재되는 프로세스 수)를 관리
선점형 스케줄링과 비선점형 스케줄링의 차이
비선점형 스케줄링(FCFS, SJF)
프로세스가 실행되는 도중에 다른 프로세스가 CPU를 강제로 빼앗을 수 없습니다.
컨텍스트 스위칭: 적음
응답시간: 느림
선점형 스케줄링(라운드 로빈, SRTF-Shortest Remain Time First)
현재 실행 중인 프로세스가 CPU를 점유하고 있더라도, 더 높은 우선순위를 가진 프로세스가 도착하면 강제로 CPU를 빼앗길 수 있는 방식
컨텍스트 스위칭: 많음
응답시간: 실시간
선입선출 스케줄링(FCFS)에 대해 설명해주세요.
비선점형 스케줄링 알고리즘 (작업을 완료할 때까지 CPU를 독점)
장 먼저 대기 큐에 도착한 프로세스부터 순서대로 CPU를 할당
단점: Convoy 효과. CPU 사용시간이 긴 프로세스가 먼저 도착하면 짧은 CPU 작업을 가진 프로세스들이 긴 시간을 대기.
최단 작업 우선 스케줄링(SJF)
비선점형 스케줄링 알고리즘 (작업을 완료할 때까지 CPU를 독점)
CPU 실행 시간이 가장 짧은 프로세스를 먼저 실행
단점으로는 CPU 실행 시간을 미리 알아야 하고, Starvation 현상이 발생할 수 있음.
최소 잔류 시간 우선 스케줄링(SRTF)
선점형 스케줄링 알고리즘
현재 CPU에서 실행 중인 프로세스의 남은 실행 시간과 새롭게 도착한 프로세스의 실행 시간을 비교하여, 남은 시간이 더 짧은 프로세스가 있으면 현재 작업 중인 프로세스의 CPU를 선점하여 처리하는 방식
장점으로는 Convoy효과가 발생하지 않고 평균 대기 시간을 최소화
단점으로는 CPU 실행 시간 예측이 어렵다는 것, Starvation 효과, 컨텍스트 스위칭이 자주 발생
우선순위 스케줄링에 대해 설명해주세요
선점형, 비선점형 모두 가능.
프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스가 먼저 CPU를 할당받는 스케줄링 방식
우선순위는 CPU 실행시간/ 프로세스 중요도/ 메모리 사용량에 따라 결정
장점으로는 응답시간 최소화, 다양한 스케줄링 정책 적용 가능
단점으로는 Starvation현상 -> 에이징 기법으로 해결
선점형일 경우 높은 컨텍스트 스위칭 비용
라운드 로빈 스케줄링에 대해 설명해주세요.
선점형 스케줄링 알고리즘
정해진 시간(Time Quantum, 타임 퀀텀) 동안만 CPU를 사용하고, 시간이 지나면 강제로 CPU를 반납한 후 대기 큐의 맨 뒤로 이동. 공평하게 CPU를 사용할 기회
타임 퀀텀에 따라 응답시간이 짧아지거나 프로세스가 CPU를 더 오래 사용(비선점형에 가까워짐)
장점으로는 기아 현상이 발생하지 않고, 대화형 시스템에 적합합니다.
단점으로는 컨텍스트 스위칭 오버헤드가 발생할 수 있고, 타임 퀀텀 설정이 중요합니다.
Time Quantum을 정하는 방식
프로세스들의 평균 CPU 버스트 시간 기반 설정
응답 시간 목표 기반 설정
컨텍스트 스위칭 오버헤드 고려
동적 타임 퀀텀 설정(Dynamic Time Quantum)
프로세스의 우선순위나 현재 시스템 부하에 따라 타임 퀀텀이 짧아지거나 길어질 수 있습니다.
예시: CPU 사용량이 높은 프로세스에게 더 긴 타임 퀀텀을 부여하거나, 시스템 부하가 커지면 타임 퀀텀을 줄여 많은 프로세스가 번갈아 실행되도록 조정할 수 있습니다.
멀티 레벨 큐 스케줄링이 뭔가요?
여러 개의 큐를 사용하여 다양한 우선순위를 가진 프로세스들을 그룹으로 나누어 각각의 큐에서 스케줄링하는 방식
프로세스의 특성에 따라 서로 다른 큐에 배정하고, 각 큐에 대해 다른 스케줄링 알고리즘을 적용
전위 큐(Foreground Queue): 일반적으로 대화형 프로세스(응답 시간이 중요한 프로세스)가 들어가는 큐로, 라운드 로빈(Round Robin)과 같은 선점형 스케줄링이 적용됩니다.
후위 큐(Background Queue): 배치 작업이나 우선순위가 낮은 작업이 들어가는 큐로, FCFS(First-Come, First-Served)와 같은 비선점형 스케줄링이 적용될 수 있습니다.
장점으로는 다양한 유형에 맞는 스케줄링으로 유연하게 관리 가능
단점으로는 각 큐의 알고리즘에 따른 기아현상 발생 가능 -> 에이징 기법으로 해결
단점으로 큐 간 이동 불가. 프로세스의 특성이 변해도 다른 큐로 이동 불가
큐 간에도 스케줄링이 존재.
우선순위 기반
타임 슬라이드(타임 퀀텀)
에이징 기법
멀티 레벨 피드백 큐 스케줄링에 대해 설명해주세요.
"프로세스가 계속해서 동일한 큐에 머무는 것이 아니라, CPU 사용 패턴에 따라 큐 사이를 이동한다는 점"
여러 개의 우선순위 큐를 사용하여 프로세스의 상태나 CPU 사용 패턴에 따라 프로세스가 다른 큐로 이동할 수 있는 스케줄링 방식
동적인 스케줄링 알고리즘으로, 각 프로세스의 실행 시간과 우선순위에 따라 다른 큐로 재배치
Example
3개의 우선순위 큐가 있습니다:
큐 1: 가장 높은 우선순위, 타임 퀀텀 5ms (대화형 작업)
큐 2: 중간 우선순위, 타임 퀀텀 10ms (중간 정도의 CPU 사용량 작업)
큐 3: 가장 낮은 우선순위, 타임 퀀텀 20ms (긴 배치 작업)
4개의 프로세스가 있습니다:
P1: 도착 시간 0ms, 실행 시간 16ms
P2: 도착 시간 1ms, 실행 시간 6ms
P3: 도착 시간 2ms, 실행 시간 10ms
P4: 도착 시간 3ms, 실행 시간 25ms
1단계: 처음 도착한 프로세스 처리
시간 0ms:
P1이 도착합니다. **큐 1(가장 높은 우선순위)**에 할당되어 CPU를 받습니다.
P1은 5ms 동안 실행되고 타임 퀀텀을 모두 소모하지만, **전체 실행 시간(16ms)**을 완료하지 못합니다.
남은 시간은 11ms입니다.
P1은 **큐 2(중간 우선순위)**로 이동합니다.
2단계: 새로운 프로세스 도착
시간 1ms:
P2가 도착합니다. 큐 1에 들어갑니다.
P1이 큐 2로 이동한 상태이므로, P2는 CPU를 할당받습니다.
P2는 5ms의 타임 퀀텀 동안 실행되고 6ms 중 5ms를 사용했으므로, 남은 1ms가 남습니다.
큐 1에서 계속 대기하지 않고, 큐 2로 이동합니다.
3단계: 추가 프로세스 도착
시간 2ms:
P3가 도착하여 큐 1에 들어갑니다.
P3가 CPU를 할당받고, 5ms 동안 실행되어 전체 10ms 중 5ms를 사용합니다.
남은 시간은 5ms이며, P3도 큐 2로 이동합니다.
4단계: 또 다른 프로세스 도착
시간 3ms:
P4가 도착하여 큐 1에 들어갑니다.
P4는 5ms 동안 실행되어 25ms 중 5ms를 사용합니다.
남은 20ms를 완료하기 위해 큐 2로 이동합니다.
5단계: 큐 2의 처리
시간 6ms~10ms:
큐 1에 남아있는 프로세스가 없기 때문에, 큐 2에서 처리 시작됩니다.
P1이 먼저 큐 2에서 CPU를 할당받습니다. 타임 퀀텀 10ms로 실행되고 남은 11ms 중 10ms를 모두 사용합니다.
P1은 이제 남은 시간이 1ms이므로, **큐 3(가장 낮은 우선순위)**로 이동합니다.
6단계: 계속되는 큐 2 처리
시간 11ms~20ms:
큐 2에서 P2가 다시 CPU를 받습니다. P2는 남은 1ms만 남아 있었으므로, 실행을 마치고 종료됩니다.
이후 P3가 CPU를 받습니다. P3는 5ms를 더 실행하여 10ms를 모두 완료하고 종료됩니다.
마지막으로 P4가 CPU를 받습니다. 큐 2에서 10ms를 사용해 남은 20ms 중 10ms를 완료합니다.
P4는 남은 10ms로 큐 3으로 이동합니다.
7단계: 큐 3 처리
시간 21ms~30ms:
큐 3에서 가장 먼저 도착한 P1이 남은 1ms를 처리하여 종료됩니다.
이후 P4가 CPU를 할당받아 남은 10ms를 처리하고 종료됩니다.
최종 프로세스 완료 시간:
P1: 22ms에 종료
P2: 12ms에 종료
P3: 20ms에 종료
P4: 30ms에 종료
"큐3이 실행되다가 큐1에 새로운 프로세스가 도착하면 큐3의 타임 슬라이스가 끝나면 큐1의 프로세스를 실행하고, 큐1의 프로세스의 타임슬라이스가 끝나면 큐2로 가게되고, 큐1의 프로세스가 없으면 큐2를 실행한뒤에 큐3으로 배치"
Last updated