운영체제 (9) - 프로세스, 스케줄링, Dispatcher

운영체제 수업을 수강하며 정리한 내용을 작성하려고 합니다.

새로운 프로그램 로드, 실행: exec()

• fork()로 생성한 프로세스에 새로운 프로그램을 로드함
  • address space에 새로운 프로그램을 로드함

프로세스 종료: exit()

• 각 프로세스는 로드된 프로그램의 마지막 명령어를 수행함
• 커널에 자신의 삭제를 exit() 시스템 콜을 통해 요청함
  • 이 때, parent 프로세스가 wait()을 실행중인 경우 wait()이 종료됨
  • 프로세스의 리소스가 커널에 의해 할당 해제됨
• Parent가 child를 종료시키는 경우도 존재 - abort()
  • child가 허용된 리소스를 초과했을 때
  • child에게 할당된 태스크가 더 이상 필요하지 않을 때
  • Parent가 끝나고, OS에 의해 child가 Parent없이 동작하지 못할 때
  • abort()는 SIGABRT 시그널을 보낸다

스케줄링이란 무엇인가

• CPU 스케줄링: 어떻게 프로세스에게 CPU의 사용을 분배할 것인가
  • 메모리 내 실행 준비된 프로세스들 가운데 하나를 선택하여 CPU를 할당
• 프로세스 스케줄러가 이용 가능한 프로세스들 중 다음 실행할 것을 선택
• 목표: idle time을 줄이고, CPU 가용성 극대화
  • time sharing을 위해 CPU에 빠르게 프로세스를 전환
  • 커널이 프로세스를 스케줄링 및 전환하는 데 걸리는 시간은?

프로세스 수행 cycle의 특징

• 프로세스 실행 시간 1) CPU 사용 집중 구간 2) IO 사용 집중 구간
  
• CPU-I/O Burst Cycle
  • CPU Burst : CPU로 연산을 수행하는 시간
  • I/O Burst : I/O 처리를 위해 기다리는 시간
  • 일반적인 프로세스는 두 burst를 번갈아 가며 수행됨
• 프로세스 분류에 따른 CPU Burst의 특징
  • I/O-bound 프로세스 : IO에 더 긴 시간, 짧은 CPU bursts
  • CPU-bound 프로세스 : CPU에 더 긴 시간, 긴 CPU bursts
  • 어떤 종류의 프로세스가 많은 지에 따라 스케줄링 기법의 효율성이 달라짐

CPU burst time의 히스토그램

CPU bursts가 짧은 프로세스가 많고, 긴 프로세스가 적다

Dispatcher

• Kernel 내 프로세스의 CPU 스케줄링을 관할하는 구현
  • Context switching
  • Jumping to the proper location in the user program to restart that program

Dispatcher는 어떻게 실행되는가

• 방법1: voluntary yield
  • 프로세스가 CPU 점유를 반환한다고(relinquish) 믿음
  • 프로세스가 CPU를 반환하는 명령어를 호출 E.g., yield() system call (trap)
  • 프로세스가 IO 작업을 할 때
• 방법2: multiprogramming
  • 반드시 OS가 주기적으로 control을 획득할 수 있도록 함
  • 특정 주기의 ‘클락’ (알람)마다 OS에 진입
  • E.g., CPU 또는 별도 칩셋으로부터의 타이머 인터럽트
  • 타이머 인터럽트는 상대적으로 높은 우선순위로 처리
  • 일반적으로 time slice: 10 ms ~ 200 ms

Dispatcher의 동작

• Invoke dispatcher by voluntary yield or time slicing
• Switch from user mode to kernel mode → dispatcher 실행
• Save execution state (registers) of old process in PCB
• Insert PCB in queue
• Decide the next process
• Load state of next process from PCB to registers
• Switch from kernel to user mode
• Jump to instruction in the new user process

Dispatcher 구현의 기본적 구조

• 다음 task의 결정
• 현재 task의 queueing

스케줄링의 종류

• CPU scheduling 의 결정은 대개 다음 상태 변화에서 이루어짐
  • 1) Running → Waiting
  • 2) Running → Ready
  • 3) Waiting → Ready
• 비선점형 스케줄링 (Non-preemptive Scheduling)
  • 실행중인 프로세스가 자발적으로 wait을 하는 경우 (즉, 위에서 1에 해당)
    • 대개 프로세스가 I/O를 할 때 wait으로 자발적으로 이동
  • OS가 프로세스의 CPU 사용을 제어할 수 없음
• 선점형 스케줄링 (Preemptive Scheduling)
  • OS가 현재 CPU를 사용중인 프로세스의 수행을 제어할 수 있음
  • E.g., 프로세스가 일정 시간마다 돌아가면서 CPU를 사용하도록 함 (round robin)
  • 선점을 어떻게 구현하는가?
    • 1) 주기적인 상태 확인 (모니터링)
    • 2) context switching

Scheduling algorithms

• First-Come, First-Served Scheduling
• Shortest-Job-First Scheduling
• Priority Scheduling
• Round-Robin Scheduling
• Multilevel Queue Scheduling
• Multilevel Feedback Queue Scheduling

Scheduling Criteria

• CPU 활용률 (CPU utilization)
  • 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
• 처리량 (Throughput)
  • CPU가 단위 시간 당 처리하는 프로세스의 개수
• 응답 시간 (Response time)
  • 프로세스가 입출력을 시작해서 첫 결과가 나오는데 까지 걸리는 시간
    • 질문: 큐로 설명해 보기
• 대기 시간 (Waiting time)
  • 프로세스가 Ready Queue 내에서 대기하는 시간의 총합
• Turnaround time
  • 프로세스가 시작해서 끝날 때까지 걸리는 시간

Scheduler design

• 이상적인 스케줄러
  • 최대의 CPU 사용률
  • 최대의 처리량
  • 최소의 응답시간
  • 최소의 대기시간
• 시스템의 용도에 따른 요구사항이 상이함
  • 슈퍼 컴퓨터 - CPU 사용률
  • 개인용 컴퓨터 - 응답시간
  • 워크 스테이션 - 처리량
  • 인공지능 시스템 - 정확도 및 학습/추론시간
• 모든 조건을 만족 시키는 스케줄러를 만드는 것은 현실적으로 불가능