28. Free Block Management

Disk block을 파일에게 allocation 하려면 가용 가능한 free block이 어떤 것들이 있는지 빠르게 알 수 있어야 합니다. 이런 문제를 Free Block Management라고 부릅니다.

 

 

Free List

 

 

Free list는 이 문제를 해결하기 위한 방법 중 하나로 과거에는 굉장히 단순하게 구현할 수 있어 많이 사용되었지만 이제는 너무 단점이 많아서 거의 사용하지 않습니다. Linked File Structure와 유사하게 free block들을 전부 링크를 달아서 링크드 리스트로 만드는 방법입니다.

 

어떤 파일이 블록 3개를 요구하는 경우 링크드 리스트에서 첫 번째 free block을 따주고 세 번째 블록까지 전달해 줍니다. 이렇게 block by block allocation을 지원해 주는 방법이 Free List입니다. 구조체도 단순하고 구현도 단순하며 free block들의 맨 마지막에 포인터를 이용해서 데이터 구조를 구현하기 때문에 정보를 표시하기 위한 오버헤드 공간이 없습니다.

 

공간 효율적인 방법이지만 블록들을 할당할 때 블록들이 어떤 실린더에 있는지 알 수 없기 때문에 할당 받은 블록들로 sequential accress를 한다면 굉장히 많은 seek time이 발생합니다. 또한 fregmentation 문제도 발생할 수 있습니다.

 

 

Bitmap

 

 

modern OS는 Bitmap 기반의 data structure를 사용합니다. 디스크 스토리지에 존재하는 모든 블록들에 한 비트를 매핑시키고 allocation 되어 사용 중인 블록의 matching bit에 0을 저장하는 방식으로 free block을 구분합니다. 각 블록들의 bit를 연결하면 bit array 구조가 될 것입니다. 이 array를 bitmap이라고 부릅니다. (별도의 bitmap이라는 정보를 사용하여 overhead가 발생)

 

추가적인 공간을 사용하지만 생각보다 오버헤드가 크지 않습니다. 8k 블록을 1bit으로 표현한다면 압축비가 1:64k 만큼이 됩니다. 64k만큼의 공간을 한 비트로 표현하니 충분히 압축비가 좋은 정보 블록이 되는 것입니다. 이 bitmap을 사용하는 경우 연속적인 블록 할당을 쉽게 할 수 있습니다. (1이 20개 연달아 있는 패턴을 찾아서 할당하면 됩니다.)

 

단점으로는 추가적인 정보 저장을 위한 오버헤드가 필요하다는 점과 bitmap을 통해 extent based allocation을 진행할 시 fregment가 발생할 수 있습니다. (연속 할당 시), 저장장치의 크기가 점점 커지는 추세인데 이러면 bitmap의 크기도 점점 커지는 문제가 발생합니다.

 

 

 

이런 단점들을 고려하여 변형된 bitmap 기법들이 제안되고 있습니다. 대표적인 방법이 이런 bitmap을 여러 개의 파티션으로 나눈 뒤 각 파티션 별로 available free block의 개수를 저장하는 것입니다. 그 뒤 어떤 파일 리 디스크 블록을 요청했을 때 bit search를 진행하게 됩니다.

 

 

Performance

 

 

파일 시스템에서 퍼포먼스를 잘 관리하는 일은 중요한 문제입니다. 메모리 계층 구조(memory hierarchy) 상에 존재하는 메모리 소자들의 성능은 위 사진과 같습니다. 디스크의 경우 액세스 시간이 큰 것을 볼 수 있는데 이는 seek delay 때문입니다. 그래서 DRAM의 액세스 시간이 1이라고 한다면 디스크 액세스 시간은 십만 배 더 느립니다.

 

만약 스토리지 액세스를 최적화하지 않아서 매번 디스크 액세스를 하게 된다면 일반 사용자들이 사용할 수 없을 정도의 성능이 나쁜 컴퓨터 시스템이 될 것입니다. 

 

 

 

