[OS] 데이터 블럭들의 관리

파일 시스템에서 파일 컨트롤 블록 리스트 다음에 데이터 블록 영역이 있다.

 

📁 File Allocation 방법

데이터 블록에는 파일의 내용이 저장된다.

만약 파일 크기가 크다면 데이터 블록 여러개가 필요할 것이고, 이들을 연결해주어야 한다.

이 연결 문제를 운영체제의 파일 시스템이 관리하는 방법에 대해 살펴보자.

파일 하나가 만들어질 때 생기는 파일 내용을 담은 데이터 블록을 어떻게 연결할지의 문제를 file allocation이라고 한다.

 

 

Contiguous allocation(연속 할당)

결론적으로 지금은 사용하지 않는 방법.

디스크 안에 존재하는 연속된 블록들을 할당해서 파일을 저장하는 방법.
그림을 보면 파일 allocation 테이블이라는 것이 있다.
여기 보면 파일 a가 있는데, 파일 a는 2번 블록부터 시작해서 3번, 4번의 세 개의 블록으로 구성된다.
즉 2, 3, 4번 블록으로 파일 a의 내용이 저장된다는 뜻이다.

이 방법은 파일을 읽거나 쓰는데 시간이 적게 걸리는 장점이 있다.
external fragmentation(외부 조각화)라는 심각한 문제가 있어서 지금은 안쓴다.

먼저 fragmentation에 대해 알아보자.
fragmentation이란 메인 메모리나 보조기억장치 같은 저장공간에 작은 크기의 빈 공간이 생기는 현상을 말한다.
그 빈공간은 fragment라고 부른다.
사용되지 않는 빈 공간이 연이어져 뭉쳐져 있으면 사용하는데 효율적인데, 작은 공간 상태로 남아있으면 뭔가를 저장하기에 쉽지 않다.
즉 공간 활용도가 떨어지는 것이다.

예를 들면 여기 29번 블록이 하나 남아있는데, 블록 하나에는 파일을 저장하기 쉽지 않기 때문에 29번 블록은 fragment가 된다.
0, 1번도 같다.
보통 파일들은 이보다는 크니까 contiguous allocation 방법으로 저장하려면 연속적인 빈공간이 아니면 사용하지 못한다.

이렇게 되면 디스크 전체적으로는 빈 공간이 있지만 파일을 저장할 수 있는 공간은 얼마 없으므로 디스크의 이용 효율이 떨어진다.

이때 external fragmentation이란 어느 파일이나 프로세스에 속하지 않고 fragment가 외부에 있다는 뜻이다.
29번 공간을 보면 이는 파일 a와 c의 외부에 있다.
internal fragmentation이란 fragment가 내부에 있다는 뜻으로, 어떤 파일에 할당한 공간 중에서 쓰지 않는 공간이 즉 intenal fragment이다.
예를들어 파일 a가 블록 2, 3, 4에 들어있는데, 세 블록중 2, 3 블록은 4096바이트를 모두 꽉 채운 상태일것이다. 그래도 자리가 부족하기때문에 블록 4가 할당된것이므로 이 블록 4 안에는 빈공간이 있을수도 있다.
하지만 이런 빈 공간은 오직 파일 a에 할당된 것이기 때문에 다른 파일이 사용할 수 없다.

결론적으로 contiguous allocation은 external fragmentation 현상이 발생하므로 좋지 않은 방법이다.

두번째 단점은 fit size가 증가하는 경우 빈 공간을 할당하는데 어려움이 있다.
예를 들어 파일 c는 25번 블록까지 사용하고 있다.
사용자가 c를 편집해서 뒤에 내용을 더 추가했다고 하자.
만약에 파일 c의 25번 블록에 인터널 fragment로 남은 부분이 있다면 그 부분을 사용할텐데, 내용이 넘쳐서 새 블록을 할당해야한다면 뒤에 연이어져있는 블록을 써야하니까 26번을 써야하는데, 이는 이미 파일 e에 의해 사용되고 있는 블록이다.
이런 경우에는 파일 c전체를 다른 곳으로 복사해서 거기서 파일 크기를 늘려야하고, 이렇게 이동하는데 시간이 걸린다.

 

 

chained allocation

위 단점들을 극복해서 만들어진것이 chained allocation(linked allocation)이다.
파일 사이즈가 쉽게 늘어난다는 장점이 있다.

이 방법을 위해서는 각 블록이 다음 블록을 가리킬 수 있는 포인터 주소 정보가 저장되는 영역이 각 블록마다 저장되어야하므로 데이터 블록 구조가 달라져야한다. 공간이 더 많이 쓰일것.

예를 들면 그림에서 파일 b가 1번이라는 시작 블록의 번호와, 총 길이 5를 저장한다.
그러면 1번블록과 뒤따라오는 4개의 블록이 전부 파일 b에 해당되는 것이다.
1번 블록에 다음번 블록 번호를 저장하는 별도의 필드를 만들어 두었으니, 그림에서는 두번째 블록이 8번 블록, 세번째 블록이 3번, 다음 14번, 다음 28번 블록이 된다.
주소를 보고 쫓아가면 linked list 형식으로 파일의 내용을 연결할 수 있는 것이다.

