OS study

scheduling

  • FIFO: 먼저 들어온 순서대로 큐에 있는 거 뽑아서 실행:
  • SJF: 먼저 끝나는 작업 부터 실행
  • STCF: 남은 실행시간이 가장 짧은 프로세스부터 먼저 처리
  • RR(Round Robin): 일정 시간별로 돌아가면서 실행하는 것

STCF

job 들어오면 인터럽트 걸리고 wait 되어서 평가하고 새로운거 시작하거나 이전꺼 하거나 그래서 새로 들어오는 시점에 재평가됨

프로세스 상태 전이도 (Process State Transition)

stateDiagram-v2
    new --> ready : admitted (3)
    ready --> running : scheduler dispatch (0)
    running --> ready : interrupt (2)
    running --> blocked : I/O or event wait (1)
    blocked --> ready : I/O or event completion (3)
    running --> terminated : exit (4)
  • (0) ready →\rightarrow running: 스케줄러에 의해 CPU를 할당받음 (scheduler dispatch)
  • (1) running →\rightarrow blocked: I/O 요청이나 특정 이벤트 대기 (I/O or event wait)
  • (2) running →\rightarrow ready: 할당된 시간 초과 또는 다른 이유로 CPU 반납 (interrupt)
  • (3) new →\rightarrow ready: 프로세스가 생성되어 준비 큐에 진입 (admitted)
  • (3) blocked →\rightarrow ready: 대기 중이던 I/O나 이벤트가 완료되어 다시 준비 상태로 복귀 (I/O or event completion)
  • (4) running →\rightarrow terminated: 프로세스 실행이 완료되어 종료됨 (exit)

Priority Scheduling

MLFQ(Multi-Level Feedback Queue)는 여러 개의 큐를 사용하고, 각 큐마다 다른 우선순위와 time slice를 가진다.

interactive 한 job은 time slice를 짧게 해서 빠르게 응답하고, batch 한 job은 time slice를 길게 해서 효율적으로 처리할 것이다.

그래서 cpu를 조금 쓰고 I/O를 많이 쓰는 job은 우선순위 올려주고, cpu를 많이 쓰는 job은 우선순위 내린다.

RULE:

  1. If priority(A) > priority(B), run A (even if B is already running)
  2. If priority(A) = priority(B), run A (round-robin)
  3. When a job enters the system, it enters the highest priority queue
  4. If a job uses up an entire time slice while running, its priority is reduced (i.e., it moves down on queue). →\rightarrow Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down on queue)
  5. If a job voluntarily gives up the CPU (e.g., by performing I/O) before the time slice expires, it stays at the same priority level →\rightarrow After some time period S, move all the jobs in the system to the topmost queue

우선순위를 주었을 때 제일 중요한 건 기아상태에 빠지지 않게 해야함.

Priority Inversion

lock 한 상태의 우선순위 low 작업때문에 high 작업이 unlock 기다리는데 medium이 같은 자원 안쓰는 프로세스라면 high 작업이 medium 때문에 기다리는 문제 발생.

Solution

같은 자원을 쓰는 프로세스라면 우선순위를 높여서 해결.

[기본 우선순위 가정] L(2) < M(4) < H(8)

예시 1: 단일 락 (Single Lock)

  • L이 락 점유.
  • M이 대기 →\rightarrow L의 우선순위를 4로 상향.
  • H가 대기 →\rightarrow L의 우선순위를 8로 추가 상향.

예시 2: 다중 락 (Multiple Locks)

  • L은 락1, M은 락2 점유.
  • M이 락1 대기 →\rightarrow L 우선순위 4로 상향.
  • H가 앞서 M이 점유 중인 락2 대기 →\rightarrow M 우선순위 8로 상향.
  • 연쇄 작용 →\rightarrow M이 대기하는 락1의 소유자 L의 우선순위도 8로 연쇄 상향됨.