///////
Search
2️⃣

연습문제 7 ~ 12

7. SJF 스케줄링 알고리즘의 단점으로 크기가 큰 작업이 계속 뒤로 밀리는 현상을 무엇이라 하는가?

SJF 스케줄링
•
준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당
•
비선점형 방식
•
FCFS 스케줄링의 콘보이 효과를 완화(시스템 효율성 증대)
도착 순서
도착 시간
작업 시간
P1
0
30
P2
3
18
P3
6
9
•
P1은 도착하자마자 실행되므로 대기 시간 0, 작업시간 30
•
P2. P3 중 P3가 작업 시간이 짧으므로 먼저 실행
•
P3의 대기시간(30-6)=24, 작업시간 9
•
P2는 대기시간(30+9-3)=36, 작업시간 18
•
P1, P2, P3의 평균 대기시간 = (0+24+36)/3 = 20
공평성을 위배하는 문제
•
P2가 P3보다 준비 큐에 먼저 도착하지만, 작업 시간이 길다는 이유로 가장 나중에 실행되었다.
P3와 같은 작업이 계속 준비 큐에 들어오면 P2의 작업이 계속 연기되는데, 이를 아사 현상이라고 한다.

8. 아사 현상을 해결하는 방법을 설명하시오.

9. 서비스를 받기 위해 대기한 시간과 CPU 사용 시간을 고려하여 우선순위를 정하는 스케줄링 알고리즘은 무엇인가?

•
에이징(나이 먹기)로 완화 가능
◦
프로세스가 양보할 수 있는 상한선을 정하는 방식
◦
프로세스가 자신의 순서를 양보할 횟수를 규정하는 것
◦
기준이 불명확함 → 한계
HRN 스케줄링
•
서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링 하는 방식
•
오로지 프로세스의 실행 시간이 판단기준인 SJF와 차별점
•
우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간
도착 순서
도착 시간
작업 시간
P1
0
30
P2
3
18
P3
6
9
•
먼저 P1이 30초 동안 실행
•
P2의 대기시간 27초, P3의 대기시간 24초
•
P2의 우선 순위 = (27+18) / 18 = 2.5
•
P3의 우선 순위 = (24+9) / 9 = 3.67
•
P3 먼저 실행 후 P2 실행
•
평균 대기 시간은 (0+24+36)/3 = 20초
HRN 스케줄링, 서비스를 받기 위해 기다린 시간과 CPU 사용시간을 고려하여 스케줄링
•
SJF와 비교하면 CPU를 할당받을 확률을 높일 수 있으나 여전히 공평성은 위배된다.

10. 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 다음 자기 차례가 올 때까지 기다리는 선점형 스케줄링 알고리즘 중 가장 단순한 것은 무엇인가?

라운드 로빈 방식
비선점형 알고리즘의 FCFS와 유사하지만, 프로세스마다 CPU를 사용할 수 있는 최대 시간(타임 슬라이스)가 존재하기 때문에 우선순위가 적용되지 않는다.
도착 순서
도착 시간
작업 시간
P1
0
30
P2
3
18
P3
6
9
•
타임 슬라이스(10초)
시간
프로세스
실행 시간
대기 시간
남은 작업시간
큐
0
P1
10
0
20
P2, P3
0+10 = 10
P2
10
10-3 = 7
8
P3, P1
10+10 = 20
P3
9
20-6 = 14
0
P1, P2
20+9 = 29
P1
10
10+9 = 19
10
P2
29+10 = 39
P2
8
9+10 = 19
0
P1
39+8 = 47
P1
10
8
0
X
•
총 대기 시간 = 0+7+14+19+19+8 = 67
•
평균 대기 시간 = 67 / 3 = 23.33

11. 타임 슬라이스의 크기와 문맥 교환의 관계를 설명하시오.

•
라운드 로빈 스케줄링과 FCFS 스케줄링의 평균 대기시간이 같다면 라운드 로빈 스케줄링이 더 비효율적인 알고리즘이다.
→ 선점형 방식에서는 문맥 교환 시간이 추가되기 때문
선점형 방식에서는 문맥 교환 시간이 추가 되기 때문에 평균 대기 시간이 동일할 때 더 비효율적이다.
타임 슬라이스가 작을 경우 문맥 교환이 너무 자주 일어나 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며, 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하는 문제가 발생한다.
타임 슬라이스가 큰 경우, 라운드 로빈 방식은 FCFS 스케줄링과 다를 바 없다. 따라서 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.

12. 기본적으로 라운드 로빈 방식을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남아있는 작업 시간이 가장 적은 것을 선택하는 스케줄링 알고리즘은 무엇인가?

SRT(Shortest Remaining Time) 스케줄링
SRT 스케줄링
•
SJF 스케줄링 + 라운드 로빈 스케줄링 → SJF의 선점형 버전
•
최소 잔류 시간 우선 스케줄링
•
기본적으로 라운드 로빈 스케줄링을 사용, CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스 선택
→ 라운드 로빈은 타임 슬라이스 동안 작업하지 못해 준비 큐의 맨 뒤로 가면 그 순서대로 CPU를 할당하지만, SRT는 남은 시간이 적은 프로세스에 CPU를 먼저 할당
도착 순서
도착 시간
작업 시간
P1
0
30
P2
3
18
P3
6
9
•
타임 슬라이스(10초)
시간
프로세스
실행 시간
대기 시간
남은 작업시간
0
P1
10
0
P2(18), P3(9)
0+10 = 10
P3
9
10-6 = 4
P1(20), P2(18)
10+9 = 19
P2
10
19-3 = 16
P1(20), P2(8)
19+10 = 29
P2
8
0
P1(20)
29+8 = 37
P1
10
9+10+8 = 27
P1(10)
37+10=47
P1
10
0
0
•
총 대기 시간 = 0+4+16+0+27+0 = 47
•
평균 대기 시간 = 47/3 = 15.66
•
SJF와 SRT의 평균 대기시간을 비교하면 SRT 스케줄링의 평균 대기 시간이 짧으나, 이것이 SRT 스케줄링이 좋은 알고리즘이라는 것은 아니다.
◦
남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와의 문맥 교환 시간도 추가
•
SRT 또한 종료 시간 예측이 어려우며, 아사 현상이 일어나기 때문에 잘 사용하지 않는다.
Made with