1993.1.6

SUBJECT: UNIX의 Filesystem의 구조와 file 종류

CONTENTS
0. Filesystem이란 ?
1. Filesystem의 구조
   1) 일반적인 구조
   2) Sun의 구조
   3) boot block
   4) super block
   5) inode list
2. UNIX의 file 종류
   1) ordinary file(일반 file)
   2) directory file
   3) special file(특수 file)

DESCRIPTION:
0. Filesystem이란 ?
   * 시스템은 '여러개의 물리적 disk'를 가지며, 각 disk는 '하나 이상의 filesystem'을 갖는다.
   * kernel은 논리적 수준에서는 disk가 아니라 filesystem을 다루며,
     각 filesystem을 device number로 식별하는 '논리적 device'로 취급한다.
     'device number'란 /dev 밑에 있는, 예를 들어 /dev/sd0a, /dev/sd0g하는 것을 의미한다.
     "df" command를 수행해 보면 이런 '논리적 device'들이 나타나고 'mount point'로 mount되어
     있음을 보여 준다.
   * file은 어떤 정보의 모임을 지칭하는 것인데 
     일반적으로 file은 보조기억장치(디스크, 테이프)에 보존된다.
     filesystem이란 이러한 file들의 집합이 적절한 형태로 구성되어진 것을 지칭한다.
   * UNIX의 filesystem은 계층적인 tree구조이다.
     그래서 file들이 하나의 level로 되어있지 않고 복수의 level에 속한다.
   * filesystem의 top 즉 level 1 은 'root(/)' 디렉토리이다.
   * 'filesystem의 생성'은 "mkfs(or newfs)"라는 명령어로 만들어 진다.

