[운영체제및실습] 10주차 4회차: 디스크 스케줄링

여러분은 이전에 디바이스 스케쥴링이라는 것이 무엇인지에 대해서 공부를 한 적이 있습니다.

디스크 스케쥴링은 디스크라는 디바이스에 대한 스케쥴링입니다.

일반적으로 입출력 장치의 스케쥴링에 사용하는 알고리즘은 선입선출 알고리즘을 사용합니다.

디스크의 경우에는 선입선출 알고리즘을 사용하지 않습니다. 

왜 사용하지 않는지, 그 대신에 어떤 알고리즘 사용하는지 알아봅시다.

이전에 보았던 디스크 장치의 구조를 다시 봅시다.

 

동그란 금속판 한 장 또는 여러 장이 존재하는 모습을 볼 수 있습니다.

하드디스크에선는 디스크 3장이 있지만 윗면, 아랫면 두 면에 모두 정보를 기록하는 것이 일반적입니다.

 

 

이 그림을 봅시다.

디스크 한 면을 위에서 바라보면, 왼쪽 그림처럼 둥근 띠 모양이 여러 개 있는데, 띠 한 줄을 트랙이라고 합니다.

트랙은 운동장 트랙이나 나이테와 유사한 모습입니다. 여러 개의 트랙이 있어서 번호를 붙이는데, 바깥쪽이 track0이고, 안쪽이 track1이고 차례로 바깥부터 번호를 붙이며, 하나의 면에는 20개부터 1500개의 트랙이 존재합니다. 첫번째 디스크의 윗면, 아랫면 해서 3개의 디스크에는 6개의 surface가 존재하며, 다같이 트랙 바깥쪽부터 같은 번호를 붙입니다. 0번부터 n-1번까지 존재합니다. cylinder는 모든 디스크에서 같은 번호의 트랙들의  집합입니다. 각각의 디스크에서 같은 위치에 있는 트랙들을 모아서 실린더라고 부릅니다. 그러니까 트랙이 디스크에 모두 100개가 있으면, 실린더도 100개가 있습니다. 트랙들은 피자 조각처럼 여러 조각들로 나뉩니다. 예를 들어 노란색 부분을 보면, sector라고 합니다. 노란색 섹터도 바이너리 데이터들이 쭉 나란히 저장됩니다. 섹터 끝의 줄은 실제로의 줄이 아니며, 섹터와 그 옆의 섹터의 경계를 나눈 것 뿐이며, 줄 부분에는 노란색 부분의 데이터가 저장되고 나면, 저장된 데이터들에 대해 parity를 계산해서 책선값을 저장합니다. 책선은 디스크를 접근하면서 주기적으로 오류 검사를 할 때 이용됩니다. 저장된 데이터에서 책선값을 새로 계산한 다음에 이전에 저장한 책선값과 지금 계산한 책선값과 같으면 문제가 없으며, 다르다면, 의도치않게 변경되어서 bad sector로 판정합니다. 섹터는 제조사가 정의한 디스크에 저장하는 물리적인 최소 정보 단위입니다. 그래서 섹터 단위로 디스크에 가서 읽고 씁니다. 그러나 운영체제 입장에서는 디스크에 접근하는 정보 단위는 섹터가 아니라 블록이라고 하는 4096바이트, 즉 4K바이트 블록이라는 정보를 사용합니다. 따라서 블록을 섹터로 맵핑시켜야 합니다. 두 크기가 같으면, 운영체제에서 한 블록을 읽거나 쓸려고 할 때 디스크의 한 섹터만 접근하면 됩니다. 다르면, 한 블록을 접근하기 위해 보통 블록 크기가 크므로 연속적인 섹터 여러 개를 모아서 운영체제에게 한 블록으로 돌려줍니다.

