프로세스 스케줄링
1. 선점(Preemptive) 스케줄링
선점 스케줄링이란 우선순위가 높은 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유하는 스케줄링 기법
- 실행 중인 프로세스를 중단하고,더 우선순위가 높은 다른 프로세스에게 CPU를 양보
- 비교적 응답이 빠르다는 장점이 있으나, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드가 발생하게 된다.
- 선점 스케줄링의 예로는 RR, SRT, 다단계 큐, 다단계 피드백 큐가 있음.
📌 선점 스케줄링 알고리즘
🔹 Round Robin : 시간 할당량(Time Quantum) 지나면 다음 프로세스로 교체
🔹 SRTF (Shortest Remaining Time First) : 남은 시간이 더 짧은 새 작업이 오면 현재 작업 중단
🔹 선점형 우선순위(Priority Scheduling) : 더 높은 우선순위의 프로세스가 도착하면 중단됨
2. 비선점(Non-preemptive) 스케줄링
프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 기법
한 번 실행된 프로세스는 끝날 때까지 CPU를 점유한다. 그래서 새로 도착한 프로세스는 대기해야 한다.
중요한 작업이 길면, 뒤에 있는 짧은 작업이 오래 기다릴 수 있기 때문에 기아현상 발생 가능
📌 비선점 스케줄링 알고리즘
🔸 FCFS (First Come First Serve) : 먼저 도착한 순서대로 실행
🔸 SJF (Shortest Job First) : 실행시간이 짧은 것부터 실행
🔸 비선점 우선순위 스케줄링 : 우선순위 높은 순으로 실행, 중간 교체 없음
🔸 HRN (Highest Response Ratio Next) : 반응 비율 기반, 대기시간 고려
문제풀이
비선점은 들어온 순서대로 처리하니까 쉬움
선점형은 실행 도중에도 더 짧은 프로세스가 도착하면 현재 작업을 중단하고 짧은 걸 먼저 실행하므로실행 순서가 바뀜
1.FCFS
- 난이도 ⭐
- 도착한 순서대로 처리하면 됨
- 최소 평균 반환시간 t 는 실행시간이 짧은 것부터 실행 (P2 → P1 → P3)
- t = ( 0 + 3 + 12 ) / 3 = 15 / 3 = 5
- 최대 평균 반환시간 T 는 실행시간이 긴 것부터 나열 (P3 → P1 → P2)
- T = (0 + 12 + 21) / 3 = 33 / 3 = 11
- T - t = 11 - 5 = 6
2.SFJ
- 난이도 ⭐
- 실행시간 짧은 것부터 실행하면 됨
- 평균대기시간 / 평균반환시간 / 평균실행시간 중 무엇을 구해야 하는지 확인
프로세스 | 실행시간 | 대기시간 | 반환시간 |
P-2 | 3 | 0 | 3 |
P-1 | 6 | 3 | 9 |
P-4 | 7 | 9 | 16 |
P-3 | 8 | 16 | 24 |
|
| 28 / 4 = 7 | 52 / 4 = 13 |
Task | 도착시간 | 실행시간 | 대기시간 | 반환시간 |
Task1 | 0 | 6 | 0 | 6 |
Task2 | 1 | 3 | 6 | 9 |
Task3 | 2 | 2 | 9 | 2 |
합계 |
|
| 15 | 17 |
- Task2의 반환시간 = 2의 대기시간(Waiting Time) + 2의 실행시간(Burst Time) = 6 + 3 = 9
⭐ 도착시간이 0일 때 T1만 도착했기 때문에 T1가 실행시간이 길더라도 먼저 실행된다. (왜? 해당 시간에 도착한 작업이 T1뿐)
3.HRN
- 난이도 ⭐
- 비선점 스케줄링 알고리즘 중 하나로, 대기시간이 길어질수록 우선순위가 높아지는 방식
- 우선순위 = 1 + 대기시간/서비스 시간
- → 숫자가 클수록 우선순위가 높다!
✅ HRN 우선순위 계산식
- 대기시간 (Waiting Time) = 현재 시점 − 도착시간 − 아직 실행 안 된 경우
- 서비스시간 (Service Time) = 실행시간, 즉 Burst Time
- 짧은 작업(SJF)에게 유리하면서도,오래 기다린 작업도 점점 우선순위가 높아져 기아 현상(starvation) 방지 가능!
- A = 1 + (8 / 2) = 1 + 4 = 5
- B = 1 + (10 / 6) = 2.6666
- C = 1 + (15 / 7) = 3.14
- D = 1 + (20 / 8) = 3.5
- 우선 순위 큰 순서대로 A > D > C > B
4.SRT
- 난이도 ⭐⭐
- SRT(Shortest Remaining Time First)는 선점형 프로세스 스케줄링 알고리즘 방식
- 현재 실행 중인 프로세스보다 남은 실행시간이 더 짧은 새로운 프로세스가 도착하면 CPU를 양보하기
- 그래프 그리면서 풀기
- 반환시간 = 종료시간 - 도착시간
5.RR(Round Robin)
- 난이도 ⭐⭐⭐
- 타임 퀀텀 (Time Quantum) 이 주어짐
- 선입선출 (FIFO) 방식으로 할당시간(타임 퀀텀)만큼 실행 후 대기 큐로 이동
- 새로운 작업이 도착하면 도착 순서대로 대기 큐에 추가
- 할당 시간이 중요
- 대기큐 + 남은 시간 + 그래프 세 가지를 그리면서 풀어야 함
- 무조건 짧은게 우선이 아니라 큐에 들어간 순서대로 다시 실행되므로 만약 프로세스가 3개면 3개가 번갈아 가면서 실행됨
- 유형 : CPU 사용 순서 / 평균 대기시간 / 평균 반환시간 문제!
- ⭐ 대기 시간 (Waiting Time, WT) = 완료 시간 (FT) - 도착 시간 (AT) - 실행 시간 (BT)
- ⭐ 반환 시간 (Turnaround Time, TAT) = 완료 시간 (FT) - 도착 시간 (AT)
CPU 사용 순서 문제
라운드 로빈 방식에서 주의할 점
⭐ 남은 실행 시간만 보고 풀면 틀린다.
⭐ 대기큐를 그려야 한다.
라운드 로빈 (RR) 스케줄링을 풀 때 대기 큐의 순서를 반드시 고려해야 한다. 단순히 "남은 실행 시간"만 보고 짧은 작업을 먼저 실행하는 것이 아니라, 큐에 들어간 순서대로 작업이 실행된다.
타임 퀀텀(시간 할당)이 끝나면 무조건 대기 큐로 이동! → 대기 큐에 있는 순서대로 실행! → 남은 실행 시간이 짧아도 먼저 실행되지 않음 → 그래서 모든 작업이 번갈아가면서 실행됨
라운드 로빈에서는 남은 시간이 적은 작업이 있더라도 먼저 들어온 순서대로 실행된다. 즉, ABC 세 개의 작업이 남아 있다면, ABC 순서대로 계속 번갈아가면서 실행된다. 이걸 놓치면 잘못된 순서로 풀게 되어 답이 틀릴 수 있다.
이렇게 풀면 절대 틀리지 않는다.
평균 대기시간 문제
대기 시간 (Waiting Time, WT) = 완료 시간 (FT) - 도착 시간 (AT) - 실행 시간 (BT)
평균 반환시간 문제
반환 시간 (Turnaround Time, TAT) = 완료 시간 (FT) - 도착 시간 (AT)
- 이런 문제는 도착시간이 모두 0이라고 생각하고 푼다 (문제에 따로 명시되지 않았기 때문)
참고 자료
- 흥달쌤의 정보처리기사 계산식 특강
- https://buly.kr/8eljGok