1. Filesystem의 구조

   0) 한 filesystem은 boot block, super block, inode list, data block의 네 요소로 구성되어 있다.

   1) 일반적인 구조
                  +-------------+-----------------+---------------------+
      Disk drive  |  partition  |    partition    |      partition      |
                  +-------------+-----------------+---------------------+
                                |                 |
                  +-------------+                 +-------------------------------+
                  |                                                               |
                  +------------+-------------+--------------+---------------------+
      Filesystem  | boot block | super block |  inode list  |      data block     |
                  +------------+-------------+--------------+---------------------+
                                             |              |
                                 +-----------+              +-----+
                                 |                                |
                                 +--------+--------+-----+--------+
                                 | i-nofr | i-node | ... | i-nofr |
                                 +--------+--------+-----+--------+

   2) Sun의 구조
      * original UNIX filesystem의 경우,
        처음 filsystem이 만들어졌을 때 생성되는 file들은 인접한 setcor들에 형성된다.
        시간이 지남에 따라 생성되고 지워지고 변경되는 file들은 filesystem 내의
        free block들을 찾아 여기 저기 할당된다.
        또한 free block list에 있는 free block number들도 인접해 있지 않고 여기 저기 산재한
        block number들이 list up 되게 된다.
        결국 file 한 개가 disk 전체 여기 저기에 널려 있는 현상이 발생한다.
      * filesystem의 data 용량이 증가하면서 동시에 fragment가 증가하면서
        한 file의 모든 data block을 seek하는 시간이 오래 걸린다.
        게다가 inode들이 filesystem의 앞 부분에 모여 있음으로 인해
        이런 현상이 더욱 악화된다.
        어떤 경우는 read/write하는 시간 보다도 seek time이 더 걸리기도 한다.
      * 이런 현상을 조금이나 줄여 보려고 BSD에서는  'cylinder group'이라는 알고리즘이 등장한다.

            super block
                 │
      boot block │      first cylinder group              second cylinder group
           ↓    ↓ |--------------------------------|--------------------------------| 
        +-----+-----+----+----+-----+----------------+----+----+-----+----------------+
        |     |     |    |    |     | data block     |    |    |     | data block     |
        +-----+-----+----+----+-----+----------------+----+----+-----+----------------+
                      ↑    ↑   ↑
       backup super block   │   │
                            │ inode table
           cylinder group block

      * Sun의 filesystem은 'cylinder group'을 사용하는
        Berkely Fat Fast Filesystem으로 구현되어 있다.

      * Sun의 경우 한 개의 'cylinder group'은 default 16 cylinder로 구성된다.
        'cylinder group block'은 'cylinder group'을 정의한다.

      * 'cylinder group'을 사용한 filesystem의 특징:
        ① 한 file의 data block들이 분산되는 정도가 줄어듦:
           'cylinder group'을 사용해도 file들의 fragment는 여전하겠지만,
           original UNIX filesystem에서 발생하는
           심각한 scattering 현상은 나타나지 않을 것이다.
           이는 filesystem이 directory와 그에 속한 file들을 동일 'cylinder group'내에
           할당하여 주기 때문이다.
        ② file seek time의 향상:
           한 file의 data block들을 찾을 때 제일 긴 seek라도 16 cylinder를 넘지 않는다.
        ③ large file의 'cylinder group' 독점 방지:
           large file들은 'cylinder group'당 2 Mbyte를 할당하며 여러 'cylinder group'에
           분산시킨다. 
           이는 긴 seek 후에야 단지 2 Mbyte씩을 read/write를 할 수 있게 되는 단점이 생긴다.

   3) boot block
      * filesystem의 시작부에 위치. 전형적으로 첫 번째 sector를 차지한다.
      * Sun의 경우 이 첫 번째 'disk sector - 512 byte disk block'에는 disk label이 들어가고
        그 뒤 '15 disk sector - 15 disk block'에 boot block이 따른다.
        그리고 이 label과 boot block은 8192 byte의 'filesystem block'을 형성한다.
      * boot block에는 OS를 boot or 초기화하기 위한 bootstrap code를 넣을 수 있다.
        이 code는 kernel의 복사본을 memory에 적재하여 이를 수행하는 것이 목적이다.
        이 bootstrap code는 단지 몇 개의 명령으로 구성된 간단한 프로그램일 수도 있다.

      ※ Sun의 경우를 보면, PROM이 boot disk의 boot block에 있는  bootstrap code를 찾게 되고
         bootstrap code의 table에는 root filesystem의 "boot" file block number가 기록되어 있어
         이 block number에 있는  "boot" file을 memory로 load한다.
         이 "boot" file은 filesystem에 있는 kernel(/vmunix, /kernel/unix ...)을 memory로 load하고
         memory의 kernel 시작 번지로 control을 옮겨 kernel의 수행을 시작케 한다.

      * system을 boot하기 위해선 단지 하나의 boot block이 필요하기는 하지만,
        실제 모든 filesystem이 boot block를 가지고 있다.
        하나를 제외한 나머지 boot block들은 비어 있을 것이다.

   4) super block
      * filesystem에 대한 모든 중요한 정보를 저장하는 곳이다.
        super block에 있는 filesystem 상태를 기술하는 여러 field를 보면,
           - filesystem의 크기
           - filesystem 내의 free block 수
           - inode의 list 크기
           - filesystem 내의 free inode 수
           - filesystem 내의 free inode의 list
           - free inode list의 다음 free inode의 index
           - free block list와 free inode list를 위한 lock field들
      * 기타 field들에 대해선  /usr/include/ufs/fs.h 참조.

      ※ filesystem을 mount할 때, superblock을 memory로 copy한다.
      file을 만들고 지우고 하는 모든 동작들은  memory 내의 superblock을 동시에 update한다.
      Sun의 경우 정기적으로 memory의 superblock을 disk의 superblock로 sync한다.
      'filesystem이 깨진다'고 하는 현상(대개 전원이 나감으로 인해 발생한다)은
      일반적으로 memory의 superblock을 disk에 write하려다 OS가 crash를 냄으로서 발생한다.
   
   5) inode list
      * process가 disk의 file을 access하기 위한 도구로 'inode table = inode list'를 이용한다.
      * 어느 한 file이나 directory가 만들어질 경우 그에 해당되는 하나의 inode가 만들어 지고
        그 inode가 inode list에 등록되는데, 이 때 등록된 번호를 'inode number'라 한다.
      * inode 하나는 64 byte의 크기이고, 어떤 file이나 directory에 대한 모든 정보가
        해당 inode에 담겨져 있어 file을 대표한다.
      * 각 filesystem의 root directory의 inode number는 1 이다.
      * 한 inode에 담겨진 내용을 보면 다음과 같다.(Sun의 경우)
        - file type, access mode
        - link된 갯수
        - owner의 UID, GID
        - file의 크기(byte수)
        - file이 마지막으로 access, write되고 inode가 change된 시간
        - 'direct'로  data block을 가리키는 12 pointer의 array
          이는 file size를 96 Kbyte(8192x12/1024)까지 확장할 수 있다.
        - 'indirect' pointer 3 개
          'single indirect' data block은 file size를 96 Kbyte에서 16 Mbyte까지 할당할 수 있음.
          'double indirect' data block은 16 Mbytes에서 32 Gbytes까지 할당 가능함. 
          'triple indirect' data block은 SunOS에서는 사용되지 않음.
        - file에 의해 사용된 physical block의 수
 
      ※ file의 크기와 'inode의 data block pointer'의 관계 
         - file의 최대 크기 : ① + ② + ③ 하면 된다.
              ① 'direct' pointer 12 개 : 8192 x 12 / 1024 = 96 Kbyte
              ② 'single indirect' pointer 1 개 : 8192 x 2048 / 1024 = 16 Mbyte
              ③ 'double indirect' pointer 1 개 : 8192 x 2048 x 2048 /1024 = 32 Gbyte
         - 위 계산에서 2048은 어떻게 나온 것인가 ?
            data 1 block을 가리키는 pointer의 size가 4 byte이기에,
            'indirect' pointer가 가리킨 8192 byte 크기의 data block 1개가 가질수 있는
            4 byte 짜리 pointer갯수는  2048개가 되는 것이다.