이런 방식으로 저장하면 파일 크기가 늘어나도 문제가 없다.
만약 28번 블록 뒤에 하나 더 늘어난다고 하면 31번 블록에 내용을 넣고 28번이 31번을 가리키면 된다.

또한 external fragmentation으로 공간 이용 효율이 떨어질 염려가 없다.
위 연속 할당에서 생기는 fragment들을 linked list로 가리켜서 사용하면 되기 때문이다.

하지만 이 방법도 단점이 있다.
direct access란 블록을 직접 찾아가서 읽는것을 말하는데 이것이 불가능하다.
chain식으로 연결이 되기 때문에, 만약 3번 블록에 에러가 생기는 등 읽지 못하게 되면 뒤따라오는 14번, 28번 블록도 읽지 못한다.

또한 첫번째 블록부터 읽어나가야지만 마지막 부분의 주소를 알 수 있기 때문에 읽기에 시간이 많이 걸린다.

 

 

 

indexed allocation

위 단점들을 극복해서 만들어졌다. 요즘 사용되는 방법이다.
그 파일의 데이터 블록을 인덱스 블록이라는 별도의 블록에 저장하고, 
데이터 블록의 번호를 저장하는 별도의 테이블이 있는데, 그 테이블을 저장한 블록이 인덱스 블록이다.
그림을 보면, 인덱스 블록을 읽으면, 1, 8, 3, 14, 28번 블록 순으로 파일이 모두 5개의 블록으로 저장되어있다는 것을 알 수 있다.
인덱스 블록이 몇번인지만 알려주면 전체 파일에 엑세스할 수 있는 것이다.

인덱스 블록은 인덱스 번호를 저장하기 위해서 특수하게 만들어놓은 블록이 아니라, 일반 데이터 블록과 똑같은 블록인데 그것을 인덱스 번호를 저장하는 용도로 사용하는 것이다. 때문에 어떤 블록이든지 인덱스블록으로 사용 가능하다.

단점은 파일을 저장하는데 필요한 블록의 개수가 1개 늘어난다. 공간이 그만큼 많이 든다.

chained allocation보다 indexed allocation은 안정성 면에서 더 좋거나 나쁘다고 할 수 없다.
만약 인덱스 블록이 깨지면 파일 내용을 전부 접근할 수 없어서 나쁜점도 있지만,
인덱스 블록이 아닌 다른 특정 블록이 깨졌다고 하면 그 외의 블록들은 문제없이 읽을 수 있다는 좋은점도 있다.

파일 b가 블럭 5개로 구성되는데, 내용이 추가돼서 더 늘어난다고 하면 빈 블록을 할당받은 후 번호를 인덱스 블록에 추가하기만 하면 되기 때문에 파일이 늘어나는 것에 문제가 없고, external fragmentation이 없다는 장점이 있다.

또한 파일 b의 내용을 어떤 블럭이든 직접 접근할 수 있다는 direct access 장점이 있다.

 

 

 

📁 Free-Space Managment

 파일 하나가 아니라 디스크에 구성되는 파일 시스템 전체의 빈 블록들을 어떻게 관리할 것인가?

 

파일 시스템의 데이터 블록중에는 내용이 있는 블록도 있지만 없는 블록도 있다.

즉, 파일에 할당되었느냐 아니냐를 구분해야 하는것이다.

예를 들어, 블록에 0 값이 전부 저장되어있다고 가정하자.

이는 0이라는 값 데이터가 저장된 것일수있으므로 빈 블록이 아니다.

즉 값을 기준으로 구분할 수 없고, 특정 블록이 특정 파일에 할당 되었는가를 구분해야한다.

 

이 그림을 보자.
흰 부분은 비어있는 부분이고 회색 부분은 사용된 부분이다.
파일의 크기가 늘어난다고 하면 비어있는 블록을 받아야 하기 때문에, 슈퍼블록에 어떤 블록들이 비어있다는 정보를 관리하고 있어야한다.

디스크에서 빈 공간을 관리하는 방법

 

 

Counting

연속할당 방법을 프리데이터블록 관리에 적용한 것이다.

예를 들면 0번 블록부터 한 개, 2번 블록부터 한 개, 4번 블록부터 네 개가 비어있다 와 같이 몇 번 블록부터 시작해서 몇 개가 비어있는지 정보를 슈퍼블록 안에 저장하는 방법이다.

 

 

Linked List(free list)

chained allocation 방법을 프리데이터블록 관리에 적용한것이다.
내용이 들어가는 블럭 옆에 블록 번호를 저장할 수 있는 별도의 영역을 만들고, 빈 데이터블록을 연이어서 가르쳐주는 linked list를 만든다.
chained allocation에서 발생하는 문제점이 똑같이 발생할까?