초록색 부분은 disk arm이라고 합니다. 끝부분은 head라고 합니다. head가 디스크 면 위를 스캔해가면서 섹터에 저장된 일련 데이터를 읽는 센서입니다. arm이 제일 바깥쪽 트랙에 있는 상태에서 노란색 부분을 읽으려면 arm이 움직여서 변경되어야 합니다. arm 3개가 모두 일체형이어서 모터가 축 역할을 하는데, 바깥쪽부터 노란색 있는 부분으로 arm팔이 움직여야 합니다. 디스크는 축을 중심으로 빙글빙글 돌아서 노란색 부분이 한 바퀴 돌아서 arm에 끝에 있는 head가 노란색 부분을 스캔해 가면서 노란색 정보를 읽습니다.

 

rotation speed는 3600~7200 rpm(1분당 회전수)를 가리키며, 3600이면, 1분이 60초여서 1초에 60번 회전한다는 말입니다. 요즘 제품은 7200rpm이므로 1초에 120번 디스크가 돌아가게 됩니다.

 

운영체제는 디스크를 access할 때 블록 단위로 합니다. 1차원 array로 간주합니다. sector하나의 크기는 32~4096바이트이므로 섹터가 블록 크기보다 작을 경우, 연이어서 여러 개의 섹터를 한 블록으로 간주합니다. 블록들이 순차적으로 연결되어 있는 1차원 array로 운영체제는 생각하며, 각 블록마다 b0,b1,...,bn-1처럼 블록 번호를 매깁니다. 편의상 섹터 크기와 블록 크기가 같다고 가정합시다. 한 섹터에 한 블록이 저장되는 것입니다. 이럴 경우, 어떻게 번호를 부여하는 지 알아봅시다. 앞의 그림에서 디스크에 저장된 특정 블록을 가장 자리부터 시작해서 특정 위치에 있는 섹터를 0번으로 주면, 그 옆은 1번, 그 옆은 3번,... 7번까지 총 8개의 블록이 존재합니다. 안쪽으로 들어오는 것이 아니라 아랫면의 뒤쪽에 있는 섹터를 8번으로 붙이며, 1번 뒤는 9번으로 매겨서 15번까지 붙입니다. 16번은 두번째 디스크의 똑같은 위치의 섹터에 번호를 매겨, 같은 트랙에 있는 트랙들에 대해서 실린더 단위로 번호를 매기게 됩니다. 디스크 3개는 6개의 surface가 존재하므로 48개의 번호를 매긴 후에는 다음 안쪽으로 들어와서 번호를 매깁니다.

그래서 이 번호가 블록의 주소에 해당합니다. b100이 몇 번 서키스에 몇 번 트랙에 몇 번 섹터에 있는 것인지 변환해서 계산할 수 있습니다. 물리적인 디스크의 위치도 계산해서 실제 디스크를 접근합니다.

 

이제까지 디스크 구조를 살펴봤습니다.

이러한 디스크의 구조 덕분에 물리적인 섹터의 위치에 따라 시간이 다르게 걸려서 디스크 스케줄링이 필요합니다.

 

 

디스크를 읽는데 걸리는 시간을 봅시다. 앞 그림에 있었던 노란색 섹터를 연상해봅시다. 먼저 arm이 노란색 sector가 들어있는 track에 가야 합니다. 그 후 head가 노란색으로 갈떄까지 기다려야 합니다.

seek time은 arm이 기계적인 모터에 의해 움직여서 해당 트랙으로 옮기는데까지 걸리는 시간입니다. 

그 후, 디스크가 빙글빙글 돌아서 앎 끝의 head로 와야 하니까 그 시간을 Rotation delay라고 합니다.

arm이 원래 여기에서 기계적으로 쭉 이동을 해서 seek time이며, 끝의 head라는 센서가 노란색 포함 트랙의 다른 섹터를 가리키므로 노란색 섹터가 올 때까지 기다리는 시간이 rotation delay입니다. 그러고 나서 실제 노란색 부분이 head밑을 쭉 지나가면 데이터 센싱을 하는 데 그 시간을 Data transfer time이라고 합니다.

Wait for Device, Wait for Chanel은 고려하지 않겠습니다. 디스크 활성화 된 후에는 seek, rotational Delay, Data Transfer과정을 거칩니다.

 

