Disk Scheduling

Disk Scheduling

 

디스크 스케쥴링을 학습하기 전 알아두면 좋은 것들은 다음과 같습니다.

 

1. 디스크 구조와 동작 원리
   
   
   • 디스크 스케쥴링을 이해하기 위해서는 디스크의 구조와 동작 원리에 대해 이해해야 합니다.
     디스크는 여러 개의 원판으로 구성되어 있으며, 각 원판은 다양한 위치에 트랙(track)이라 불리는
     원형의 경로를 가지고 있습니다. 트랙은 다시 여러 개의 섹터(sector)로 구성되어 있으며,
     각 섹터에는 데이터가 저장됩니다. 이러한 디스크의 구조와 동작 원리를 이해해야 디스크 스케줄링을
     효율적으로 수행할 수 있습니다.
     
     
2. 디스크 스케줄링 알고리즘의 종류와 특징
   
   
   • 디스크 스케줄링에는 여러 가지 알고리즘이 있습니다.
     각 알고리즘은 디스크의 입출력(I/O) 요청을 처리하는 방식에 따라 다릅니다.
     대표적인 디스크 스케줄링 알고리즘으로 FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK 등이 있습니다.
     이러한 알고리즘들의 특징과 장단점을 이해하면 어떤 알고리즘이 어떤 상황에서 효과적인지 판단할 수 있습니다.
     
     
3. 디스크 스케줄링의 성능 측정 기준
   
   
   • 디스크 스케줄링의 성능을 측정할 때는 평균 응답시간, 평균 대기 시간, 평균 서비스 시간, 입 출력 요청 대기 시간 등의 지표를 사용합니다. 이러한 지표들은 디스크 스케줄링 알고리즘의 성능을 평가하고 비교하는데 도움을 줍니다.
     
     

---

디스크의 구조와 동작 원리

 

디스크는 컴퓨터에서 데이터를 저장하는 데 사용되는 주요한 보조 저장 장치입니다.
일반적으로 회전하는 원판인 플래터 위에 자성 매체로 이루어진 트랙이 있으며 각 트랙은 섹터로 나누어져 있습니다.
디스크는 읽기/쓰기 헤드로부터 전기 신호를 통해 데이터를 읽거나 쓰게 됩니다.

 

디스크는 선형적인 데이터 접근 방식을 사용합니다.

읽거나 쓰려는 데이터의 위치를 찾기 위해 디스크 헤드가 디스크를 이동합니다.

이 때 디스크 헤드는 디스크 표면과 매우 가까이 위치하며 디스크의 회전과 함께 데이터를 읽거나 씁니다.

디스크는 빠른 속도로 회전하기 때문에 데이터 접근 시간은 디스크 헤드의 이동 시간과 회전 지연 시간으로 결정됩니다.

 

데이터는 디스크에 연속적으로 저장되지 않고, 조각으로 나누어져 있습니다.

이러한 조각들은 서로 다른 위치에 저장되어 있기 때문에, 디스크 헤드가 이동해야 하는 거리가 길어져서

데이터 접근 시간이 증가할 수 있습니다. 이러한 이유로 디스크 스케줄링은 효율적인 디스크 액세스를 위해 중요합니다.

 

아래는 디스크 작동원리를 설명해주는 영상입니다.

이 영상에서는 디스크의 내부 구조와 디스크 헤드의 작동 원리 및 회전속도에 따라 시각적인 이해를 구할 수 있습니다.

 

How a Hard Drive works in Slow Motion - The Slow Mo Guys

 

---

디스크 스케줄링 알고리즘의 종류와 특징

 

디스크 스케줄링 알고리즘은 디스크에 요청된 여러 작업들 중에서 어떤 순서로 처리할지를 결정하는 방법입니다.

다양한 디스크 스케줄링 알고리즘이 개발되었는데, 각각의 알고리즘은 다양한 특징을 가지고 있습니다.

다음은 디스크 스케줄링 알고리즘의 종류와 각 특징입니다.

 

1. FCFS(First-Come, First-Served)
   
   
   • 먼저 들어온 요청 작업부터 순서대로 처리하는 알고리즘
   • 간단하고 구현이 쉬우며 공정한 방법이라는 장점이 있음
   • 그러나 선입선처리 방식에 따라 평균 응답 시간 및 평균 대기 시간을 증가 시켜 비용이 많이 발생 될 수 있음
   
   

   Input:
   Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
   Initial head position = 50
   
   Output:
   Total number of seek operations = 510
   Seek Sequence is
   176
   79
   34
   60
   92
   11
   41
   114

   
   
    
2. SSTF(Shortest Seek Time First)
   
   
   • 현재 헤드 위치에서 가장 가까운 트랙의 요청 작업을 우선 처리하는 알고리즘
   • FCFS에 비해 대기시간이 적게 소요됨
   • 그러나 헤드가 가장 가까운 작업만을 처리하다보니 멀리 떨어진 작업(안쪽 및 바깥쪽)에 있는 요청된 작업들은
     오랜 시간 동안 처리되지 않아 starvation 문제가 발생할 수 있음
   • 반면 트랙을 찾는 시간을 최소화 할 수 있으며 처리량을 극대화 할 수 있음
   
   

   Suppose ther order to request is - (80, 170, 43, 140, 24, 16, 190)
   And current position of Read/Write head is : 50

   
   
    