파일의 뒷부분을 찾아갈 때 시간이 많이 걸릴까? 즉 direct access가 안될까?
여기서는 해당되지 않는다.
파일의 내용이 저장된거라고 하면 사용자가 경우에 따라서 뒷부분을 읽을 필요가 있지만, 빈 데이터 블록을 할당하기 위해서 빈 데이터 블록들을 묶어둔거기 때문에 아무 빈 데이터 블록을 할당하면 된다. 굳이 뒤에 있는 빈 데이터 블록에 접근하고 할당할 필요가 없다.
그래서 빈 데이터 블록이 필요하다고 할 때 헤드가 가리키는 제일 앞의 블럭을 사용하고, 헤더는 이제 다음 블럭을 가리킨다.

안정성 문제가 나타날까?
만약 중간의 블럭이 깨지면 이후 블럭들에 접근할 수 없는것은 여기서도 마찬가지이므로 안정성 문제가 나타난다.

결론적으로 linked list는 좋은 방법이 아니다.

 

 

grouping

유닉스 초기 파일 시스템에서 사용된다.
indexed allocation방법을 프리데이터블록 관리에 적용한 것이다.
비어있는 블록들의 번호를 인덱스 블록에 저장하는 방식이다.

그림을 보자. 슈퍼블록은 여러 데이터블록들로 구성되는데, 그 중 하나를 인덱스블록으로 할당한다.
블록 하나 크기는 4096byte이고, integer는 4byte이므로 인덱스 블록 안에는 1024개의 번호들을 저장할 수 있다.
예를 들어서 4, 5, ... 109번까지 빈 블록들을 저장했는데, 빈 블록이 아직 더 남아있다. 한 인덱스 블록에는 1024개밖에 저장하지 못한다.
이럴때, 저장된 빈 블록들중 가장 위에 있는 번호가 109번이므로 109번 빈블록을 임시로 인덱스블록으로 사용한다.
109번 블록에 또 1024개 번호를 채우고, 또 남으면 109번 블록 안에서 가장 높은 숫자인 211번 블록을 임시로 인덱스블록으로 사용하는 방법으로 빈 블록들의 번호를 전부 저장한다.

이 방법으로 빈 블록을 할당하는 방법을 알아보자.
그 전에, 109번이나 211번같은 블록들은 특수한 블록이 아니라 그냥 데이터가 저장할 수 있는 파일 내용이 저장될 수 있는 일반 데이터 블록이다. 하지만 지금 당장은 비어있기 때문에 인덱스 블록으로 임시로 사용하는 것이다.

빈 블록이 필요하면 슈퍼 블록의 아랫자리에서부터 번호를 따가서 사용한다.
예를 들어 이 그림에서는 4번을 먼저 사용하고, 이 자리는 비게된다. 다음은 5번, 7번 순으로 사용되고 비어질 것이다.
그래서 위 그림처럼 마지막으로 109번이 남았다고 하자.
이 상태에서 또 빈 블록이 필요하다고 하면 이젠 109번을 사용해야하는데, 지금 109번은 빈 데이터 블록들의 번호가 저장되어 있기 때문에 109번에 있는 내용을 먼저 슈퍼블록에 비어진 부분들에 복사한다.
이후 109번을 백업하고 할당한다.

 

 

Bit vecter(bit map)

리눅스 파일 시스템에서 사용하는 방식이다.
파일 시스템 내에 데이터 블록 개수만큼 비트들을 일렬로 할당한다. 0번부터 n-1까지 비트가 나열될것인데 이때 n은 파일 시스템의 데이터 블록 전체 개수이다.
비트의 인덱스를 데이터블록 인덱스와 대응하여 해당되는 블록이 사용중인지 여부를 0과 1 비트로 표시한다.
사용중인 블록을 나타내는 비트 값이 0인지 1인지는 운영체제가 정하기 나름이지만 보통은 사용중인 블록을 0으로 표시한다.
이유는 0을 사용중인 블록이라고 나타내야 빈 블록을 찾는게 훨씬 빠르기 때문이다.
예를 들어 0부터 7번까지 블록을 전부 사용중이라고 하면 0000000이 될 것이다.
이 비트 시퀀스를 쭉 조사할 때 0으로 된 값들은 빨리 건너뛰고 non-zero값이 들어있는 1을 찾아내면 빨리 찾아낼 수 있다.

개념적으로는 아주 간단하고 좋은 방법이지만 단점도 있다.
비트 벡터의 길이가 아주 길어질 수 있어서, 디스크 공간을 많이 차지할 수 있다.
파일 시스템의 데이터 블록 영역 크기가 1TB라고 가정하자. 즉 데이터를 저장하는데 1TB만큼 쓸 수 있다고 할때, 이는 2^40bytes이다.
이를 하나의 블록 크기인 4096으로 나누면 2^28이 되고, 이것이 디스크 안에 있는 블록의 개수이며 곧 비트맵의 길이이다.
비트맵의 길이가 2^28비트, 즉 2^25바이트이다. 이 크기는 4096바이트 블록이 약 8천개 모인 크기이다.

즉 효율적으로 아주 빨리 찾을 수 있다는 장점은 있지만, 비트맵 길이가 길어질 수 있다는 단점이 있다.