cpu 스케줄링

스케줄러의 종류

장기 (작업) 스케줄러

프로세스의 생성 과정에서 프로세스의 준비상태에 무엇을 추가할지 결정

중기 스케줄러

작업의 혼합 개선 혹은 메모리 가용량 증가를 위해 교체 작업

단기 (CPU) 스케줄러

미리 정해진 정책(알고리즘)에 따라 실행할 프로세스를 선택

디스팻처 : 단기 스케줄러가 선택한 프로세스에 실질적으로 CPU에 할당해주는 분배기. 문맥교환을 수행하고 사용자 모드로 전환한다.
디스팻처 지연 : 한 프로세스를 멈추고 다른 프로세스를 시작하는데까지 소요되는 시간

비선점 스케줄링

• 다른 프로세스에 할당된 자원을 못뺏는 스케줄링
• 응답시간 예측이 쉬움

선점 스케줄링

• 현재 실행중인 프로세스를 인터럽트하거나 준비상태로 이동시킬 수 있는 스케줄링
• 우선순위가 높은 프로세스들이 긴급한 처리를 요청할 때 유용
• 선점 할 때 메인메모리에 많은 프로세스들이 저장되어 있어야 하므로 많은 오버헤드 발생

스케줄링 알고리즘

알고리즘의 비교 기준

• CPU 이용률(utilization)
• 처리량 (throughput)
• 총처리 시간 or 반환 시간(turnaround time)
• 대기 시간(waiting time) - 준비큐에서 대기하는 시간
• 응답시간 or 반응 시간(response time) - 요청을 제출하고 부터 첫번째 응답이 나올 때까지의 시간

알고리즘들

FCFS

일괄처리 시스템에 효율적 but 대화식 시스템에 부적합

SJF (Shortest-Remaining-Time-First Scheduling)

최단 작업 우선 스케줄링의 문제점 : 실행 시간의 길이 예측이 힘듬

SJF는 선점 비선점이 모두 가능

Priority 스케줄링

• 최고 우선순위의 프로세스를 cpu에 할당
• SJF가 우선순위 스케줄링에 포함된다
• 마찬가지로 선점/비선점 모두 적용 가능
• 문제점
  • 기아 상태 발생 가능 - 우선순위 높은 친구들만 계속 들어오면 우선순위 낮은 친구들이 무한정 기다려야 하는 상황
  • 해결방법 : Aging 기법 - 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 기법

RR 스케줄링 - 선점 알고리즘

• 시분할 시스템을 위해 설계됨
• 규정 시간량(Time Quantum) 또는 시간 할당량(Time Slice)을 정의
• 준비 큐는 FCFS이면 Circular Queue로 설계
• 규정 시간량이 지나면 인터럽트가 발생되며 문맥교환 수행
  
• 규정 시간량이 너무 클 경우 - 작업이 긴 프로세스들 때문에 작업시간이 짧은 프로세스들이 대기-> 평균 대기 시간 길어짐
• 규정 시간량이 너무 짧은 경우 - N개의 프로세스가 실제 프로세서 속도의 1/N 속도로 실행되는 것 처럼 보임(느리게) -> 문맥교환 횟수 증가로 프로세서의 유휴시간 증가

다단계 큐 스케줄링

다단계 피드백 큐 스캐줄링

• 다단계 큐는 작업이 시스템에 들어가면 한 큐에서만 고정이라 스케줄링 부담은 적지만 융통성이 부족
• 다단계 피드백 큐는 작업이 큐 사이를 이동할 수 있다. - 어떤 작업이 요구하는 프로세스 시간이 너무 길면 작업을 낮은 단계 큐로 옮긴다.
• 기아상태 예방을 위한 에이징 방법 활용 가능
  • 특정 큐에서 오래 기다린 프로ㅔ쓰를 우선순위가 높은 큐로 이동
  • 프로세서 점유 시간이 긴 작업을 우선순위 낮은 큐로 이동

그 외의 스케줄링

• HRN - 비선점 : 대기시간 + 서비스받을 시간 / 서비스 받을 시간
• 다중 처리기
• 실시간 스케줄링