보조기억장치 파일 시스템의 빈 공간을 관리하는 방법에 대해서 알아보자!!
1) Bit Vector
데이터 블록 중 비어있는 블록이 어디인지 관리해야 한다.
이 때, bit map(bit vector)을 이용하여 관리한다.
m개(총 데이터 블록 개수)의 bit map을 둠으로써, 해당 bit map의 한 bit은 각 블록 하나하나와 matching되도록 한다.
즉, 각 블록은 1bit으로 나타내진다.
그 bit이 0인지 1인지에 따라 해당 블록이 사용중인지 나타낸다. 1이면 사용중, 0이면 빈 블록으로 표시한다.
만약 10개의 블록이 필요하다면 연속으로 10개 0인 bit을 찾으면 된다.
Bit Vector은 이렇게 탐색하는 데에 효과적이다.
리눅스에서는 bit vector 기법을 사용한다.
2) Linked List
모든 빈블록들을 linked list로 연결시킨다.
빈 블록 a에는 다음 빈 블록 b의 정보가 포함되어 있어서 링크되도록 한다.
성능 면에서 효과적이지 않다.
빈 블록을 찾으려면 일일이 링크를 따라가야 하기 때문이다.
중간 빈 블록에 문제가 생기면, 링크가 중간에 끊기면 뒤 빈 블록을 찾을수없으므로 reliability 문제가 있다.
3) Grouping
linked list를 보완한 기법이다.
블록 하나의 크기는 1kb, 4kb이다.
block number 표현하는 것은 4byte면 되는데, 대부분 block size는 4kb 이다.
이 경우 한 block안에 block number는 1024개나 들어갈 수 있다.그런데 한 블록당 공간을 4byte 하나만 사용한다? 공간의 낭비다!
빈 블록의 번호들을 한 블록에 여러개 넣는다. 마지막 블록 번호를 따라가면, 또 다른 빈 블록에 여러개의 빈 블록 번호들이 있다.
따라서 grouping 역시 linked list이지만, 한 블록이 빈 블록 넘버 하나만 가진것이 아니라 n개의 빈 블록 넘버를 가지고 있는 것이다.
따라서 한 빈 블록만 읽어들이면, 여러개의 빈 블록 번호를 알 수 있다는 것이다. n개의 빈 블록 번호 중 n-1개는 실제로 free한 빈 블록일 뿐이고, 마지막 1개는 다른 빈 블록들의 번호를 가진 반 블록이다.
🌳 UFS
유닉스 파일 시스템에서는 Grouping기법을 사용한다.
파일 시스템의 mount가 이뤄지면, 해당 파일 시스템의 super block을 메모리로 읽어들인다.
해당 파일 시스템을 사용할 수 있게 되면 super block이 메모리에 올라오고, 시스템이 unmount될 때까지 계속 메모리에 유지된다.
superblock안에 빈 블록 번호들을 여러개 유지하는 공간이 있다.
그리고 이 공간이 부족하면, 마지막 블록을 다른 빈 블록의 번호를 저장해두어 그 번호를 따라가면 빈 블록들이 저장된 빈 블록이 나오게 된다.
4) Counting
빈 블록 a에서는 연속으로 1개, 빈블록 b에서는 연속으로 3개, c에서는 연속으로 2개가 비어있다고 저장하는 것.
[(a,1),(b,3),(c,2), .. ]
즉, 첫 빈 블록의 주소와 그 뒤 연속적으로 빈 블록의 개수 n을 저장하는 기법이다.
따라서 연속적인 빈 블록을 할당하고 반납하는 과정에서 매우 효과적이다.
