퇴근 후 운영체제 시리즈 - CPU 스케줄링

in Studying CS Basic
퇴근 후 운영체제 시리즈 - CPU 스케줄링

운영체제 스터디 기록

해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다

은행 업무에 적응을 많이 하고 있다. 아직까지는 시재 실수는 하지 않았지만 정신 똑바로 차리자!! 이번 스케줄링 부분에서도 정신을 똑바로 차리고 한 번 보도록 하자. PS. 반효경 교수님의 강의력이 정말,,, 귀에 쏙쏙 들어온다. 이 글을 읽고 계시는 분이 있다면 꼭 한번 듣는 것을 추천한다.

스케쥴러

Long Term scheduler

장기 or job 스케쥴러

✓ 시작 프로세스 중 어떤 것들을 ready queue 로 보낼지 결정

✓ 프로세스에 메모리 및 각종 자원을 주는 문제

✓ degree of multi-programming 을 제어 → 메모리에 올라간 프로그램이 몇개냐?

✓ time sharing system 에는 보통 장기 스케줄러가 없음 (무조건 ready)

우리가 쓰는 건 바로 ready 큐

Short Term scheduler

단기 or CPU 스케줄러

✓ 어떤 프로세스를 다음번에 running 시킬지 결정

✓ 프로세스에 cpu를 주는 문제

✓ 충분히 빨라야 함 (ms 단위)

Medium term scheduler

중기 스케쥴러 or swapper(당장 필요한 프로세스에게만 주자)

✓ 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 → Suspended 상태

✓ 프로세스에게서 memory를 뺏는 문제

범용 컴터에는 장기 스케줄러 없기에 중기 스케줄러가 이를 처리

✓ degree of multi-programming 제어

CPU & I/O 버스트

image

image

  • CPU burst 와 I/O burst 를 반복하는 것이 프로세스의 순리
  • 다만 CPU burst를 오래 쓰냐 I/O burst 를 오래 쓰냐는 프로세스 차이
  • CPU 를 짧게 쓴다 → I/O bound job
  • CPU를 길게 쓴다 → CPU bound job

⇒ 이런 경우에는 누구에게 CPU를 주는게 이득일까? → 이를 해결하기 위해 CPU 스케쥴링 필요함

💡 여러 종류의 JOB 이 섞여 있기 때문에 CPU 스케줄링이 필요하다

  • Interactive job 에게 적절한 response 제공 요망
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

CPU Scheduler & Dispatcher

CPU Scheduler

Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.

현대의 운영체제 스케줄링은 커널 수준 스레드 를 스케줄하지만 프로세스 스케줄링도 상호 교환적으로 사용

Dispatcher

✓ CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘긴다.

✓ 이 과정을 context switch 라고 하고 모든 context switch 에서 디스패처가 호출됨 → 빨리 처리되어야 됨

✓ 사용자 모드로 전환하는 일 담당

✓ 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

CPU 스케줄링 필요한 경우

프로세스에게 다음과 같은 상태 변화가 있는 경우

  1. Running → blocked (ex. I/O 요청하는 시스템 콜) 비선점형
  2. Running → Ready (ex. 타이머 인터럽트) 선점형
  3. Blocked → Ready (ex. I/O 완료 후 인터럽트) 선점형
  4. Terminate 비선점형

스케줄링 알고리즘 ⭐️

FCFS (First Come First Served)

image

image

  • 비선점 방식
  • 순서는 보존하지만 효율은 낮아짐

  • 긴 작업 하나 때문에 나머지 작은 작업들이 기다리는 것을 → Convoy Effect (호위 효과)

  • 반대로 들어왔다면 어떨까?
    • 최저의 대기시간

Shortest Job First

💡 CPU burst time 이 가장 짧은 프로세스를 제일 먼저 스케줄

대기시간 Optimal

비선점방식

CPU를 잡으면 이번 CPU burst가 완료될 때까지 선점 당하지 않음

선점 방식 (Optimal)

  • 현재 수행 중인 프로세스의 남은 cpu burst time 보다 더 짧은 CPU burst time 을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  • aka Shortest-Remaining-Time-First

SJF 단점

기아 문제

→ CPU burst 가 길다라는 이유로 아예 CPU 에 배정받지 못하는 일이 생김

다음 CPU burst time 의 예측

다음번 CPU burst 시간을 어떻게 알 수 있는가?

→ 추정만이 가능함

과거의 CPU burst time 을 이용해서 추정 (지수 평균을 이용한다)

우선순위 스케줄링

💡 높은 우선순위를 가진 프로세스 먼저 CPU를 할당하겠다.

선점, 비선점으로 구현이 가능하다.

SJF는 일종의 우선순위 스케줄링이다

기아 문제 해결책 → Aging

시간이 흐를수록 남아있는 프로세스들의 우선순위를 높이는 방법

