지우너

[정보처리기사 실기/계산식] CPU 스케줄링 본문

Records/정보처리기사

[정보처리기사 실기/계산식] CPU 스케줄링

지옹 2024. 10. 15. 10:44

관련 강의

[이론 강의]: [Q&A] 운영체제 | 프로세스 스케줄링

[계산식 강의]: [Q&A] 프로세스 스케줄링 | SRT

[계산식 강의]: [정보처리특강] 프로세스 스케줄링 - 라운드 로빈(Round Robin)

[계산식 강의]: [Q&A] 운영체제 | RR 스케줄링(1)

[계산식 강의]: [Q&A] 운영체제 | RR 프로세스 스케줄링(2)

FIFO, SJF, HRN은 필기 특강 밖에 없음. 이론만 알면 비교적 쉽게 적용 가능

 

빨간색은 계산식에 나올 수 있음

선점형(=뺏을게) RR(Round Robin), SRT(Shortest Remaining Time), MLQ, MLFQ
비선점형(=못 뺏음) FCFS(=FIFO), SJF(=Shortest Job First), HRN(Hightest Response-ratio Next), 우선순위, 기한부

 

기아현상(오래동안 프로세스가 할당 받지 못하는 현상)을 해결하기 위헤 에이징 기법을 도입한 방법

: MLFQ, HRN

 

선점형

RR(Round Robin)

시간 할당량 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU 양보

시간 할당량(=할당되는 시간)이 클 경우 FCFS 기법과 같아지고,

시간 할당량이 작을 경우 문맥 교환 및 오버헤드가 자주 발생

SRT(Shortest Remaining Time

(현재 실행중인 프로세스의 남은 시간)과 (준비상태 큐에 새로 도착한 프로세스의 실행 시간) 비교.

→ 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU 할당.

준비상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드 증가

MLQ(Multi Level Queue)

시스템 큐

실시간 큐

배치 큐

 

이런 식으로 여러 개의 큐를 만들어 놓음. 프로세스가 들어오면 어느 큐에 적합한지 판단.

시스템 큐에 있는 프로세스가 다 끝나야 실시간 큐에 있는 프로세스를 실행하고, 그 다음에 배치 큐에 있는 프로세스를 실행.

 

실시간 큐에 있는 프로세스를 실행하다가 시스템 큐에 프로세스가 들어오면 작업을 멈추고 시스템 큐의 프로세스를 먼저 실행.

MLFQ(Multi Level Feedback Queue)

A

B

C

 

큐를 여러 개 두고, A 큐에 들어있는 프로세스는 2초 실행, B큐에 들어있는 프로세스는 4초 실행, 마지막 C 큐에 들어있는 프로세스는 RR방식으로 실행.

 

프로세스 a가 들어오면 무조건 맨위에 있는 A 큐에 집어 넣음.

a를 2초 실행. a 프로세스의 작업이 끝나지 않았다면 B 큐로 넘김.

a를 4초 실행. a 프로세스의 작업이 끝나지 않았다면 C 큐로 넘김.

a의 작업이 끝날 때까지 RR방식(시간 할당량 동안만 실행후 양보 반복)으로 작업.

 

비선점형

FCFS(=FIFO)

준비 상태 큐에 도착한 순서대로 실행

SJF(=Shortest Job First)

준비 상태 큐에서 실행시간이 짧은 순서로 실행

HRN(Hightest Response-ratio Next)

"(대기시간+실행시간)/실행시간"이 큰 걸 우선으로 실행

 

!!! 계산식에 나올 수 있는 방식: RR, SRT, FCFS, SJF, HRN !!!

 

<문제 풀 때 알아야 함>

대기 시간: 대기한 시간

실행 시간: 실행한 시간

반환 시간: 대기시간 + 실행시간

 

Round Robin ★★★★★

반드시 준비 상태 큐를 그려서 관리할 것.

시간할당량이 5라고 가정했을 때 첫 프로세스의 작업이 끝났을 때(0에 들어왔다면 5), 준비 상태 큐에 누가 들어와 있을지 생각할 것.

 

 

SRT ★★★

작업이 들어오면 하던 작업을 멈추고 남은 시간 기준으로 짧은 거 실행.

 

 

HRN ★

비선점형. 우선순위 계산이 좀 귀찮음

 

SJF

비선점형. 하나 끝났을 때 준비 상태 큐에 있는 것 중 실행 시간이 가장 짧은 거 실행.

 

FIFO

비선점형. 그냥 들어온 순서대로 준비 상태 큐에 넣고 실행.