[정보처리기사] 프로세스 스케줄링 헷갈리는거 오답정리

1. 선점(Preemptive) 스케줄링

실행 중인 프로세스를 중단하고,더 우선순위가 높은 다른 프로세스에게 CPU를 양보 가능. 

📌 선점 스케줄링 알고리즘
🔹 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. SJF 

• 난이도 ⭐
• 실행시간 짧은 것부터 실행하면 됨

프로세스	실행시간	대기시간	반환시간
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 (라운드로빈)

• 난이도 ⭐⭐⭐
• 타임 퀀텀 (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이라고 생각하고 푼다 (문제에 따로 명시되지 않았기 때문)