Skip to content

Latest commit

 

History

History
219 lines (162 loc) · 11.1 KB

04-cpu-scheduling.md

File metadata and controls

219 lines (162 loc) · 11.1 KB
Raw

CPU 스케줄링

스케줄링 개념

CPU 스케줄링의 목적과 필요성에 대해 설명하세요.
  • 공정성: 모든 프로세스에게 공정하고 합리적으로 CPU 자원을 할당하기 위해
  • 자원 낭비 최소화: CPU가 쉬지 않고 사용되도록 하여 자원 낭비를 방지하기 위해
  • 멀티태스킹: 동시에 여러 프로세스를 실행하기 위해
  • 우선순위 관리: 높은 우선순위를 가진 프로세스가 먼저 실행되기 위해

중요한 사실
프로세스 자체는 운영체제의 스케줄러에 의해 직접 실행되지 않으며, 스레드가 실행됨

I/O bound, CPU bound 프로세스에 대해 설명하세요.

버스트(Burst)

  • CPU 버스트: 프로세스가 CPU를 연속적으로 사용하는 시간
  • I/O 버스트: 프로세스가 I/O 작업을 요청하고 완료될 때까지 기다리는 시간

I/O bound 프로세스

  • CPU 버스트보다 I/O 버스트가 많은 프로세스(e.g. 일반적인 백엔드 API 서버 프로그램 등)
  • I/O 요청 후 응답까지 기다리는 시간이 길기 때문에 CPU가 상대적으로 덜 사용됨
  • 따라서 I/O bound 프로세스의 상태는 실행보다 대기 상태에 더 오래 머무름

CPU bound 프로세스

  • I/O 버스트보다 CPU 버스트가 많은 프로세스(e.g. 동영상 편집 프로그램, 머신러닝 프로그램 등)
  • 따라서 CPU bound 프로세스의 상태는 대기보다 실행 상태에 더 오래 머무름

듀얼 코어 CPU에서 동작할 I/O bound, CPU bound 프로그램은 각각 몇 개의 쓰레드를 사용하는것이 적절할까요?

I/O bound 프로세스

  • 상황에 맞게 적절한 개수의 쓰레드를 사용해야함
  • 단, I/O 작업을 하는 동안 CPU가 대기하는 시간이 길어지므로 많은 수의 쓰레드를 사용하는 것이 일반적임

CPU bound 프로세스

  • 코어 개수와 비슷한 개수의 쓰레드를 사용하는 것이 좋음, 즉 2개 ~ 3개의 쓰레드를 사용하는 것이 적절함
  • 불필요하게 많은 개수의 쓰레드를 사용하면 컨텍스트 스위칭 오버헤드가 심해짐

프로세스 우선순위와 스케줄링 큐에 대해 설명하세요.

프로세스 우선순위

  • 운영체제는 프로세스가 중요도에 따라 실행될 수 있도록 우선순위를 부여하며, 각 프로세스의 우선순위 정보는 PCB에 저장됨

스케줄링 큐

  • 운영체제가 모든 PCB를 확인해 실행시킬 프로세스를 결정할 순 없으므로, 스케줄링 큐를 통해 프로세스 상태를 관리함
  • 준비 큐: CPU 사용을 기다리며 실행 준비가 완료된 프로세스들이 대기하는 큐
  • 대기 큐: I/O 작업 등 특정 이벤트가 완료되길 기다리는 프로세스들이 대기하는 큐

선점형과 비선점형 스케줄링에 대해 설명하세요.

선점형(Preemptive) 스케줄링

  • 운영체제가 실행중인 프로세스로부터 자원을 강제로 뺏어 다른 프로세스에 할당할 수 있는 스케줄링 방식
  • 자원을 공정하게 분배할 수 있지만 컨텍스트 스위칭 오버헤드 존재
  • 현재 대부분의 운영체제가 사용중인 방식

비선점형(Non-preemptive) 스케줄링

  • 운영체제가 실행중인 프로세스로부터 자원을 강제로 뺏을 수 없는 스케줄링 방식
  • 현재 실행중인 프로세스가 종료되거나 스스로 대기 상태가 되기 전까진 자원을 뺏을 수 없음
  • 컨텍스트 스위칭 오버헤드는 비교적 적지만, 자원을 공정하게 분배받지 못함

장기, 단기, 중기 스케줄러에 대해 설명하세요.

스케줄러

  • 실행될 프로세스를 선택하는 역할을 담당
  • 크게 장기, 중기, 단기 스케줄러가 있음

장기 스케줄러

  • 어떤 프로세스를 준비 큐로 보낼지 결정
  • 즉, 디스크의 프로그램 중 메모리로 올릴 프로그램을 결정하여 시스템에서 실행되는 프로세스의 수를 제어하기 위한 스케줄러
  • 어떤 프로그램을 실행할지는 사용자가 요청하고 장기 스케줄러는 사용자가 실행을 요청한 프로그램을 메모리에 올릴지 말지 결정, 현재 메모리를 사용할 수 없는 상태라면 장기 스케줄러는 프로세스를 준비 큐가 아닌 대기 큐에 넣을 수 있음

단기 스케줄러(CPU 스케줄러)

  • 준비 큐에 있는 프로세스 중 실행될 프로세스를 선택
  • CPU 할당을 최적화하기 위한 스케줄러, CPU 스케줄러라고도 부름
  • 아래의 '스케줄링 알고리즘' 파트는 단기 스케줄러에서 사용하는 알고리즘을 의미함

중기 스케줄러

  • 실행 중인 프로세스의 스와핑을 담당
  • 메모리 관리를 위한 스케줄러