Round Robin (현대 운영체제)

💡 각 프로세스는 동일한 크기의 할당 시간을 부여하는 것 (일반적으로 10~100 ms)

✓ 할당 시간이 지나면 프로세스는 선점 당하고 ready queue append

✓ n개의 프로세스가 ready queue 에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 cpu 시간의 1/n을 얻는다 → 어떤 프로세스도 (n-1)*q time unit 이상 기다리지 않는다.

**성능**

  • q large → FCFS
  • q small → context switch 오버헤드가 커지게 된다.

Multi-Level Queue

🎙️ Ready Queue 를 여러 개로 분할

✔︎ foreground (interactive)

✔︎ background (batch - no human interaction)

image

→ 큐끼리 따로 상호 작용이 없고 한번 배정되면 그 큐에서 처리될 때까지 기다려야 하는 것

⇒ Starvation 문제가 존재

각 큐는 독립적인 스케줄링 알고리즘을 가짐

✔︎ Fore ground : Round Robin

✔︎ background : FCFS

큐에 대한 스케줄링이 필요

✔︎ Fixed priority scheduling

  • foreground 먼저 처리한 후 백그라운드 처리
  • 이럴 때는 기아 문제 발생할 수 잇음

✔︎ Time Slice

  • 각 큐에 CPU 시간을 적절한 비율로 배분
  • ex) 80% foreground RR , 20% background fcfs

Multi-Level Feedback Queue

🎙️ 프로세스가 다른 큐로 이동 가능!

image

일단 제일 높은 우선순위 큐에 넣고 시간 안에 처리가 안된다면 후속 큐로 넣어준다

위에는 짧은 Time slice 를 가진 RR / 2배 RR

  • 에이징을 이와 같은 방식으로 구현할 수 잇음
  • Multi-Level feedback Queue 스케줄러를 정의하는 파라미터
    • Queue의 수
    • 각 큐의 스케줄링 알고리즘
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 내쫓는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

⇒ 현대의 운영체제는 단순히 RR만 쓰지 않고 이렇게 다중 큐로 구성을 해서 처리함

Why?

짧은 I/O 바운드를 빠르게 처리하고자!

Multi-processor scheduling

이전까지 봣던 내용들은 CPU가 1개일 때를 가정하고 살펴본 스케줄링 기법들임. CPU가 늘어날수록 스케줄링 알고리즘은 더욱 복잡해짐

Homogeneous processor

✔︎ Queue 에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음

✔︎ 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡

Load sharing (Load Balancing)

✔︎ 일부 프로세서에 job이 물리지 않도록 부하를 적절히 공유하는 메커니즘 필요

✔︎ 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법

Symmetric Multiprocessing(SMP)

여러 CPU가 모두 대등한 위치를 가짐

✔︎ 각 프로세서가 각자 알아서 스케줄링 결정

Asymmetric multiprocessing

한 개의 CPU가 리더 CPU가 되고 해당 CPU의 명령을 따름

✔︎ 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

Thread Scheduling ⭐️

⛸️ 대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드임

  • 사용자 수준의 스레드는 스레드 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못함
  • 결국 사용자 스레드는 커널 스레드에 사상이 되어야함

Algorithm Evaluation

Queueing models

🎙️ 확률 분포로 주어지는 arrival rate 와 service rate 등을 통해 각종 performance index 값을 계산

image

Implementation & Mesasurement (현대)

🥏 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교

Simulation

🎠 모의 프로그램을 작성 후 trace를 입력으로 하여 결과 비교

연습 문제

선점 스케줄링과 비선점 스케줄링의 차이


선점 스케줄링과 비선점 스케줄링의 차이점
선점 스케줄링과 비선점 스케줄링은 모두 프로세스 스케줄링 알고리즘이지만,
 작업 중간에 다른 프로세스가 CPU를 빼앗을 수 있는지 여부에서 차이가 있습니다.

1. 선점 스케줄링:

작업 중간에 다른 프로세스가 CPU를 빼앗을 수 있습니다.
우선 순위가 높은 프로세스가 CPU를 더 많이 사용할 수 있도록 합니다.
응답 시간이 빠르지만, 오버헤드가 발생할 수 있습니다.
예시: 라운드 로빈 스케줄링, 우선 순위 기반 스케줄링

2. 비선점 스케줄링:

작업이 종료될 때까지 다른 프로세스가 CPU를 빼앗을 수 없습니다.
모든 프로세스가 공정하게 CPU를 사용할 수 있도록 합니다.
응답 시간이 느리지만, 오버헤드가 적습니다.
예시: FCFS(First Come First Served) 스케줄링

선택 가이드:

응답 시간이 중요한 경우: 선점 스케줄링
공정성이 중요한 경우: 비선점 스케줄링
시스템의 특성과 요구 사항에 따라 적절한 알고리즘 선택