2. UNIX의 file 종류

   1) ordinary file(일반 file)
      * 이 file은 OS에 의해 규정된 특수한 구조를 갖지 않는 file을 지칭하는 것으로
        일반적인 data file, program source file등의 'text file'과
        실행 가능한 'binary file'이 있다.
      * 다른 OS에 비해 UNIX의 file은 매우 simple하다.
        ordinary file의 '내용'과 '이름'간에는 아무 연관이 없고,
        각 file 뒤에 확장자를 사용한다면 이는 사용자의 편의일 뿐
        어떤 고정적인 의미를 담고 있는 것은 아니다.
        DOS에서 실행 file의 확장자를 .COM, .EXE, .BAT로 한정해 놓았는데
        UNIX에서는 이런 제한이 전혀 없다.
        따라서 ordinary file에 담겨져 있는 내용으로서 ordinary file이 구별될 뿐
        '모두 동일한 형태의 file로 취급'받는다.
        이처럼 UNIX는 file의 구조를 OS에서 결정하지 않는다. 이 점이 다른 OS와는 다른 점.
      * file명을 주는데 약간의 예외는 있다.
        어떤 프로그램들은 특별한 확장자를 요구하는 경우가 있다.
        예를 들면, 어셈블러는 .s로 끝나는 assembly code를 입력 받아
        .o와 같은 object code를 만들며 linker/loader는 .o 형태의 file을 입력으로 요구한다.
      * 그렇지만 UNIX는 기본적으로 OS의 간섭을 받지 않고
        사용자가 원하는대로 레코드의 구조를 자유롭게 구성할 수 있어
        프로그래머에게는 편리함을 제공한다.
        사용자는 한 file의 내부적 저장 구조에 직접 신경쓰지 않아도 file 조작을 할 수 있다. 
      * UNIX의 file I/O는 각 file이 디스크에 어떻게 저장되어 있는가를 신경 쓰지 않고 
        액세스 되도록 kernel에서  buffering작업을 해 준다.
        이는 file을 단순히 byte로 연결된 형태로 간주할 수 있게 해 준다.
        즉 시스템에서 한 file은 data block으로 나뉘어져 디스크상의 여기 저기에 저장되어 있지만
        사용자에게는 논리적으로 모든 바이트들이 한줄로 연결된 것처럼 보인다.
      * 요약하면, 
        ① file이란 squential하게 or random하게 access될 수 있는 "logical sequence bytes"이다.
        ② file의 구조는 이를 액세스하는 프로그램에 의하여 제어되는 것이지
           OS에 의해 제어되는 것이 아니다.

   2) directory file
      * 디렉토리는 file 이름들의 저장 창고와 같다.
        디렉토리 개념은 DOS와 같은 OS를 사용해본 사용자도 모두 친숙할 것이다.
        왜냐면 UNIX의 file 구조인 트리 형태의 계층적인 구조는 다는 OS에서도 모방을 많이 
        하였기 때문이다.
      * 디렉토리는 각 file의 이름과 그 file 자체를 서로 연결시켜 주는 역할을 하므로
        file 시스템의 전체적 구조를 결정지어 준다.
      * 디렉토리는 많은 file들을 포함하며 또한 마찬가지로 여러 file들을 갖는 서브 디렉토리를
        가질 수 있다.
      * 디렉토리는 ordinary file과 구별되는 개념이지만 읽힐 때는 ordinary file과 똑같이 행동한다.
      * 모든 디렉토리는 적어도 '.'와 '..'라는 file을 가지고 있어야 하는데.
        '.'은 디렉토리 file 자체를 지시하고 '..'은 그 디렉토리의 상위 디렉토리를 나타낸다.
        이들 file들을 이용하여 전체 file 시스템을 루트에서부터 차례로 내려오면서 모든 file을
        탐색할 수 있다.
      * pathname(경로명)
        모든 file은 자신이 속해 있는 디렉토리가 있으므로 어느 한 file을 지정하기 위해서는
        그 file명은 물론 그file이 속해 있는 디렉토리명도 지정해야 한다.
        따라서 file을 지정하기 위해서는 관련 디렉토리명과 file명 그리고 '/'로 이루어지는
        pathname(경로명)이 필요하다.
           - 절대 path
           - 상대 path

   3) special file(특수 file)
      * special file은 UNIX filesystem의 가장 특별한 경우 중 하나임.
        UNIX는 'file의 개념'을 시스템에 연결되어 있는 '주변장치에까지 확장'시킨다.
        printer, disk, tape, main memory 등과 같은 주변장치들은 file 구조상의
        file 이름으로 나타난다.
        즉 각각의 I/O device는 적어도 하나의 special file에 연결된다.
      * special file은 ordinary file과 달리
        관련 device를 구동하여 데이타를 read/write할 수 있도록 하는  channel을 형성해 준다. 
        device driver와 연결해 주는 special file로 /dev밑에 있음.
        system의 모든 input/output(I/O)는 /dev directory를 통해 이루어(channel)된다.
      * "mknod" command로 special file을 만듦. 

   4) socket(BSD)
      * process간에 communication을 빠르고 신뢰성 있게 수행해 준다.
        UNIX에는 여러 종류의 socket들이 있지만 대부분 'network'을 경유하여
        서로 다른 host간 process를 connection해 주는데 사용된다.
        물론 single host의 process간 non-network communication을 위해서도 사용 가능하다.
      * socket은 특정 host에 local하게 있으면서
        'network port'보다는 filesystem object를 통해 참조된다.
      * 비록 socket file은 directory entry로 다른 process들에게 보여지지만
        socket connection에 포함되지 않은 process들은 read/write할 수 없다.
      * socket을 사용하는 유일한 UNIX program은 printing system을 취급하는 것들이다.
      * 'socket이라는 file type'은 4.3+BSD에서만 사용됨.
        SVR4에서도 IPC(interprocess communication)을 위해 socket을 사용하지만,
        이는 kernel 내부에 존재하는 soket이라는 file type이 아니고
        socket function들을 library level에서 제공하는 것이다. 
      * "socket" system call에 의해 생성
        "rm" or "unlink" system call에 의해 지워짐.

   5) Named Pipe(FIFOs - ATT)
      * 동일 host에서 수행되는 서로 관련이 없는 process간에 data를 교환할 수 있게 해준다.
      * "mknod"로 생성

   6) Hard link
      * hard link를 이해하기 위해서는 link의 개념을 우선 이해해야 한다.
      * "link"의 개념: 
        - "link"라는 개념을 이해하는 한 방법은
          filesystem의 directory가 어떻게 계층적으로 구조를 형성하고 있으며
          어떻게 "cd" command로 여러 directory를 이동할 수 있는가를 이해하는 것이다.
        - 각 directory는 기본적으로 최소한 두 개의 file을 가진다.
             ① directory 자신을 표현하는 dot(.)
             ② 자신의 parent directory를 표현하는  dot-dot(..)
        - 이 두 file이 directory들을 연결하여 filesystem의 계층적 구조를 형성한다.
          각 directory의 parent와 sub-directory를 dot(.)와 dot-dot(..) file로 연결 하는 것이다. 
          즉 ① 'current directory의 dot-dot(..) file'의 inode
                = 'parent directory의 dot(.) file'의 inode
             ② 'current directory의 dot(.) file'의 inode
                = 'sub directory의 dot-dot(..) file'의 inode
        - sub directory가 여러 개인 directory의 경우
          sub directory들의 dot-dot(..) file의 inode는
          이들 parent directory의 dot(.) file의 inode와 같을 것이다.
          달리 표현하면, sub directory들의 각 'drectory entry'는
          current directory의 dot-dot(..) file 즉 parenet directory의 inode를 가리키는 것이다.
        - 이처럼 '하나의 inode'에 '여러 개의 (direcory) file'이 '연결(link)'되어 있을 수 있고,
          이처럼 '연결(link)된 갯수'를 'link 갯수'라 한다.
      * hard link란 ?
        - 위에서 directory를 들어 설명한 link의 개념서
          여러개의 (directory) file들이
          한 개의 inode number를 사용해 서로 연결될 수 있음을 보았다.
        - hard link란 이러한 link와 같은 개념이다.
          한 file의 inode에 여러 file들의 inode를 일치시킴으로써
          서로를 연결(link)시키는 방식인 것이다.
        - hard link는 'directory file'의 link 구조를 'ordinary file'로 확장시킨 것이다.
          즉 "ln"이라는 command를 사용하여 'link라는 내부적 표현'을
          실제 (hard) link된 file들로 보여 준다.
        - hard link를 확인할 수 있는 방법은 
          symbolic link처럼 filename에서 확인할 수 있는 것이 아니고, 
          'link 갯수'가 2 이상인가를 확인하고
          inode number가 같은 file을 찾아야 하는 것이다.
        - hard link는 file이 존재할 때만 만들어 질 수 있다.
          즉 inode가 미리 존재하고 있어야 '동일 inode'를 갖는 file을 만들 수 있는것.
        - filesystem을 cross하여 hard link를 형성할 수는 없다.
        - hard link된 file중 하나를 지웠다고 하여 실제 그 file을 지웠다고 할 수 있는 것은 아니다.
          hard link되어 있는 다른 file이 동일 inode를 사용하기 때문이다.
          file을 지웠다 함은 그 file이 사용하고 있는 indoe가 release됨을 의미한다.
         
        
           
   
   7) Symbolic link(BSD)
      * 한 file을 단순히 '다른 이름(pathname)'으로 지시하는 file type이다. 
      * 

  
Revision History
Created        on Jan. 6 ,1993