Week3 CPU Scheduling

CPU 스케줄링

참고: 프로세스 스케줄링 != CPU 스케줄링

프로세스 스케줄링은 CPU 스케줄링의 상위 개념.

비유로 설명:

• 프로세스 스케줄링은 회사에서 직원들을 각각의 회의실(또는 컴퓨터)로 배치하는 일입니다. 어떤 직원이 어떤 회의실에서 일할지를 정하는 과정입니다.

• CPU 스케줄링은 특정 회의실(또는 컴퓨터)에 들어온 직원들 중에서 누가 먼저 발표(또는 작업)를 할지를 정하는 일입니다.

프로세스 스케줄링 종류:

• I/O 스케줄링

• 메모리 스케줄링

• 네트워크 스케줄링

• 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으로 배치"