디스패처에 대해 설명하세요.
  • 스케줄러가 선택한 프로세스를 CPU에서 실행할 수 있도록 하는 역할을 담당
  • 구체적으로 컨텍스트 스위칭, 유저 모드와 커널 모드간 전환 등을 담당
  • 하지만 일반적으로 스케줄러와 디스패처를 크게 구분하지 않음

스케줄링 알고리즘

FCFS(First Come First Served) 스케줄링에 대해 설명하세요.
  • 정의: 준비 큐에 삽입된 순서대로 프로세스를 실행하는 비선점형 스케줄링 알고리즘
  • 장점: 단순하고 구현이 용이함
  • 단점: CPU bound 프로세스가 있을 경우, 뒤에 있는 다른 프로세스들이 오랫동안 대기해야하는 문제 발생

호위 효과(Convoy effect)에 대해 설명하세요.
  • CPU bound 프로세스가 준비 큐의 앞에 있을 경우, 뒤에 있는 CPU 버스트가 짧은 프로세스들도 오랫동안 대기해야하는 문제
  • I/O bound 프로세스와 CPU bound 프로세스가 많이 섞여있는 환경일수록 문제가 커짐

SJF(Shortest Job First) 스케줄링에 대해 설명하세요.
  • 정의: CPU 버스트가 가장 짧은 프로세스부터 실행하는 비선점형 스케줄링 알고리즘
  • 장점: 효울적, convoy effect 해결
  • 단점: 실제 CPU 버스트 시간을 예측하기 어렵고, 기아(starvation) 현상이 발생할 수 있음

SRTF(Shortest Remaining Time First) 스케줄링에 대해 설명하세요.
  • 정의: CPU 버스트가 가장 짧은 프로세스부터 실행하는 선점형 스케줄링 알고리즘(SJF의 선점형 버전)
    • 즉, 현재 실행 중인 프로세스의 남은 CPU 버스트보다 다른 프로세스의 예상 CPU 버스트가 더 짧으면 현재 프로세스를 중단하고 다른 프로세스 실행
  • 장점: 효울적, convoy effect 해결
  • 단점: 기아(starvation) 현상이 발생할 수 있으며, 빈번한 컨텍스트 스위칭이 발생할 수 있음

RR(Round Robin) 스케줄링에 대해 설명하세요.
  • 정의: 준비 큐에 삽입된 순서대로 타임 슬라이스 만큼의 시간동안 번갈아가며 실행하는 선점형 스케줄링 알고리즘
    • 각 프로세스는 정해진 타임 슬라이스 동안 CPU를 사용하며, 완료되지 못한 경우 다시 준비 큐의 끝으로 이동
  • 타임 슬라이스: 각 프로세스가 CPU를 사용할 수 있는 정해진 시간

타임 슬라이스의 크기에 따른 트레이드오프를 설명하세요.
  • 타임 슬라이스의 크기가 너무 크면 FCFS 스케줄링과 크게 다를 바가 없어져 convoy effect 발생 가능
  • 타임 슬라이스의 크기가 너무 작으면 컨텍스트 스위칭 오버헤드 증가

우선순위 스케줄링에 대해 설명하세요.
  • 정의: 우선순위가 높은 프로세스부터 실행하는 스케줄링 방식
  • SJF, SRTF도 CPU 버스트 시간을 우선순위로 취급하므로 넓은 의미에서 우선순위 스케줄링이라 할 수 있음
  • 단점: 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스에 밀려 계속해서 CPU를 할당받지 못하는 기아(starvation) 현상 발생 가능

기아(Starvation) 현상과 그 해결법에 대해 설명하세요.
  • 정의: 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스에 밀려 계속해서 CPU를 할당받지 못하는 현상
  • 해결법: 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여주는 에이징(Aging) 기법을 사용해 해결

Multilevel queue 스케줄링에 대해 설명하세요.
  • 정의: 우선순위나 특성에 따라 여러 준비 큐를 사용하는 스케줄링
  • 높은 우선순위의 큐에 있는 프로세스들을 먼저 전부 처리한 다음 낮은 우선순위의 큐에 있는 프로세스를 처리함
  • 각 큐는 별도의 스케줄링 알고리즘을 사용할 수 있음
  • 마찬가지로 기아 현상 발생 가능

image

Multilevel feedback queue 스케줄링에 대해 설명하세요.

개념

  • Multilevel queue 스케줄링의 발전된 형태
  • Multilevel queue 스케줄링에서는 프로세스들의 큐 간 이동이 불가해 기아 현상이 발생할 수 있는데, Multilevel feedback queue 스케줄링에서는 프로세스가 큐 사이를 이동할 수 있어 기아 현상이 발생하지 않음
  • 가장 일반적으로 사용하는 CPU 스케줄링 알고리즘

작동방식

  1. 새로 준비 상태가 된 프로세스는 가장 높은 우선순위의 큐에 삽입
  2. 삽입된 프로세스가 해당 큐에서 실행이 완료되지 않으면 다음 우선순위의 큐에 삽입 (반복)
  3. 낮은 우선순위가 되어 오랫동안 실행되지 못한 경우 다시 우선순위가 높은 큐로 이동시키는 에이징 기법 적용
결론
  • 결국 CPU bound 프로세스의 우선순위는 점점 낮아지며, I/O bound 프로세스는 빠르게 실행될 수 있음

다음 상황에 사용하면 적절한 스케줄링 알고리즘에 대해 설명하세요.

짧은 응답 시간이 중요한 경우
  • RR 등

준비 큐에 CPU bound, I/O bound이 반반 섞인 경우
  • SJF, SRTF 등
  • 이유: I/O bound 프로세스를 먼저 실행해야 하므로

준비 큐에 CPU bound 작업이 많은 경우
  • FCFS, 우선순위 스케줄링 등
  • 이유: 컨텍스트 스위칭 오버헤드를 줄일 수 있으므로