이렇게 디스크가 준비된 상태에서 특정 블록을 찾아가는데 걸리는 시간을 봤는데, rotational delay는 운이 좋으면 0이 될 수도 있고, 운이 나쁘면 거의 한 바퀴를 돌아야 할 수 있습니다. 평균적으로 0.5바퀴정도 기다린다고 볼 수 있습니다.

data tranfer과 rotational delay는 디스크 회전 속도에 따라 좌우됩니다. 7200rpm인 경우, 초당 120번 회전해서 평균적으로 0.5바퀴를 기다려야 된다고 하면, 그 시간은 4ms입니다. cpu입장에서는 제법 긴 시간이지만, 실제로 기계적인 동작으로 모터에 의해서 앎이 트랙을 바꿔나가는 시간에 의하면 디스크가 회전하는 데 걸리는 rotational delay는 아주 적다고 나왔습니다. 즉, seek time이라고 하는 것처럼 arm이 트랙을 왔다갔다 하는데 걸리는 시간이 제일 많이 걸리며, 디스크를 빠르게 동작하게 하려면 seek time을 줄여야 하는 것이 밝혀졌습니다!

 

seek time이 성능을 좌우하는데, 어떻게 그 시간을 줄일까요? 소프트웨어적으로 개선할 때, 디스크 스케줄링이 그 방법입니다.

 

디스크 스케쥴링의 필요성을 이해햇고, 알고리즘을 봅시다.

요청한 순서대로 fifo구조로 선입선출 구조로 합니다. 그림에서 y축에 있는 번호는 트랙 번호를 나타냅니다. 0번부터 199번까지 존재합니다. x축은 시간의 흐름입니다. 위의 숫자들 55,58,39,18,90,160,150,38,184이 있는데, 디스크에 접근 원하는 트랙번호를 나타냅니다. 그리고 처음시작이 100번이므로 100번 트랙에 있다고 가정한 것입니다. 디스크 요청이 오게 되면, 오는 순서대로 처리할 것이고, cpu는 다른 프로세스로 가서 그 블록으로 가며 여러 개의 요청이 올 수 있는데, 휴에 그 요청들을 넣어놓습니다.

100번에서 55번으로 쭉 이동해야 하는데, 그게 끝나면, 55에서 58로 3개의 트랙을 움직입니다. 그 다음 과정도 마찬가지입니다. 

제일 위쪽이 fifo 알고리즘입니다. 처음 위치가 100번 트랙이므로 55번 트랙으로 옮겨가기 위해 45개의 트랙을 옮겨갔습니다. 그 다음 58번으로 가기 위해 3개의 트랙을 이동했습니다. 이런 식으로 모든 서비스 요청을 서비스했다면, 총 498개의 트랙들을 이동한 것이 됩니다. 이런 방법을 해보니까 너무 많은 트랙들을 왔다갔다한다는 것을 알게 되었습니다. 

 

 

SSTF라고 하는 Shortest Seek Time First라는 방법이 나왔습니다. 그래서 seek time이 짧은 것을 먼저하라는 말입니다. 즉 요청 온 순서대로 서비스를 진행하는 것이 아니라 head와 가까운 트랙을 먼저 서비스하는 것입니다. 100번에서 90이 제일 가까워서 90을 서비스하며, 그 다음은 거리차이가 가장 작은 58로 가며, 55번으로 가며, 39번으로 가며, 18로 갑니다. 그 후, 150,160,184로 서비스합니다. SSTF로 하면, 248개의 트랙만 이동하면 되서 거의 반 정도의 시간을 줄일 수 있습니다.

근데 문제점이 있습니다. 요새 그래서 사용하지 않습니다. 이것은 우선순위에 기반한 방법인데, 우선순위가 낮은 요청은 오랫동안 기다려야 하며, 그 부작용을 starvation(기아) 현상이 생깁니다. 왜 생기냐면, arm이 지금 100번에서 0번쪽으로 가장자리쪽으로 가고 있는데, 계속 가장자리 부분이 요청이 되면, 안쪽 부분은 계속 기다려야 하는 현상이 발생합니다. 이런 문제를 해결하기 위해서 SCAN이 나왔습니다.

 

 

