OS

Go back

OS Review
Device Driver
NS Tools

Home
Papers
Daily Link

To Main

14. 파일시스템 및 디스크 스케줄링(File System and Disk Scheduling)

이제 끝이 보인다,,,끝이 보여!!! 여러분 힘 내십쇼!
뭔가를 제대로 알기란 이렇듯 쉽지가 않은가 봅니다. 그래도 이왕 공부하는거 즐거운 마음으로, 그리고 부담없이 읽어주시기를 당부하네요.

디스크 자체를 논하기 이전에 일단 디스크를 논리적으로 관리해주는 파일 시스템에 대한 전반적인 이해를 할 필요가 있지요. 파일 시스템은 항시 디스크에 상주하면서 많은 양의 데이터를 영구적으로 담고 있어야만 한다는 숙명적인 존재이기도 합니다. 파일 시스템이 하는 구체적인 일들로써는 유저가 원하는 데이터의 트래킹, 빈 공간의 확보 및 트래킹, 그리고 오에스와 디스크와의 교량역할등이 있지만 여기서는 파일시스템의 데이터 트래킹과 빈공간 관리만을 간략하게 다루어 보렵니다.

자, 그럼 이젠 잠시 디스크를 살펴볼까요? 디스크는 본질적으 논리블록(logical block)으로 불리는 일차원 배열들입니다. 논리적 블록은 고로 디스크에서 씨피유로 데이터를 전송함에 있어서의 가장 기초적인 단위가 되죠. 디스크의 논리적 기초단위가 1 또는 0을 담고 있을거라고 생각하시는 인간님들이 많은데, 그렇게 디스크를 관리했다가는 오에스가 500메가 짜리 디스크 관리하기도 버거워져버릴겁니다. 블록은 그래서 일정한 수의 바이트 크기로 나뉘게 되는데 사실 쪼끄만 문서같은 경우는 그 크기가 한개의 블록크기보다도 훨씬 작을수가 있지요. 그럼 블록안에 남아도는 나머지 바이트들은? 그거 그냥 버려야 되요. 또한 디스크의 용량이 커지면 커질수록 논리블록의 크기또한 크게 잡아주게 되고, 그렇기에 기가급들 하드는 엄청난 공간의 낭비가 발생하겠죠? 바로 이래서 최근 맥오에스8.0에서부터는 HFS+(Extended HFS)라고 불리는 파일시스템입니다. 대용량 하드를 사용함에 있어서도 작은 크기의 논리블록을 잡을수 있도록 허용하는 파일 시스템이니 만큼 40M 짜리 하드달아놓고 HFS+인스톨하느라 고생했다고 자랑하면 븅따리 취급 받게되는겁니다.

디스크의 본질적인 특징은 여러파일들에 대한 덮어쓰기 및 직접엑세스(direct-access)라고 할수 있어요. 이 두가지의 특징을 가지고 있는 가운데 디스크 관리의 관건은 어떻게 파일들을 공간에 할당을 시켜줌으로써 전체적인 디스크의 공간의 효율이 증가하는 동시에 파일들에 대한 엑세스를 재빨리 수행하는가 입니다. 이때 디스크내의 공간에 대한 할당을 위해서는 크게 세가지 방법들이 등장합니다. 연속(contiguous), 링크드(linked), 그리고 인덱스(indexed) 할당이라고 하죠. 특정 시스템은 그 세가지를 모두 지원해주지만, 대부분 그중 한가지만을 이용하거나 짬뽕을 시킨 제2의 방법을 이용합니다. 자! 그럼 이제는 저 디스크라는 광활한 해원에서 넘실거리는 무수한 블럭들중 내가 원하는 블록을 그럼 과연 어떻게 찾아내어 할당할것인가에 대한 항해를 해봅시다.

연속할당
연속할당은 가장 직관적인 할당을 수행하게 됩니다. 말그대로 어떤 파일을 디스크에 할당 해줌에 있어서 먼저 b번째 블록을 할당한 다음 아직도 더 할당을 해야할경우 b+1번째,,,이런식이죠. 이 방법은 일단 디스크 헤드의 움직임을 최소화 한 방법이니 만큼 속도하나만큼은 숑숑~입니다. 하지만 오에스입장에서는 아주 골치아픈 경우를 맞닥뜨리게 되는데, 과연 파일의 크기가 얼마나 될지가 확정되지 않는 경우입니다. 그냥 문서를 하나 열어놓고 유저가 계속 타이핑해가면 파일이 점점,,,커질텐데, 공간이 널널하다면야 상관없겠지만, 어떤 파일을 지우고 그 자리에서 다시 채워가고 있는 경우는 참으로 곤혹스러워지죠. 또한 등치큰 파일 한번 지우고 나면 엄청난 프레그먼테이션이 생기느니만큼 가끔씩 주메모리에서나 해주던 컴팩션을 디스크에 걸어줘야한다니 배보다 배꼽이 더 커져버리게 됩니다.

