이전 발행글
2022.12.26 - [Operating System] - [운영체제] CPU 스케줄링 1 (CPU burst Time, Scheduler & Dispatcher)
[운영체제] CPU 스케줄링 1 (CPU burst Time, Scheduler & Dispatcher)
● CPU and I/O burst in program Excution 프로그램 실행이 되면 프로그램은 아래와 같은 Path를 실행한다. 프로세스는 CPU에서 기계어가 실행되는 상태와 I/O 작업을 하는 상태의 반복이다. 프로그램마다 다
rannnneey.tistory.com
[운영체제] CPU 스케줄링 2 (FCFS, SJF, SRTF, Round Robin, Multilevel Queue, Multilevel Feedback )
● Scheduling Algorithms 종류 FCFS (First-Come First-Served) SJF (Shortest-Job-First), SRTF (Shortest-Remaining-Time-First) Priority Scheduling RR (Round Robin, 라운드 로빈) Multilevel Queue Multilevel Feedback Queue 스케줄링 알고리즘은
rannnneey.tistory.com
● Multiple-Processor Scheduling
- Homogeneous Process
Queue에 프로세스들을 한 줄로 세우고 각 프로세서가 알아서 꺼내가게 하는 기법이다.
그러나 반드시 특정한 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.
- Load Sharing (Load Balancing)
특정 CPU만 일하고 나머지 CPU가 놀고 있으면 안 되고 여러 CPU가 골고루 일을 할 수 있도록 해야 한다.
즉, 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요하다. 별개의 Queue를 두는 방법과 공동 Queue를 사용하는 방법이 있다.
- Symmetric Multiprocessing(SMP)
모든 CPU가 대등하게 일을 하기 때문에 각 CPU가 알아서 스케줄링을 결정하도록 한다. 예를 들어, 큰 행렬의 곱셈과 과 같은 일을 할 때이다.
- Asymmertric Multiprocessing(ASMP)
CPU가 여러 개 있는데 그중에서 하나의 CPU가 전체적인 컨트롤을 담당한다. 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서들은 거기에 따라야 한다.
● Real-Time Scheduling
Deadine이 있어서 정해진 시간 안에 반드시 실행되어야 하는 스케줄링이다.
- Hard Real-time Systems
Hard Real Time System은 정해진 시간 안에 반드시 끝내도록 스케줄링을 해야 한다. Dead line을 어기면 큰 문제가 생기는 시스템이기 때문에 CPU의 용량 같은 정보들을 미리 맞춰 놓아야 한다. 따라서 보통 Hard Real-time은 그때그때 온라인으로 하는 것이 아니라 오프라인으로 사전에 어떤 프로세스들이 실행될지 미리 정하고 그대로 시스템이 따라가게 하는 경우가 많다. 지금까지 배웠던 Time Sharing OS에서는 온라인으로 스케줄링을 했던 것이다.
- Soft Real-time Systems
Dead Line을 넘겨도 큰 일까지는 나지 않는 시스템이다. 예를 들어 동영상 스트리밍 프로세스가 있다. Dead Line을 넘기면 불편하긴 하지만 문제가 되진 않는다. Soft time task는 일반 프로세스에 비해 높은 우선순위를 가진다. 우선순위만 높여줘서 CPU를 먼저 받을 수 있게 하지만 Dead Line을 반드시 지키지는 않는다.
● Thread Scheduling
하나의 프로세스 안에 CPU 수행 단위가 여러 개 있는 것으로 구현 방식은 두 종류이다.
- Local Scheduling
User Level Thread의 경우, 사용자 수준의 Thread Library에 의해 어떤 thread를 스케줄링할지 결정한다.
사용자 프로세스가 직접 Thread를 관리하며 운영체제 커널은 Thread의 존재를 알지 못한다.
- Global Scheduling
Kernel Level Thread인 경우, 일반 프로세스와 마찬가지로 Kernel의 단기 스케줄러가 어떤 Thread를 스케줄링할 것인지 결정한다.
운영체제가 Thread의 존재를 이미 알고 있다.
두 가지의 상황이 다르기 때문에 스케줄링하는 방법도 다르다.
User Level Thread의 경우 운영체제는 Thread를 모르기 때문에 운영체제는 해당 프로세스에게 CPU 제어권을 넘겨줄지 넘겨주지 않을지만 결정한다. 그러고 난 후, CPU 제어권이 넘어갔을 때 어떤 Thread에게 CPU를 줄 것인가는 프로세스 내부에서 결정한다. (Local 스케줄링. OS가 하는 게 아니라 사용자 프로세스가 결정!)
Kernel Level Thread의 경우에는 운영체제가 Thread의 존재를 알기 때문에 프로세스 스케줄링 하듯이 운영체제가 어떠한 알고리즘에 근거해서 어떤 스레드에게 CPU를 줄 건지를 결정한다. (Global 스케줄링)
● Algorithm 평가
알고리즘이 좋은지 평가하는 방법이 필요하다.
- Queueing models
확률 분포로 주어지는 Arrival rate와 Service rate를 통해 처리량, 대기 시간 등 각종 값을 계산하는 이론적인 방법이다.
- Implementation(구현) & Measurement (성능 측정)
실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해 성능을 측정하여 비교한다. CPU 알고리즘을 새로 하나 만들었을 경우, 그걸 평가하기 위해 실제 시스템에 구현해서 기존 스케줄러랑 비교하는 방법이다.
- Simulation (모의 실험)
알고리즘을 모의 프로그램으로 작성 후, trace(실제 값들을 진짜 프로세스가 동작할 때와 같은 값들로 집어넣는 작업)를 입력으로 하여 결과를 비교하는 방식이다.