3. SCAN
   
   
   • 디스크 헤드의 진행방향에 있는 요청을 처리하고 다시 반대방향으로 틀어 반대 방향에 있는 요청들을 처리
   • 헤드가 한쪽 끝에서 다른 한쪽 끝까지 이동하면서 요청 작업을 처리하여 Elevator 기법이라고도 불림
   • 빠른 응답시간으로 편차를 줄일 수 있으며 starvation 을 방지할 수 있는 특징을 가짐
     
     

   Suppose the request to be addressed are - 82, 170, 43, 140, 24, 16, 190.
   ANd the Read/Write arm is at 50.
   
   , and it is also given that the disk arm should move "towards the lager value"

   
   
    
4. C-SCAN (Circular SCAN)
   
   
   • SCAN 알고리즘과 유사하지만, 디스크의 한쪽 끝에서 작업을 처리한 후,반대쪽 끝으로 이동하여 작업을
     처리하는 것이 아니라 작업을 처리한 후, 다시 시작점으로 돌아와 작업을 처리
   • 조금 더 시간을 균등하게 배분할 수 있으며 진행되는 과정에서 요청이 들어오면 해당 요청은 미처리
   • 응답 시간의 편차가 매우 적어 SCAN 보다 시간 균등성이 좋음
   • 디스크 안쪽 및 바깥쪽에 처리할 요청 작업이 없어도 끝까지 이동하기 때문에 비효율적
     
     

   Suppose the requests to be addressed are - 82, 170, 43, 140, 24, 16, 190.
   And the Read/Write arm is at 50
   
   , and it is also given that the disk arm should move "towards the larger value".

   
   
    
5. LOOK
   
   
   • 진행 방향의 마지막 요청을 처리한 후 반대방향으로 처리하는 기법
   • 디스크 헤드의 현재 위치에서 가장 가까운 요청을 처리하고 그 후 다시 반대방향으로 디스크 헤드를
     이동시켜 다음 가장 가까운 요청을 처리하는 방식으로 동작하는 방식으로 이러한 디스크 헤드의
     이동 패턴이 좌우로 번갈아 가며 일어나는 것이 마치 '눈길을 이동시키는' 모습과 비슷하다고 생각하여
     LOOK 이라는 이름이 붙여지게 됨

 

Suppose the requests to be addressed are - 82, 170, 43, 140, 24, 16, 190.
And the Read/Write arm is at 50

, and it is also given that the disk arm should move "towards the larger value".

 

6. C-LOOK (Circular LOOK)

 

• 바깥에서 안쪽 방향의 모든 요청을 처리한 후 가장 바깥쪽으로 이동한 뒤 다시 안쪽 방향으로 이동하는 기법

 

Suppose the requests to be addressed are- 82, 170, 43, 140, 24, 16, 190.
And the Read/Write arm is at 50,

and it is also given that the disk arm should move "towards the lager value"

 

 

* Eschenbach (에션바흐) 기법

 

• 헤드가 진행하는 과정에서 각 실린더에 대해 디스크팩의 한 번의 회전 시간 동안만 입출력 요구들을
  처리하는 기법입니다. 즉, 한 회전 동안 서비스를 받지 못하는 요구들에 대한 처리는 다음으로 미루는 것입니다.
  이를 위해서는 한 실린더 내의 트랙이나 섹터들에 대한 요구들을 별도로 순서화하는 메커니즘이 필요합니다.
  결국, 탐구시간의 최적화와 회전 지연 시간의 최적화를 동시에 추구하는 기본적인 기법인 것입니다.

 

* N-STEP SCAN

 

• SCAN의 무한 대기 발생 가능성을 제거한 것으로 SCAN 보다 응답시간의 편차가 적고,
  SCAN과 같이 진행 방향상의 요청을 서비스하지만, 진행 중에 새로이 추가된 요청은 서비스하지 않고
  다음 진행시에 서비스하는 디스크 스케줄링 기법입니다.

---

디스크 스케줄링 성능 측정 기준

 

1. 평균 응답 시간 (Average Response Time)
   
   
   • 디스크 스케줄링 알고리즘의 핵심 목표 중 하나는 디스크 요청을 얼마나 빠르게 처리 할 수 있는지 입니다.
     평균 응답 시간은 디스크의 요청이 발생한 시점부터 해당 요청이 처리되어 결과를 돌려받는데까지
     걸리는 시간의 평균 값입니다. 이 값이 작을수록 디스크 스케줄링 알고리즘의 성능이 좋다고 볼 수 있습니다.
     
     
2. 평균 대기 시간 (Average Waiting TIme)
   
   
   • 평균 대기 시간은 요청이 발생한 시점부터 해당 요청이 처리되기까지 대기한 시간의 평균 값입니다.
     이 값이 작을수록 디스크 스케줄링 알고리즘의 성능이 좋다고 볼 수 있습니다.
     
     
3. 평균 서비스 시간 (Average Service Time)
   
   
   • 평균 서비스 시간은 디스크 요청이 처리되는 데 소요되는 시간의 평균 값입니다.
     이 값이 작을수록 디스크 스케줄링 알고리즘의 성능이 좋다고 볼 수 있습니다.
     
     
4. 처리량 (Thoroughput)
   
   
   • 처리량은 일정 시간 동안 처리된 디스크 요청의 수를 나타내는 지표입니다.
     이 값이 높을수록 디스크 스케줄링 알고리즘의 성능이 좋다고 볼 수 있습니다.
     
     

이러한 성능 측정 기준을 이용하여 여러 가지 디스크 스케줄링 알고리즘을 비교하고 분석할 수 있습니다.

다만, 이들 기준을 모두 고려하여 디스크 스케줄링 알고리즘의 성능을 측정하는 것은 쉽지 않기 때문에,
일반적으로는 이들 중 하나나 두가지 정도를 중심으로 분석하게 됩니다.

 

---

#Ref,

Disk Scheduling Algorithms - GeeksforGeeks