링크드 할당
위의 단점을 개선해보고자 등장하는 것이 링크드 할당이죠. 이것은 간단하게 이야기해서 논리적으로 연속된 블록들을 링크드 리스트(linked list)로 만들어버리는 것입니다. 위에서 발생한 문제를 이방법은 멋지게 해결하지만, 상당히 심각한 단점또한 가지고 있게되죠. 먼저 각 블록마다 포인터를 한개씩 달고 있어야 하기에 공간낭비, 링크드 리스트의 특성상 상대적으로 느린 랜덤엑세스, 그리고 결정적으로 특정 블록의 포인터 한개가 훼손될시 전체 파일은 두동강나버리게 됩니다. 못쓰게 되겠죠. 이것을 극복하기 위해서 리스트(doubly linked list)도 사용되지만, 그만큼 공간은 또한번 낭비되고 말아요. 물론 디스크 헤드는 장난아닌 노가다를 뛰는 운명에 처합니다. 현재 윈도우즈에서 채용되고 있는 FAT(File Allocation Table)은 바로 이 링크드 할당의 변종인데 각 디스크의 파티션정보의 시작 즈음해서 담고있는 각 파일들의 시작블록을 포인트해주는 테이블을 가지고 있다는 특징이 있습니다. 모든 파일을 링크를 따라서 찾아내는것보다 훨씬 효과적인 탐색이 가능해지겠죠?

인덱스 할당
다음으로 인덱스 할당은 한개의 블록이 특정 파일에 대한 모든 블록들의 위치정보를 담고있게 됩니다. 이 방법은 링크드 할당의 직접엑세스에대한 버벅거림을 어느정도 해결해줌과 동시에 연속할당의 공간낭비문제 또한 해결해 주지만 실질적인 포인터에 의한 오버헤드는 링크드 할당보다 심하다고 합니다. 또한 만에 하나라도 인덱스가 들어있는 블록이 망가져버린다면,,,이건 대형사고입니다. 인덱스 할당도 여러개의 변종이 존재하는데, 멀티레벨 인덱스(multilevel index)라는 방법과 링크드 할당을 섞은 짬뽕인덱스(combined index)가 바로 유닉스 시스템이 채용한 방법이랍니다. 이것은 인덱스 블록이 인덱스 블록을 포인트하는 식으로 파일의 크기에 따라서 계속 인덱스 블록들끼리 포인팅하다가 최후에 데이타가 담겨있는 블록들과의 연결이 이루어집니다.

인덱스 할당을 곰곰히 생각해보면 이것은 바로 데이타 구조론의 B-트리구조를 하고 있음을 알게 되죠. B-트리구조의 특징은 한개의 노드에서 여러개의 노드들이 뻗어나가게 되는 구조이기에 그 높이는 낮지만 밸런스를 유지하기가 상당히 난해한 구조입니다. 밸런스가 유지되어야 각종 탐색이나 소팅등이 수월해지지요. 가끔 노턴디스크닥터 돌리다 B-tree가 어쩌니 고칠거냐~!!!??? 라고 뭍는데 무심코 오케이 눌러놓고 뜻밖의 참사를 당하게 되는 이유가 바로 B-트리의 각 노드이 파일들의 위치를 담고있는 인덱스 역할을 하고 있는 데이터이기 때문일겁니다. 참고로 킨토시는 각 볼륨별로 카탈로그(file catalog)라는 것을 이용해서 각종 파일및 디렉터리 정보를 유지해줍니다. 파일 메니저를 공부하게 되면서 가장 여러분을 고뇌하게 만드는 녀석이죠.

우리에게는 특정 크기의 파일이 할당되었다는 사실에서 남은 빈공간을 트래킹하기란 그리 어려운 일이 아니겠지만, 파일시스템에게는 상당히 중요하면서도 골치아픈 문제중에 하나입니다. 이를 위해서는 주로 비트벡터(Bit Vector)를 이용하게 되는데, 벡터란 뭐 방향과 크기를 갖는,,,이러한 수학적인 의미의 벡터라기보다는 그냥 배열이다,,,라고 생각해주시면 됩니다. 즉 0과1만을 담고있는 길죽한 배열을 정의해놓고 각 배열과 한개의 블록을 대응시켜줍니다. 만일 b번째 블록에 내용이 채워지면 똑같이 b번째 배열을 0으로 만들어주게 되고 결과적으로 1이 담겨있는 배열의 총합 곱하기 단위 블록의 크기가 결국엔 사용가능한공간이 되는것이죠. 또다른 방법들로써 링크드 할당과 유사하게 빈공간만을 링크드 리스트로 관리하는 방법, 그룹핑, 그리고 카운팅등이 존재하지만 역시 단순하고 빠른 비트벡터를 이용한 방법이 가장 널리 쓰인다고 하네요.