SCAN은 스캐너는 종이 한쪽 끝에서 다른 한 쪽 끝으로 쭉 스캔하는데, 트랙 0번부터 안쪽에 있는 트랙까지 진행하고 그때마다 서비스를 할 것을 하며, 다시 바깥쪽으로 가는 방법입니다. 이 예에서는 100번에서 숫자가 커지므로 중심축으로 갑니다. 서비스 요청은 같은 경우입니다. 들어온 순서와 상관없이 쭉 안쪽으로 이동을 함녀서 바로 앞에 있는 150,160,184를 진행을 합니다. 더 이상 갈 필요가 없으면, 바깥쪽으로 나가면서 90,58등을 진행합니다. 이때, 이렇게 하다가 새로운 번호가 들어오면 나가면서 바로 서비스를 하게 됩니다. 이러면서 안쪽으로 훝어나가면서 Elevator Algorithm이라고 부릅니다. 처음에는 0번부터 199번까지 끝에서 끝으로 터치하는 방식으로 무조건 갔는데, 이제는 개선되어서 더이상 안쪽 서비스가 할 게 없어서 바로 방향을 움직여서 Elevator Algorithm이라고 부릅니다. 또한 Look policy라고 부릅니다. scan을 쓰면 250트랙을 이동하므로 앞의 SSTF와 성능이 비슷합니다. 하지만, SCAN에서는 starvation방법이 안생겨서 SCAN을 사용합니다.

 

 

disk cache, buffer cache, page cache라고 부르는 디스크 캐쉬를 알아봅시다. 디스크는 속도가 매우 느리므로, 디스크에 접근을 자주 하면, 시간이 많이 걸려서 디스크에 접근할 떄 걸리는 시간보다 더 빨리 접근할 수 있는 곳에 사본을 저장합니다. 디스크의 경우, 디스크보다 빠른 저장 공간은 메인 메모리입니다. 디스크 캐쉬라고 하는 것은 운영체제가 사용하는 메모리의 일부를 할당해놓고, 보라색으로 표시한 블록을 읽었으면, 그걸 전해주면서 내부적으로 메모리 안에 사본을 저장합니다. 디스크 안의 내용을 읽고 싶으면, 메모리 속의 커널 공간의 블록을 바로 읽어서 유저 공간에서 접근해서 빨리 접근 가능합니다. 디스크 캐쉬에 많은 수의 블록을 저장하려고 하지만, 메모리 공간도 한계가 있어서 무조건 많은수를 저장할 수 없어서 일정한 수만 저장합니다. 디스크 블록을 읽어서 언젠가는 디스크 캐쉬의 빈 자리가 없어서 블록들로 꽉 찼는데, 새로운 블록을 일어와야 하면, 그럴 경우, 미리 들어와있는 것을 지우고 새로 들어온 것을 저장해야 할 것입니다. 이미 들어와있는 블록중에 어떤 블록을 지울까를 결정할 것을 Cache Replacement라고 부릅니다.

 

 

이때, Replacement알고리즘을 진행해서 디스크 캐쉬에서 없앨 블록을 결정하는데, 많이 쓰이는 것이 Least Recently Used(LRU)방법과 Least Frequently Used(LFU)방법이 잇습니다.LRU는 시간을 기준으로 가장 오래 전에 접근했던 것을 없애는 것입니다. LFU는 횟수 기준으로 프로세스가 요청할 때마다 counter에 횟수를 하나씩 증가해 횟수가 적은 것을 쫓아냅니다. LRU를 하기 위해서는 시간값을 저장하는 저장공간을 두고, 시간값을 기록하면 됩니다. 시간값을 비교해 블록들을 stack이나 linked list로 구현합니다. 그래서 블록들을 linked list로 하면, 어떤 블록들이 이용되었을 때 가장 최근에 쓴 것을 linked list 앞부분에 넣어서 맨 뒷부분을 삭제합니다. 비슷한 방법으로 stack이 있는데, 최근 이용된 것은 stack의 top으로 옮겨서 bottom에 있는 것을 삭제합니다.