[운영체제] 디스크 스케쥴링

오늘은 디스크 스케쥴링에 대해서 다뤄봅니다.

 

   디스크

디스크는 우리가 생각하는 기본적인 cd도 디스크가 될 수 있지만 통상적으로는 hard disk에 쓰이는 disk들을 디스크라고 부릅니다. cd는 한쪽 면만을 사용해서 데이터를 저장하는 방식이라면 hard disk의 저장장치는 양면을 모두 저장공간으로 사용하죠.

 

우선 디스크의 구조에 대해서 알아봅시다.

 

 

디스크는 우측과 같은 구조로 이루어져있습니다.

 

하나의 띠가 track을 의미합니다. track은 바깥에서 안쪽으로 갈수록 idx가 증가합니다.

 

섹터는 디스크 제조사에서 설정한 데이터의 최소 저장 단위입니다. 섹터가 모여 track을 구성합니다.

 

하나의 disk당 20~1500개의 track을 가지게 됩니다.

 

 

 

디스크들이 모여 이러한 층을 통상 이룹니다. 실제 하드디스크를 까서 확인해봐도 이러한 여러 층들이 있음을 확인할 수 있습니다.

 

하나의 디스크당 양면에 데이터를 저장한다고 했으니, surface 즉, 데이터를 저장할 수 있는 표면은 2개입니다. 해당 그림의 surface는 총 6개가 되겠네요.

 

또한 cylinder는 하나의 하드디스크에서 같은 track을 갖는 데이터들의 집합을 의미합니다. surface 0부터 6까지의 track 1의 위치의 데이터들은 같은 cylinder에 속하게 되는 것입니다.

 

 

이제 disk arm 부분을 확인해봅시다. 디스크를 읽는 head와 각 head들을 연결해주는 disk arm이 있습니다. 이 head는 track의 가장 안쪽에서 바깥쪽으로 이동할 수 있습니다. 또한 disk는 360도 회전하기 때문에 disk의 head는 결국 원하는 데이터를 모두 읽어올 수 있게 되는 것입니다.

 

 

   디스크 스케쥴링

우리는 이전에 device에 대해서 다뤘습니다. 운영체제가 device들을 수행하는 과정은 기본적으로 선입선출 방식이 원칙입니다.

하지만 디스크는 다릅니다. 왜 그런 것일까요??

 

디바이스들이 들어오고 해당 장치에 대한 어떠한 동작을 수행하기 위해서는 그렇게 많은 시간이 소요되지 않습니다. 디스크를 기준으로 말이죠. 디스크는 데이터를 읽어옴에 있어서 상대적으로 긴 시간을 소요하게 됩니다. 따라서 디스크는 어떠한 방식으로 처리를 하게될지를 결정하는 것이 디스크 데이터를 읽어오는 시간 단축에 있어서 큰 영향을 미치게 됩니다.

 

 

우선, 디스크를 통해서 데이터를 읽어옴에 따라 어떤 시간이 소요되게 되는 것인지를 간단하게 알아봅시다.

 

1. Seek time

disk arm이 원하는 데이터의 track에 위치하기 위해 disk arm을 움직이는 데 소요되는 시간

 

2. Rotational delay

head가 원하는 데이터의 sector에 위치하기 위해 disk를 회전하는 시간

 

3. Data transfer time

head에서 데이터를 읽어와 본체에 데이터를 받아오는 시간

 

 

이 세가지 중에서 seek time이 데이터를 전송함에 있어 큰 부분을 차지합니다. 따라서 seek time을 줄이는 것이, disk의 data transfer time을 단축시키는데 필요한 것입니다.

 

그래서 seek time을 단축시키는 여러 방법들을 알아보겠습니다.

 

 

   FIFO(First In First Out)

기본적인 방식으로 선입선출이 원칙입니다. 먼저 들어온 데이터를 먼저 읽는 방식이죠.

하지만 이것은 너무 비효율적입니다. 최악의 경우 track의 가장 바깥에서 가장 안쪽으로 움직이는 작업을 계속 반복하게 될 수도 있으니 말이죠.

 

 

 

   SSTF(Shortest Seek Time First)

그래서 SSTF 방식이 도입되게 되었습니다. 현재 head가 위치해있는 track에서 가장 짧은 거리를 갖는 track의 데이터를 읽게되는 방식이죠.

같은 데이터로 실험해봐도, FIFO 방식보다 약 2배 가량 빨라졌음을 알 수 있습니다.

 

하지만 이 SSTF 방식에는 치명적인 단점이 있습니다. 우리가 이전에 다뤘던 starvation 현상이 일어날 수 있다는 것입니다.

 

만약 지금과 같이 데이터가 주어졌다면 찾아볼 수 없지만 만약 데이터가 극단적으로 0, 1, 2, 3, 199, 4, 3 이런 식으로 진행된다면 어떻게 될까요?? 계속해서 0과 가까운 track의 데이터만 가져오게 된다면 결국 199의 track에는 도달하지 못하게 됩니다.

 

즉, starvation이 발생하는 것이죠. 이러한 치명적인 단점 때문에 사실 이 방식은 현재 사용되지는 않습니다.

 

 

   SCAN(Elevator Algorithm)

시작점을 기준으로 증가 or 감소하면서 존재하는 모든 영역을 읽은 후, 가장 하단의 데이터를 읽었다면 다시 올라가면서 읽는 방식입니다.

마치 작동하는 방식이 엘레베이터 같아서 Elevator Algorithm이라고도 불립니다.

 

 

실제로 SSTF의 단점인 starvation을 해결하면서 비슷한 성능을 내므로 이 방식을 현재는 많이 쓰고있다고 합니다.

 

 

 

   디스크 캐시

디스크는 읽고 쓰는 속도가 굉장히 느린 장치에 속합니다. 따라서 Disk Caching 기법을 사용하여 디스크에 저장된 데이터를 메모리의 kernel space에 저장하고 필요할 때 user space에서 사용하는 방식이 이용됩니다.

 

이러한 메모리에 cache 영역은 유한합니다. 따라서 디스크에서 다른 데이터를 캐시에 저장하고 싶은데 데이터가 가득 차있어서 저장할 수 없을 때가 있을 수 있습니다. 이 때, 우리는 어떠한 데이터를 버리고 새로운 데이터를 넣어야할지 정해야합니다. 이러한 과정을 Cache Replacement라고 합니다. 

 

어떠한 데이터를 삭제해야할지의 기준은 크게 두가지가 있습니다.

 

1. LRU(Least Recently Used)

말 그대로 가장 오래된 데이터를 선택합니다. 해당 데이터를 삭제하고 새로운 데이터를 해당 공간에 넣는 방식입니다. 이러한 방식을 구현하기 위해 시간정보를 저장하는 저장공간을 따로 두는 것이 아닌, LinkedList나 stack을 이용해서 데이터들의 시간정보를 간접적으로 저장하는 방식이 이용됩니다.

 

 

2. LFU(Least Frequently Used)

가장 적게 사용된 데이터를 삭제합니다. 해당 방법을 사용하기 위해서는 각 데이터의 사용 횟수를 count하는 저장공간이 추가적으로 필요하게 됩니다.

 

---

오늘은 디스크 스케쥴링에 대해서 알아봤습니다. 감사합니다.