1992.12.29

SUBJECT: Filesystem (block)과 Fragmentation

CONTENTS:
0. Filesystem과 Disk Drive
1. Filesystem block에 대하여 
2. Fragmentation에 대하여 
   1) BSD의 Fragmentation Control 
   2) System V의 Fragmentation Control 
3. 참고 자료

DESCRIPTION:

0. Filesystem과 Disk Drive

   * UNIX 시스템에서 정규 화일이나 디렉토리는 tape drive나 disk drive와 같은
     block device(블럭 장치)에 저장한다.  
     두 장치간의 접근 시간 차이로 인하여, UNIX 시스템을 설치한 곳 중
     filesystem을 위하여 tape drive를 사용하는 곳은 전무하다.
   * 시스템은 여러개의 물리적 disk를 가지며 각 disk는 하나 이상의 filesystem을 갖는다.
     /(root), /usr, /export, /home 등의 filesystem으로 하나의 disk를 분리할 수 있는 것이다.
     disk를 몇 개의 filesystem으로 분할하는 것은 관리자로 하여금 그곳에 저장된 데이터 관리를
     용이하게 해 준다. 
   * Kernel은 논리적 수준에서는 disk가 아니라 filesystem을 다루며,
     각 filesystem을 논리적인 장치번호로 식별되는 하나의 논리적 장치로 취급한다.
     논리적 장치(filesystem)의 주소를 물리적 장치(disk)의 주소로 변환하는 것은
     disk driver에 의해 행해진다.

1. Filesystem block에 대하여 

   - "filesystem block"이란 filesystem이 disk에 언제던지 자동적으로 할당할 수 있는
     데이타의 단위(unit)이다.
   - filesystem은 논리적인 block의 연속으로 구성된다.
     각 block은 시스템의 구현에 따라서 512, 1024, 2048 ... 등 512의 배수의 byte수를 가진다.
      original UNIX는 512 byte의 "filesystem block"을 가졌다.
     System V에서는 512, 1024, 2048 byte의 block size를 지원한다.
     BSD에서는 4, 8, 16, 32 K의 block size를 지원한다.
     SunOS의 경우는 8K(8192 byte)를 한 "filesystem block"으로 사용한다.
   - 논리적인 block의 크기는 하나의 filesystem 내에서는 동일하지만,
     한 시스템 구성 내의 다른 filesystem들 간에는 다를 수도 있다.
   - 큰 논리적 block 사용의 "장점" :
     disk와 memory 사이의 유효 데이타 전송 속도를 증가시킨다.
     왜냐면 한 번의 disk 작동에 의하여 많은 데이타가 전송될 수 있어서 시간을 많이
     소모하는 작업을 줄일 수 있기 때문이다.
     한 번의 읽기 동작에 의하여 1K byte의 데이타를 전송한다면, 
     512 byte를 전송하는 것보다 두 배가 빠른 것이다.
   - 큰 논리적 block 사용의 "단점" :
     유효 저장 용량이 떨어질 수 있다.
     한 화일의 크기가 "filesystem block"의 크기에 미치지 못하는 경우,
     block 내의 남은 부분은 쓸데 없이 낭비되는 것이다. 이를 fragment라 한다.
     실제로 UCB의 한 연구를 보면, 4096 byte의 "filesystem block"를 사용하는 경우
     file들이 block들을 full로 채우지 못해 낭비되는 disk space가 전체 disk의 45%에 달한다고 한다.
     8192 byte를 "filesystem block"으로 사용하는 SunOS나 그 외 BSD 계열의 경우
     이러한 문제를 fragmentation 기법으로 해결하고 있다.
 
2. Fragmentation에 대하여 

   1) BSD의 Fragmentation Control 
      * BSD의 filesystem은 fragmentation 기법을 통하여
        disk fragment로 인한 disk 낭비를 막도록 설계되어 있다.
      * SunOS의 fragmentation을 살펴 보면,
        8192 byte의 block을 1024 byte size인 8 개의 fragment들로 분할한다.
        file size가 늘어나 새로운 space가 필요할 때,
        추가의 block까지 필요 없으면 적절한 갯 수의 fragment만이 할당된다.
        또 두 개의 file이 예를 들어 각각 4개, 3개의 fragment들을 차지하며 한 block에
        공존하고 있다가 어느 한 file의 크기가 늘어나 공존할 수 없게 되면
        크기가 커지는  file을 다른 block으로 옮겨 버린다.
        그러면 동일 file이 어느 한 block에만 fragment를 발생시키지 
        여러 block에 fragment를 만들지는 않는다.
 
                                 Fragment
                                   ↓
                 +---+---+---+---+---+---+---+---+
        Block 1  | A | A | A | A |■ | B | B | B |
                 +---+---+---+---+---+---+---+---+
 
 
                 +---+---+---+---+---+---+---+---+
        Block 1  |■ |■ |■ |■ |■ | B | B | B |
                 +---+---+---+---+---+---+---+---+
                   ↓  ↓  ↓  ↓  ↓
                 +---+---+---+---+---+---+---+---+
        Block 2  | A | A | A | A | A | A |■ |■ |
                 +---+---+---+---+---+---+---+---+
 
 
      * 또한 BSD filesystem의 알고리즘은 filesystem이 full 되면
        free block을 발견하기 위해 극단적으로 느려지게 되는데,
        이를 방지하기 위해 각 filesystem에는 free space를 reserve할 수 있도록 하였다.
        minimum free space는 10 % 이다.
        실제로 "df" command를 사용해 보면 실제 disk 크기에 비해 filesystem의 크기가 작음을
        계산할 수 있다.
      * 이 reserved free space는 "newfs" 나 "tunefs"의 "-m" option으로 조절이 가능하다.
              # newfs -m 12 /dev/rsd0g 
        위 12는 reserve될  free space가 12 percent라는 의미이다.
 
   2) System V의 Fragmentation Control 
      * System V filesystem의 가장 큰 문제점은 fragmentation의 취약성에 있다.   
        시간이 지남에 따라 한 file을 연속된 block에 할당할 수가 없게 된다.
        '사용하지 않은 disk block'인 free block은 여기 저기에 흩트러지게 된다.
      * System V의 fsck는 "-S" option을 사용하여
        disk fragment를 최소화하도록 free list를 재정비할 수는 있다.
        그러나 free list를 최소화하여  fragmentation을 줄이는 방법은 도움은 되지만
        그리 큰 효과를 보는 것은 아니다.
        이미 발생한 fragmentation은 어떻게 할 수 없기 때문이다.
        fragmentation을 완벽하게 제거하는 방법은 고통스럽지만 filesystem을 backup받고
        "mkfs"로 새로운 filesystem을 만들어 backup받은 것을 restore하는 것이다.
        그렇지만 이 방법은 시간이 경과하면 fragmentation이 다시 발생하는 것까지는 어쩔 수 없다.
      * SVR4에서는 dcopy를 제공하며, dcopy는 file이 가지는 fragment 뿐 아니라
        산재되어 있는 free list에 의한 fragment도 해결한다고 한다고 한다.

3. 참고 자료
   * "UNIX의 내부구조 - The Design of the UNIX Operating System"  (홍릉과학출판사) 
      - 2장. 커널 개관 p25,26
   * "System Performance Tuning" (O'Reilly & Associates Inc., 1990, Mike Loukides)
      - 5.3 Planning and Creating Filesystems
   * "Sun System Administration 4.x - Educational Course" (SunEducation. 1990)
      - Module 4. UNIX File System
 

 Created        on Dec. 29 ,1992