여기까지 일단 파일 시스템을 살펴보았군요. 하지만 디스크 자체또한 나름대로의 세계가 있습니다. 바로 디스크 스케줄링이라 불리는 알고리즘들이지요. 디스크 입출력의 성능은 결과적으로 파일시스템의 효율성과 디스크 스케줄링 알고리즘의 함께달리기 결과라고 할수 있어요. 스케줄링 알고리즘은 주로 펌웨어(firmware)형태로 존재합니다. 즉, 디스크드라이브에 딸려오는반도체 안에 있다는 뜻이죠. 그래도 그 칩을 무능화 시킬수 있는 나름대로의 방법은 있고, 그렇기에 이분야사람들 자기가 설계한 디스크 스케줄링 알고리즘을 실험해보면서 나름대로의 익스타시를 느끼고 있는거겠죠.

디스크 스케줄링은 일련의 블록들을 읽거나 쓰기위하여 먼저 큐에 차례로 담아놓고 큐안에 들어있는 블록들을 어떤 규칙에 의거해서 찾아가면 더욱 효과적일까를 논하는 알고리즘입니다. 쉽게말해 Seek Time의 최소화가 바로 목적입니다. 직관적인 설명을 위해서는 책 p433~p.437에 나오는 도표가 필수적이겠으나, 여기서는 도표를 싣는 작업을 제게 기대하진 마쇼. 고로 먼저 큐안에 6, 9, 2, 7, 1, 8, 4, 5번째의 블록에 대한 엑세스 요구가 들어있고, 현재 헤드는 3번째 블록에 놓여져 있다는 전제로 다음의 알고리들을 살펴봅시다.

1. FCFS(First Come First Serve) 스케줄링 : 이것은 큐의 특징인 FIFO(First In First Out)란 말을 좀 특이하게 말하고 싶어서 만든 말일뿐 그 개념은 똑같다고 할수 있지요. FCFS는 그 아이디어 자체가 무척 공평무사하긴 하지만 빠른 속도는 결코 제공해 주지 못합니다. 위의 전제대로 블록요구에 대한 큐가 만들어져있을경우 3->6->9->2->7->1->8->4->5순으로 디스크 헤드는 블록을 찾아 다니겠지만, 헤드의 움직임을 보면 처음에 오른쪽에서 다시 왼쪽으로, 왼쪽에서 다시 오른쪽으로( 현재의 번호보다 큰번호의 블록을 찾기위해서는 오른쪽으로 헤드가 움직이고 작은 번호를 찾기위해서는 왼쪽으로 움직인다고 가정) 지그재그식으로 헤드가 움직이기에 이동거리 또한 무지하게 길어지죠(책에서는 wild swing~이라는 멋진말을 씁니다). 더구나 디스크의 특성상 엄청난 대용양 하드를 이런식으로 스케줄링했다가는 불탄하덜을 보고말게 될겁니다.

2. SSTF(Shortest Seek Time First) 스케줄링 : 어디서 많이 본듯한 느낌이드는 알고리즘이죠? 이 알고리즘은 아주 옛날 옛적 씨피유 스케줄링을 다루면서 등장했던 SJF(Shortest Job First) 알고리즘과 같은 사상적 기반을 가지고 있는 알고리즘이죠. 본 알고리즘은 현재의 위치에서 과연 큐안에 있는 블록들중 어디를 가면 가장 빠를까(어디가 가장 가까운가)를 고른뒤 헤들르 움직입니다. 위의 전제에서는 3->4->5->2->1->6->7->8->9순으로 헤드를 움직이게 되겠죠. 본 알고리즘은 FCFS에 비하여 상당히 빠른 성능을 보여주지만, 결정적인 단점을 가지고 있어요. 바로 배고픔(starvation) 문제가 발생할 여지가 큽니다. 다른 블록들에 비하여 유난히 멀리 떨어져 있는 블록 한개가 큐에 들어갈경우 헤드의 방문을 받을 가능성 매우 희박해지겠죠.

