Computer Science

[OS] CPU Scheduling

CPU Scheduling

= ready 상태의 프로세스 중에서 어떤 프로세스에게 cpu를 줄지 결정
- cpu burst : 프로세스가 CPU를 사용하여 실행되는 시간을 의미합니다.
- I/O burst : 프로세스가 I/O 작업을 수행하는 동안 CPU를 사용하지 않는 시간을 의미합니다.

스케줄링이 필요한 경우

1. IO 요청하는 시스템 콜
2. 할당 시간 만료 time interrupt
3. IO 요청 완료 후 인터럽트
4. 프로세스 종료돼서 다음 프로세스로 넘김

*preemptive : 강제로 빼앗음 (선점형)
*nonpreemptive : 강제로 빼앗지 않음 (비선점형)

dispatcher

cpu의 제어권을 스케줄러에 의해 선택된 프로세스에게 넘긴다.(context switch)

Scheduling Criteria(스케줄링 성능 척도)

1. 시스템 입장에서의 성능 척도(최대한 CPU의 일을 많이 시키는 것이 좋은 것)

CPU utilization(이용률) : CPU를 가능한 바쁘게 시켜라
Throughput (처리량) : 주어진 시간안에 얼마나 많은 일을 완료 했는지

2. 프로세스 입장에서의 성능 척도(시간을 얼마나 빨리 처리하는 지)

Turnaround time(소요시간, 반환 시간) : CPU를 쓰러 들어와서 다 쓰고 걸릴 때 까지의 시간
waiting time(대기 시간): CPU를 사용하기 위해 레디 큐에서 기다린 시간
(선점형에서는 cpu를 계속해서 뺏길 수도 있으므로 계속 생길 수 있음)
Response time(응답 시간): 레디 큐에 들어와서 처음으로 CPU를 얻기까지 걸린 시간

Scheduling Algorithms

-> CPU Scheduling을 위한 여러 방법들

1. FCFS(선입선출)

먼저 온 순서대로 처리
비선점형 스케줄링(먼저 온 순서대로 뺏기지 않고 처리)
CPU를 짧게 쓰는 프로세스들이 앞에 대기를 기다려야 함.

2. SJF(Shortest - Job- First)

각 프로세스와 다음번 CPU birst time을 가지고 스케줄링에 활용
가장 짧은 프로세스를 제일 먼저 스케쥴링
주어진 프로세스들에 대해 최소 평균 대기 시간을 보장 (Preemptive에 더 알맞음)
- Nonpreemptive(비선점형) : 일단 CPU를 잡으면 이번 CPU birst가 완료될 때까지 CPU를 뺏기지 않음
- Preemptive(선점형) : 현재 수행 중인 프로세스의 남은 birst time보다 더 짧은 CPU birst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
단점: CPU 사용시간이 긴 프로세스는 영원히 차례가 안 올수도 있음.. (starvation, 기아 현상)
CPu birst time을 정확히 모르는 경우가 많음. (과거에 얼마나 썼는지 추정을 통해 예측하 사용, 아때 과거의 결과보단 최신 결과를 더 많이 반영하여 추정 )

3. Priority Scheduling(우선순위 스케줄링)

highest priority(높은 우선순위)를 가진 프로세스에게 CPU를 할당
SJF와 같이 preemptive /nonpreemptive 두가지 경우 존재
SJF도 우선순위 스케줄링의 일종
단점: SJF와 같이 Starvation(기아 현상)
해결방법: Aging(노화): 아무리 긴 프로세스라도 오래 기다리면 우선순위를 높여주는 것

4. Round Robin(RR) - 현대적인 기법

각 프로세스는 동일한 크기의 할당 시간(Time Quantum)을 가짐 (일반적으로 10-100ms)
할당 시간이 지나면 프로세스는 선점당하고 Ready Queue 의 제일 뒤에 가서 다시 줄을 선다.
장점: 모든 프로세스들이 응답시간이 빨라짐(CPU를 최초로 얻기까지의 시간)
단점: 동일한 시간이 걸리는 프로세스들이 RR을 사용하면 모든 프로세스들이 동시에 빠져나가게 됨.
(그때그때 하나씩 빠져나가는 것이 더 효율적)
할당 시간이 큰 경우=> FCFS
할당 시간이 적은 경우 => context switch 오버헤드가 커진다.

5. Multilevel Queue (프로세스가 여러 줄로 cpu를 기다림)

Ready Queue를 여러개로 분할
- foreground
- background
각 큐는 독립적인 스케줄링 알고리즘을 가진다.
- foreground - RR
- background - FCFS
큐에 대한 스케줄링이 필요
- Fixed priority scheduling
  - 우선순위가 높은 곳에서부터 낮은 곳으로 cpu를 할당 받음
  - 우선순위가 낮은 프로세스들은 starvation 발생 가능성이 있다.
- Time slice
  - 각 큐에 CPU time을 적절한 비율로 할당
    (ex. foreground에 80%, background에 20%)

6. Multilevel Feedback Queue

프로세스가 다른 큐로 이동 가능
birst time이 짧은 프로세스에게 좋은 스케줄링 기법

처음 들어온 프로세스는 우선순위가 높은 큐(첫번 째)에 위치시킨다.

우선순위가 높을 수록 cpu 할당 시간은 짧다.

만약 들어온 프로세스의 birst time이 짧으면 첫번째 들어온 큐에서 완료하고 바로 빠져나간다.

birst time이 cpu 할당 시간보다 긴 경우 할당 시간이 끝나면 그 다음 우선순위 큐로 들어가고, 우선순위가 높은 큐에서의 작업이 완료되면 다음으로 처리한다. 이때 할당 시간은 첫번 째 큐에서의 할당 시간보다 길다.

이런식으로 할당 시간 안에 처리를 못한 프로세스는 그다음 세번 째 큐에서 대기하고 이때 할당 시간은 두번째 할당 시간보다 더 길다.

7. Multilple- Processor- Scheduling (CPU가 여러개 있는 스케줄링)

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
Load sharing
- 일부 프로세서에 job이 올리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

8. Real -Time Scheduling

=> cpu에서 deadline 안에 처리를 끝내는 게 우선

Hard real-time systems
- 정해진 시간 안에 반드시 끝내도록 스케줄링
Soft real-time computing
- 일반 프로세스에 비해 높은 priority를 갖도록 해야 한다.

9. Thread Scheduling

Local Scheduling
- 유저 레벨 쓰레드 경우 사용자 수준의 Thread library에 의해 어떤 thread를 스케줄링 할건지 결정
- 사용자 프로세스가 어느 쓰레드에게 스케줄할건지 결정
Global Scheduling
- 커널 레벨 쓰레드인 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄링 할건지 결정

Algorithm Evaluation (어떤 알고리즘이 좋은 지 평가)

1. Queueing models

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

2. Implementation(구현) & Measurement(성능 측정)

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

3. Simulation (모의 실험)

: 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교

**이 게시글은 이화여자대학교 반효경 교수님의 강의를 듣고 정리한 글입니다.

'Computer Science' 카테고리의 다른 글

[OS] System Structure & Program Execution , Process (0)	2023.10.07
[CS] 컴퓨터의 구성 (0)	2023.05.28

Contents

새소식

인기 검색어