[OS] CPU 스케줄링 알고리즘

2d3k commented 1 year ago

1. CPU 스케줄링 알고리즘의 종류룰 나열하시오.

2. 해당 내용을 설명하시오

2d3k commented 1 year ago

CPU 스케줄링이란, 다중 프로그래밍을 가능하게 CPU 이용률을 극대화 하기 위한 기법으로, 어떤 프로세스에 CPU를 할당할지 결정하는 작업이다.

비선점 프로세스 스케줄링

선입 선처리 스케줄링 (FCFS) 먼저 자원 사용을 요청한 프로세스에게 자원을 할당해주는 방식
- 호위효과
  - 다른 프로레스들이 하나의 긴 프로세스가 CPU를 놓기를 기다리는 것
  - 선입선처리 스케줄링에서 발생
  - 낮은 CPU와 장치 사용률
- 문제점: 한 프로레스가 지나치게 오래동안 CPU를 점유하기 떄문에 큰 손해가 발생
최단 작업 우선 스케줄링 (SJF) 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 먼저 할당
- 문제점: 실행 전 Next CPU Burst의 길이를 예측하기 어렵다
- Next CPU Burst 예측: 길이의 근사값을 계산, 지수 평균 구하기 등

선점형 프로세스 스케줄링

최소 잔여 시간 우선 (STCF) 현재 작업 중인 프로세스를 중단시키고 최단 잔여시간 프로세스의 처리르 시작하는 방식
- 선점형 SJF
- 새로운 프로세스가 실행되고 있는 프로세스의 남은 시간보다 더 짧은 CPU Burst를 가지고 있으면 Context Switching 발생
라운드 로빈 스케줄링 (RR) 시분할 시스템을 위한 선점형 스케줄링 방식
- 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당

2d3k commented 1 year ago

CPU Burst: CPU 명령을 실행하는 것 I/O Burst: I/O를 요청한 다음 기다리는 시간

Context Switching 현재 진행하고 있는 Task의 상태를 저장하고 다음 징행할 Task의 상태 값을 읽어 적용하는 과정

비선점형 스케줄링: 프로세스가 종료되거나 자발적으로 중지될 때까지 계속 실행되도록 보장 선점형 스케줄링: 다른 프로세스가 실행중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.

hyeonayou commented 1 year ago

CPU 스케줄링이란? CPU 이용률을 극대화하기 위해서는 멀티프로그래밍(multiprogramming)이 필요하다. 하지만 만약 CPU core가 하나라면 한 번에 하나의 프로세스만 실행 가능할 것이다. 이때 필요한 것이 CPU 스케줄링이다. CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이라고 할 수 있다.

비선점형 스케줄링 프로세스가 CPU를 점유하고 있다면 이를 뺐을 수 없는 방식 [ FCFS (First Come First Served) 스케줄링 ] - 선점형 /비선점형이 있음 -> 가장 먼저 요청한 프로세스에 CPU를 할당해주는 방식이다. [ SJF(Shortest-Job-First) 스케줄링 ] -> CPU burst time의 길이를 고려해서 스케줄링을 결정한다. 실행되고 있는 프로세스는 끝까지 실행된다.

선점형 스케줄링 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺐을 수 있는 방식 [ SJF(Shortest-Job-First) 스케줄링 ] -> 선점형에서는 현재 실행되고 있는 프로세스의 남은 시간보다 도착한 다음 프로세스가 더 빨리 끝날 수 있는 프로세스라면 다음 프로세스를 실행하도록 바꾸게 된다. SRTF(Shortest Remaining Time First)라고도 부른다.

[ Round Robin(RR) 스케줄링 ] -> 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간 단위(time slice/quantum)로 CPU를 할당하는 방식 *time slice : 선점형 스케줄링에서 cpu를 점유하도록 허용된 시간

2d3k / CS-Study