3. SCAN 스케줄링 : 말그대로 스캔이라는 행위를 하면서 블록을 찾아다닙니다. 위의 경우 3->2->1->0->4->5->6->7->8->9->10이라는 순서로 블록을 찾아가게 되지요. 여기서 0과 10은 최초의 블록및 최후의 블록을 이경우 의미하게 되는데 그족으로 찾을 블록이 없을지라도 일단 한 끝단에 이르러서야 방향을 바꾸는 스캔정신을 철저히 지키고 있는 기법입니다. 이 방법은 엘리베이터 알고리즘이라고도 불리게 되죠. 이경우의 엘리베이터는 언제나 위로 한번 올라갔다가 아래로 한번 내려오는 식으로 손님을 태우게 됨으로써 각 층별로 흩어져있는 기다리는 손님들을 나름대로는 효과적으로 운송해주게 됩니다. 하지만 이 알고리즘 또한 한가지 취약점을 가지고 있지요. 다시 엘리베이터 예를 들었을때, 손님들의 목적은 단순히 엘리베이터에 몸을 싣는것이라는 전제와 모든 층에서 손님이 나타날 확률이 같다는 전제하에서는 엘리베이터가 맨 윗층에 있을때 손님이 가장 많은 층은 어디일까요? 조금만 생각해보면 가장 밑층일거라는 결론이 나올겁니다. 윗층과 가까울수록 최근 엘리베이터가 최근에 지나갔기 때문에 손님이 상대적으로 적은것이죠. 고로 헤드가 한쪽 방향의 끝에 이렀을때 반대쪽 끝단에 위치한 블록들의 요구가 큐의 대부분을 차지하게 될겁니다. 이문제에 대한 멋진 해결책이 다음에 나요죠.

4. C-SCAN(Circular-SCAN) 스케줄링 : 아주 간단하게 헤드의 움직임을 10->0 이런식으로 연결해 버린것입니다. 더이상 엘리베이터 예가 불가능해지죠,,,음,,,시공을 초월하는 사차원초울트라슈퍼변태엘리베이터를 경모국군이 느닷없이 주장 하는군,,,에라이~!!! 아뭏든지 C-SCAN도 SCAN의 한 기법인지라, SCAN기법의 쓸데없는 짓거리 한가지를 둘다 언제나 행하고 있지요. 다음 알고리즘은 그짓을 더이상 하지 않습니다.

5. LOOK와 C-LOOK 스케줄링 : 쓸데없는 짓거리란 바로 스캔정신에 입각하여 0이나 10을 언제나 만나야지만 직성이 풀리는 특유의 고집입니다. 바로 LOOK는 스캔 알고리즘의 순서를 고대로 따르되 한 끝단에 도착하지 않고라도 다음 요구되는 블록으로 회귀할 준비가 되어있는 알고리즘이고, C-LOOK은 그러한 LOOK알고리즘을 마찬가지로 양끝단을 연결하듯 헤드의 움직임을 규정해주는 알고리즘이랍니다.

이상으로 디스크 스케줄링 알고리즘들을 간략하게 살펴보았습니다. 디스크 스케줄링 알고리즘을 현실에 적용함에 있어서 많은경우는 SSTF나 LOOK을 디폴트로 사용하다가 특수한 목적의 용도로 시스템을 운용할시 그에 걸맞는 스케줄링을 적용하게 됩니다. 하나의 예로써 특정 시스템의 경우 주로 한위치의 블록만을 허구한날 요구하게 된다면 위에서 논의한 모든 알고리즘들은 결과적으로 FCFS 스케줄링 알고리즘 처럼 행동하게 되지요, 하지만 SSTF나 LOOK의 경우는 각각 최소 거리를 찾거나 한쪽방향으로만 움직이려는 부가적인 루틴들이 있기때문에 결과적인 행동 양식은 같으나 쓸데없는 계산으로 오히려 조금 느릴수 있는 알고리즘이 되어버리겠죠.

이번장에서 끝내고 싶었으나 15번을 채우라는 주님의 뜻인지 유난히 긴 문서가 되어버렸네요. 이제 공식적으로 "알고리즘"이라라고 나올 거리들은 제 문서에서는 없을겁니다. 처음부터 지금까지 오에스론을 정독하신 분들, 이 문서를 닫아버리기 전에 한번 곰곰히 생각해 보시기 바래요. 그동안 등장했던 알고리즘들의 이름으로 나타난것들, 결코 어렵고 거창한것만이 아니였을 것입니다. 바로 상식적인 상황을 간단 명료한 경우의 수로 나눈뒤 각 경우의 수에 알맞는 행동지침을 정의해주는 것이라는 생각에 동의하시는지? 다음장에서는 쓰레드와 OSI 7레이어 프로토콜을 간략하게 다룬뒤 오에스론을 마칠까 합니다. 읽어주신분들,,,고마워~

-duffer 경준 (http://vorlon.cwru.edu/~kxm73)