[운영체제 / 디스크 스케쥴링] SSTF 알고리즘 - 실제 상황에서의 사용

Question

안녕하세요, OS 공부중인 학생입니다.디스크 I/O 스케쥴링에 대해 공부하던 중 의문점이 생겨 글을 올립니다.시험 문제에 대한 질문이지만 실제 상황에선 알고리즘이 어떻게 사용되는지 궁금하여 질문드립니다. SSTF (Shortest Seek Time First) 알고리즘은 현재 head가 있는 위치에서 거리가 가장 작은 부분으로 이동하는 알고리즘으로 알고 있습니다. 하지만 대부분의 예시들은 다음과 같이:큐에 1, 5, 10, 2, 17, 8, 9 가 있을때, 1 - 2 - 5 - 8 - 9 - 10 - 17 의 순서로 이동모든 I/O request 가 이미 도착했음을 가정하고 스케쥴링을 하는데요. 만약에 request 가 시간마다 다르게 도착할 경우, 어떻게 되는지 헷갈려서 질문드립니다. 만약 1) 다음과 같이 i/o request가 도착하며 2) 각 request handling 이 1 시간 유닛 만큼 걸린다고 가정했을 때:TimeT0T1T1T1T2T2T3Req1926911174제가 생각한 handling sequence 는 다음과 같습니다: T0 - 19 (첫 request 부터 시작한다고 가정)T1 - 큐에 2, 6, 9. 19에서 9가 제일 가까우니 9.T2 - 큐에 2, 6, 11. 9에서 11이 제일 가까우니 11.T3 - 큐에 2, 4, 6. 11에서 6이 제일 가까우니 6.T4 - 큐에 2, 4. 더이상 추가 리퀘스트 없음. 6 에서 4가 제일 가까우니 4.T5 - 큐에 2. 마지막 2. 이 시퀀스가 SSTF 알고리즘에 부합하는 것이 많나요? (시험 문제이므로 이 시퀀스가 시험 답에는 더 가깝다고 생각됩니다) 하지만, 이런 시퀀스로 움직였을 때 총 이동 거리는 21이 됩니다. 하지만 T3 까지 기다렸다가 모든 request를 한방에 핸들하면:19 - 17 - 11 - 9 - 6 - 4 - 2 로, 총 이동 거리는 17로 더 짧습니다. 물론 handling time 은 10 time unit으로 두 배이지만, 어떤 시퀀스가 실제로 사용되는 SSTF 알고리즘에 조금 더 부합하는 것인지 궁금합니다. 감사합니다.

byeworld · Accepted Answer

설명하신 내용(큐에 1, 5, 10, 2, 17, 8, 9 가 있을때, 1 - 2 - 5 - 8 - 9 - 10 - 17 의 순서로 이동)은 Disk 스케쥴링의 Shortest Seek Time 이 아니라 프로세스 스케쥴링의 Shortest Remain이나 Shortest Process 로 보이구요.. 문의 하신 내용은 SSTF에 따르면 전자가 맞게 됩니다.후자에서 2를 기다리느니 2.를 먼저 처리하게 되면 어떻게 될까요? 그러면 얘기가 달라지죠.. SSTF는 탐색 시간의 최적을 의미하는 것이 아닌 FIFO보다 낫다는 의미밖에 없습니다. 같은 시점에 상당히 떨어진 두 개가 들어오고 계속해서 한쪽에 가까운 것이 큐에 들어오면 하나가 계속 대기해서 기아상태에 빠질 수 있습니다. 책에서 그런 설명이 있을 겁니다. SSTF는 (가까운데 것(Shortes Seek)을 먼저 하는게 FIFO보다 낫더라)라는 것뿐입니다. 추. T2에서 큐에 17 빠졌습니다.

[운영체제 / 디스크 스케쥴링] SSTF 알고리즘 - 실제 상황에서의 사용

1개의 답변

#scheduling 목록