운영체제 (10) - fork()와 wait()의 동작원리, 프로세스 스케줄링(FCFS, SJFS, SRTF)

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

Process creation

이러한 프로세스가 존재하는 상황을 가정, fork()를 통해 child 프로세스 생성하면 자식 프로세스가 생성됨

그 후, 부모 프로세스의 wait() 호출하면

자식 프로세스로 넘어가 exec(”bin/ls”) 실행됨

실행 종료 후 1) wait()가 종료되며 부모 프로세스 종료 2) 자식 프로세스 종료

wait() in detail

• Parent가 여러 개의 child process들을 생성하고, 한 번의 wait을 실행함
  • 이 때, wait은 어느 child process의 종료를 기준으로 동작하는가?
    • 가장 빨리 종료되는 child process에 의해 wait이 종료됨

waitpid() API

• 파라미터로 wait()으로 기다릴 pid를 입력받음
  • waitpid(pid_t pid)
• 어떤 API를 사용할 지는 구현하려는 상황에 따라 다름

Process scheduling

• Process의 state
  • Running: 현재 CPU 사용
  • Ready: CPU 사용 가능
  • Wait: CPU 잡아도 곧바로 instruction 수행 불가

스케줄러 실행 (Voluntary yield) → 비선점형 스케줄러

Timer-based interrupt가 추가된 스케줄러 실행

FCFS Scheduling

• Ready 큐에 있는 순서대로 CPU를 할당한다.

  • FIFO 큐를 사용하여 간단하게 구현 가능

• 예시1. P1, P2, P3 순서로 프로세스가 생성(도착, arrive)되었을 때:

  

• 대기 시간 : P1 = 0, P2 = 24, P3 = 27

• 평균 대기 시간 : (0 + 24 + 27) / 3 = 17

• 예시2. P2, P3, P1 순서로 도착:

  

  • 대기 시간: P1 = 6, P2 = 0, P3 = 3
  • 평균 대기 시간: (6+0+3)/3 = 3
  • 예시1보다 짧은 대기 시간을 가짐

• 작업의 arrival(수행) 순서에 따라 대기 시간이 변할 수 있음

  • 짧은 프로세스가 긴 프로세스 뒤에 있을 때 문제, Convoy effect

Shortest Job First Scheduling

• Idea: 프로세스의 CPU-burst 구간 길이를 고려
• 실행해야할 프로세스들이 주어져 있을 때, 평균 대기시간 측면 가장 우수

평균 대기 시간 = (0 + 3 + 6 + 7) / 4 = 4

Shortest Remaining Time First (SRTF)

• 선점형으로 SJF 알고리즘을 구현

  • 목적: job은 동적으로 생성되고 도착함
  • 새로운 job이 도착하면 job의 잔여 CPU-burst 구간의 길이 확인
  • SJF + arrival time + preemption

• 평균 대기 시간 = (9 + 1 + 0 + 2) / 4 = 3

Problem of SJF and SRTF

• 평균 대기시간 측면에서 우수
• 문제점 : CPU-burst 구간의 길이를 사전에 알기 어려움
• 방안
  • 과거의 기록 활용
  • 모델링 또는 추론