최적화하기 위한 방법을 생각해본다면 첫 번째로 디스크로 가는 액세스의 수를 줄이는 방법, 대표적으로 메인 메모리에 캐시를 두는 방법을 생각해 볼 수 있습니다. (buffer cache, inode cache, page cache),  첫 액세스의 경우 캐시 미스가 발생하기 때문에 아무리 오래 걸린다고 해도 디스크로 가야 합니다.

 

이런 문제를 해결하기 위한 두 번째 접근은 seek optimizaiton입니다. 정보들을 가져올 때 연속적인 seek opeartion이 필요 없을 부분에 모아 둔다면 access latency를 많이 줄일 수 있습니다. 

 

 

 

Buffer Cache

 

 

버퍼 캐시의 아이디어는 간단하게 스토리지에 있는 데이터에 in-memory copy를 유지하는 겁니다. storage area에 있는 데이터 블록이 처음 액세스 되었을 때 데이터를 읽은 다음 버리지 않고 일부분을 메모리에 남겨두는 방법입니다. 이런 디스크 블록에 대한 in-memory cache를 unix에서는 buffer cache라고 부릅니다. 

 

 

 

Page Cache

 

 

메인 메모리의 페이지 프레임은 할당되어 사용되는 페이지 프레임과 할당되지 않아 사용가능한 페이지 프레임 이렇게 2개로 나뉩니다. 대부분의 memory management system은  메모리의 일정한 양의 free page frame을 유지합니다. 이때 아직 사용되지 않은 free page를 이용해서 디스크 블록에 대한 캐시를 사용하는 것입니다.

 

프로세스의 개수가 많아져 페이지 프레임의 필요한 경우에만 강제로 뺏는 방식으로 동작합니다. 정리하자면 page cache의 핵심은 user process가 사용하는 페이지 프레임과 buffer cache가 사용하는 페이지 프레임을 같이 혼용해서 사용하고 대신 프로세스의 memory management는 영향을 주지 않는 것입니다.

 

 

 

Inode Cache

 

 

어떤 파일의 데이터 콘텐츠를 액세스 하려면 먼저 그 파일의 메타 데이터인 inode를 얻어와야 합니다. inode는 파일의 콘텐츠와 함께 디스크에 있습니다. 디스크에서 inode를 읽고 index를 가져온 다음 데이터 블록을 읽어와야 파일의 데이터에 액세스 할 수 있습니다. 이 과정에서 디스크 블록 액세스 2번이 필요하다는 것을 알 수 있습니다.

 

inode는 빈번하게 사용되기 때문에 캐시로 만들면 hit ratio가 굉장히 높게 나올 것이라고 예상해 볼 수 있습니다. 그래서 파일의 inode를 메인 메모리의 캐시로 구성하는 방법이 inode cache입니다. 여기서도 이전과 같이 inode number를 가지고 빠른 검색을 하기 위해서 해싱 기법을 사용합니다.

 

 

 

Seek Optimization

 

 

seek optimization의 핵심은 한 파일에 디스크 블록들을 allocation 할 때 같은 실린더에 있는 블록에 allocation 하는 것입니다. 이를 위해서 연속적인 디스크 블록들은 전부 하나의 실린더에 들어갈 가능성이 높다 생각하며 접근해야 합니다. 하지만 파일이 생성되고 소멸되고를 반복하다 보면 스캐터 되어 어쩔 수 없이 fregmentation이 발생하게 됩니다.

 

그러면 연속적인 블록 공간을 찾기 힘들게 되는데 이를 해결하기 위해서 사용자들에게 파일 시스템의 공간을 전부 사용하게 하는 것이 아니라 여유 분을 두고 사용하게 하는 것입니다. 10%의 공간을 항상 free 하게 둔다면 빠르게 소진되는 문제를 해결할 수 있습니다.