🤽CPU 스케줄러

단기 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스들 중에서 선택하여, 이들 중 하나에게 CPU를 할당

비선점 스케줄링과 선점 스케줄링

• 비선점 스케줄링은 스케줄링 면에서 선택의 여지가 없음
• 실행을 위해 새로운 프로세스를 반드시 선택
• 선점 스케줄링은 선택의 여지가 있음
• 공유 자료에 대한 접근을 조정하는 데 필요한 비용을 유발
• 선점은 또한 운영체제 커널 설계에 영향 (동시 사용으로부터 보호)

CPU 스케줄링 결정 네 가지 상황

• 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (ex. IO요청이나 자식 프로세스들 중의 하나가 종료되기를 기다리기 위해 wait를 호출할 때) : 비선점
• 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (ex. 인터럽트가 발생) : 선점
• 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (ex. I/O 종료시) : 선점
• 프로세스가 실행 상태에서 종료할 때 : 비선점

👻디스패처 (Dispatcher)

• 디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈
• 아래 작업 수행
  • 문맥 교환 (context change)
  • 사용자 모드로 전환
  • 사용자 프로그램의 적절한 위치로 이동 (jump)
• 디스패치 지연 : 프로세스를 정지하고 다른 프로세스의 수행하는 데까지 소요되는 시간

🍯스케줄링 기준

CPU 스케줄링 시 프로세스 선택 기준 : 최적화 기준으로 사용

• CPU 이용률(CPU utilization) : 가능한 한 CPU를 최대한 바쁘게 유지
• 처리량(throughput) : 단위 시간당 완료된 프로세스의 개수
• 총 처리 시간(turnaround time) : 프로세스를 실행하는 데 소요된 시간
• 대기 시간(waiting time) : 프로세스가 준비 완료 큐에서 대기하는 시간
• 응답 시간 (response time) : 대화식 시스템에서 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간 (시작되는 데까지 시간o, 출력하는 데까지 시간x)

🐘스케줄링 종류

선입 선처리 스케줄링 (First-Come First-Served Scheduling, FCFS)

• 프로세스들이 1,2,3 도착하고, 선입 선처리 순으로 서비스 받는다면 1,2,3 순서로 실행
• CPU 버스트(프로세스 실행 시간)이 긴 프로세스가 먼저 온다면 평균 대기 시간 증가

최단 작업 우선 스케줄링 (Shortest-Job-First Scheduling, SJF)

• 최단 작업 우선 스케줄링 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관
  • (개인적으로 용어 헷갈릴 때 - 비선점형은 다른 개체가 현재를 뺏어가지 못한다고 생각)
  • 비선점형(nonpreemptive) : 지금 프로세스가 실행 중이면, CPU 버스트를 끝낼 때까지 선점되지 않음
  • 선점형(preemptive) : 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가지면 현재 실행 중인 프로세스를 선점
• SFJ 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적

우선순위 스케줄링 (Priority Scheduling)

• 우선순위 숫자가 각 프로세스들에게 연관
• 우선 순위 계산 사용 예
  • 내부적 : 시간 제한, 메모리 요구, 열린 파일의 수, 평균 입/출력 버스트의 평균 CPU 버스트에 대한 비율 등
  • 외부적 : 프로세스의 중요성, 컴퓨터 사용을 위해 지부되는 비용의 유형과 양 등
• 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 기아 상태(starvation) 발생
  • 오랫동안 대기하는 프로세스들에 우선순위 가점을 주는 노화기법(aging)으로 해결

라운드 로빈 스케줄링 (Round-Robin Scheduling, RR)

각 프로세스는 시간 할당량(time quantum) 또는 시간 조각(time slice)이라고 하는 작은 단위의 시간을 획득하고, 이 시간이 지나면 프로세스는 선점되고 준비완료 큐의 꼬리에 추가

• 시분할(대화형) 시스템에 적합
• 시간 할당량이 최소한 문맥 교환 시간에 비해 더 커야하지만 너무 크면 FIFO 정책과 같아짐
• 시간 할당량이 작으면 오버헤드가 너무 높게 됨

다단계 큐 스케줄링 (Multilevel Queue Scheduling)

• 다단계 큐 스케줄링 알고리즘은 준비 완료 큐를 다수의 별도의 큐로 분류
  • 포어그라운드(foreground, 대화형) :: RR 알고리즘
  • 백그라운드(background, 일괄 처리) 프로세스 :: FCFC 프로세스
  • 큐와 큐 사이에 스케줄링
    • 고정 우선순위의 선점형 스케줄링 : 포그라운드 우선 순위 >>> 백그라운드
    • 큐들 사이에 시간을 나누어 사용 (ex. 포 : CPU 시간의 80%, 백 : CPU 시간의 20% )

다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)

• 위와 달리 프로세스가 큐들 사이를 이동하는 것을 허용 :: 노화(aging) 구현에 이용
• 스케줄링에 영향을 주는 요소
  • 큐의 개수
  • 각 큐를 위한 스케줄링 알고리즘
  • 한 프로세스를 높은 우선순위 큐로 올려준느 시기를 결정하는 방법
  • 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
  • 프로세스가 서비스를 필요로 할 때 프로세스가 들어갈 큐를 결정하는 방법

스레드 스케줄링 (Thread Schduling)

• 사용자 수준과 커널 수준 스레드는 스케줄링에서 차이 : 최신 OS는 프로세스가 아닌 커널 수준 스레드를 스케줄링 함
• 다대일, 다대다 모델의 시스템에서는 스레드 라이브러리가 사용자 수준 스레드를 가용한 LWP 상에서 스케줄링
  • LWP(light weight process) : 사용자 스레드와 커널 스레드 사이에 존재하는 중간 자료구조
  • PCS(process-contention scope) : 같은 프로세스에 속한 스레드들 사이에서 CPU를 경쟁
• CPU 상에 어느 커널 스레드를 스케줄할 것인지 결정할 때 SCS
  • SCS(system-contention scope) : 시스템-경쟁 범위
  • 윈도우, 리눅스와 같은 일대일 모델은 SCS만을 사용하여 스케줄

🦴참고

Operating System Concepts, 10th Ed.