4장 파일 시스템

　장기 기억 정보 저장소를 위한 세 가지 필수 요구 사항은 다음과 같다.

• 저장소는 매우 큰 규모를 저장할 수 있어야 한다.
• 정보는 그것을 사용하는 프로세스가 종료된 후에도 유지되어야 한다.
• 다수의 프로세스가 동시에 정보에 접근할 수 있어야 한다.

　운영체제가 프로세스 개념을 만들어내기 위해 처리기 개념을 추상화하고 프로세스 주소 공간을 제공하기 위해 물리 메모리를 추상화한 것과 동일하게, 파일(file)이라는 새로운 추상화를 통해 위 요구사항을 만족할 수 있다.
　파일은 프로세스에 의해 생성된 정보의 논리적인 단위이다. 파일에 저장된 정보는 영속적(persistent)이어야 하며, 다른 프로세스의 생성 또는 종료에 영향을 받지 않는다. 파일은 오직 소유자가 명시적으로 삭제할 때만 사라진다.
　파일은 운영체제에 의해 관리된다. 그들을 어떻게 조직화하고, 명칭을 부여하며, 접근하고, 사용하고, 보호하고, 구현하고, 관리하는가 하는 것들은 운영체제를 설계할 때 가장 중요한 주제들이다. 전체적으로 운영체제에서 파일을 다루는 부분을 파일 시스템(file system)이라고 한다.

파일

파일 명칭 부여

　파일은 추상화된 메커니즘이다. 파일은 정보를 디스크에 저장하고 다시 읽을 수 있는 길을 제공한다. 그리고 이러한 작업은 어떻게 그리고 어디에 정보가 저장되고, 어떻게 디스크가 실제 작업을 실행하는 지와 같은 자세한 정보를 사용자가 알지 못하는 상황에서 이루어져야 한다.
　아마 모든 추상화 메커니즘에서 가장 중요한 특징은 관리되는 객체에 이름을 부여하는 것이다. 많은 운영체제는 파일 이름을 두 부분으로 구분하는데, 이 두 부분은 마침표(period)로 나뉘어진다. 마침표 다음에 나오는 부분을 파일 확장자(extension)로 불리며 보통 파일의 종류를 가리킨다. 일반적인 파일 확장자 몇개와 그들의 의미는 다음과 같다.

파일 구조

　파일은 여러 가지 형태의 구조를 가질 수 있으며, 다음과 같이 일반적인 세 가지 후보를 볼 수 있다.

　(a)의 파일은 특별한 구조를 가지지 않는 바이트들의 연속이다. 운영체제가 보기에 파일은 바이트들의 모음이며, 의미의 해석은 사용자 수준 프로그램의 책임이다.
　운영체제가 파일을 바이트들의 연속으로 간주하는 것은 가장 높은 수준의 유연성을 제공한다. 사용자 프로그램은 원하는 것이 무엇이든 파일에 기록할 수 있고 편리한 이름을 붙일 수 있다.
　구조화된 파일을 위한 첫 번째 시도가 (b)이다. 이러한 모델에서 파일은 고정된 크기의 레코드들의 연속이며, 각 레코드는 특별한 형태의 내부 구조를 가진다. 파일이 레코드들의 연속이라는 개념의 중심에는, 읽기 연산은 하나의 레코드를 읽고, 쓰기 연산은 하나의 레코드를 변경하거나 추가한다는 개념이 존재한다.
　(c)구조에서 파일은 트리 구조로 구성된 레코드들을 가지며, 동일한 길이를 가질 필요는 없지만 레코드 내부의 고정된 위치에 키(key) 필드를 가진다. 트리는 키 필드를 기준으로 정렬되어 특정 키에 대한 빠른 검색을 가능하게 한다.
　여기서 기본 연산은, 비록 가능하기는 하지만 “다음” 레코드르 가져오는 것이 아니며, 특정 키를 가진 레코드를 가져오는 것이다. 파일에서 사용자는 시스템에게 키 값으로 특정 키를 가진 레코드를 가져오도록 요구할 수 있으며 파일 내에서 해당 레코드의 실제 위치는 걱정할 필요가 없다.

파일 유형

　많은 운영체제는 여러 유형의 파일을 지원한다.

• 정규 파일(regular file): 사용자 정보를 가지고 있는 파일이다.
  • 위 그림의 모든 파일은 모두 정규 파일이다.
• 디렉터리(directory): 파일 시스템의 구조를 유지하기 위해 사용되는 시스템 파일이다.
• 문자 특수 파일(character special file): I/O 장치와 연관되어 있으며, 터미널, 프린터 또는 네트워크와 같은 문자 I/O 장치를 모델링하기 위해 사용된다.
• 블록 특수 파일(block special file): 디스크를 모델링하기 위해 사용된다.

　정규 파일은 일반적으로 ASCII 파일 또는 이진 파일이다. ASCII 파일은 텍스트 행(line)들로 구성된다. 어떤 시스템의 경우 각 행의 끝은 캐리지 반환(carrage return) 문자에 의해 표현되며, 다른 시스템의 경우 라인 피드(line feed) 문자를 사용한다. 또 다른 시스템의 경우 행의 끝에는 이 두 문자가 모두 존재해야 한다. 각 행이 모두 동일한 길이를 가질 필요는 없다.
　ASCII 파일의 가장 큰 장점은 이들이 별다른 처리 없이 표시되거나 프린트 될 수 있으며, 텍스트 편집기로 편집될 수도 있다는 점이다.
　또 다른 형태의 정규 파일은 이진 파일이며, 이것의 의미는 ASCII 파일이 아니라는 뜻이다. 프린터로 출력하면 이들은 이해하기 어려운 무의미한 정보로 보인다. 일반적으로 프로그램만이 해석할 수 있는 내부 구조체 등을 담고 있다.
　예를 들어 다음 그림의 (a)에 단순한 실행 가능한 이진 파일을 표시하였다.

　기술적으로는 이 파일은 단지 바이트들의 연속일 뿐이지만, 이 파일이 적절한 형태의 포맷을 가지고 있다면 운영체제는 이 파일을 실행 할 수 있다. 이 파일은 헤더, 텍스트, 데이터, 재배치 비트, 심볼 테이블과 같은 다섯 개 조각으로 구성된다. 헤더는 흔히 매직 넘버로 시작하며, 어느 파일이 실행 파일임을 표시하기 위해(실수로 실행 파일이 아닌 파일을 실행하는 것을 방지하기 위해) 사용된다. 헤더의 다음 부분에는 프로그램의 텍스트와 데이터가 존재한다. 이들은 메모리로 적재되며 재배치 비트에 따라 재배치된다. 심볼 테이블은 디버깅 용도로 사용된다.
　이진 파일의 두 번째 예는 아카이브 파일(b)이다. 이 파일은 컴파일 되었으나 아직 연결이 되지 않은 라이브러리 프로시듀어(모듈)들로 구성된다. 각 모듈은 앞부분에 헤더를 가지며 헤더는 이름, 생성 날자, 소유자, 보호 코드, 그리고 크기를 알려준다. 실행 파일과 동일하게, 각 모듈의 헤더는 이진 수로 채워져 있어 이들을 프린트하면 완전히 무의미한 내용이 출력된다.

파일 접근

　초기의 운영체제는 순차 접근(sequential access)이라는 한 가지 종류의 파일 접근을 지원했다. 이러한 시스템에서 프로세스는 파일의 모든 바이트 또는 레코드를 앞부분부터 순차적으로 읽을 수 있지만, 일부분을 건너 뛰거나 순서를 바꿔서 읽을 수는 없었다. 그러나 완전히 되감아서 파일을 다시 원하는 만큼 순차적으로 읽을 수는 있었다. 순차 파일은 디스크가 자기 테이프를 저장 매체로 사용하는 경우 잘 맞는다.
　파일을 저장하기 위해 디스크를 사용하면서 파일의 바이트나 레코드의 순서를 바꿔서 읽거나 위치가 아니라 키 값에 따라 레코드에 접근하는 것이 가능해졌다. 바이트나 레코드를 임의 순서로 읽는 것이 가능한 파일을 임의 접근 파일(random access file)이라 부르며 많은 응용은 이러한 파일을 필요로 한다.
　임의 접근은 데이터베이스 시스템과 같은 많은 응용에 필수적이다.
　어디서부터 읽을 지를 지정하기 위해 두 기법이 사용될 수 있다. 첫 번째 방법으로 모든 읽기(read) 연산마다 파일 내에서 읽을 위치를 지시하는 것이다. 두 번째 방법으로 seek라는 특별한 연산이 현재 위치를 지정한다. Seek 실행 후에, 이러한 현재 위치부터 파일을 순차적으로 읽게 된다.

파일 속성

　모든 파일은 이름과 데이터를 가지고 있다. 이와 별도로 모든 운영체제는 각 파일마다 마지막 변경 날짜와 시간 또는 파일의 크기와 같은 추가 정보를 유지한다. 이러한 추가 정보들은 파일의 속성(attribute)이라 불리거나 또는 메타데이터(metadata)라 불리기도 한다. 이러한 속성들은 시스템마다 매우 다르다. 다음의 테이블은 여러 개의 가능한 속성들을 보여주며, 다른 속성들도 존재할 수 있다.

　기존의 시스템들이 여기 나와 있는 속성을 모두 가지고 있지는 않지만 각각의 속성은 어느 시스템에선가는 사용되고 있다.
　파일의 보호와 관련된 처음 네 개의 속성은 누가 파일에 접근할 수 있는지 또는 없는지를 가리킨다. 몇몇 시스템에서 사용자들은 파일에 접근하기 위해 암호(password)를 제시해야하며, 이러한 경우 암호는 파일의 속성중 하나이다.
　플래그는 비트열 또는 길이가 짧은 필드이며, 어떤 속성을 제어하거나 활성화한다. 예를 들면, 숨겨진 파일은 파일을 나열할 때 보이지 않는다. 아카이브 플래그는 하나의 비트로서 파일이 최근에 백업되었는지를 가리킨다. 백업 프로그램은 이 비트를 끄며, 운영체제는 해당 파일이 변경되면 이 비트를 킨다. 이러한 방법으로 백업 프로그램은 어떤 파일을 백업해야 하는지 알 수 있다. 또한 임시 플래그를 사용하여 파일을 생성한 프로세스가 종료할 때 해당 파일이 자동으로 제거되도록 할 수 있다.
　레코드의 길이, 키의 위치와 길이 필드들은 레코드들이 키 값으로 검색되는 파일에만 존재한다. 이것들은 키를 발견하기 위해 필요한 정보를 제공한다.
　생성시간, 마지막 접근시간, 마지막 변경 시간과 같은 다양한 시간 정보가 유지될 수 있다. 이러한 시간들은 다양한 용도로 사용된다. 예를 들면 소스 파일로부터 오브젝트 파일이 이미 만들어진 후, 해당 소스 파일이 변경되면, 다시 컴파일 해야 한다. 이 경우 시간 필드들은 필요한 정보를 제공한다.
　크기는 파일이 현재 얼마나 큰 지를 가리킨다. 몇몇 구형 메인프레임 운영체제는 파일을 위해 필요한 최대 저장 공간을 미리 예약하기 위하여 파일을 생성할 때 해당 파일이 얼마나 커질 지 지정할 것을 요구하기도 했다.

파일 연산들

　파일은 정보를 저장하고 나중에 검색하기 위해 존재한다. 여러 시스템들은 저장과 검색을 실행하는 다양한 연산들을 제공한다. 파일과 관련된 일반적인 시스템 호출들은 다음과 같다.

• 생성(create)
  • 데이터 없는 파일을 생성한다. 이 호출의 목표는 파일의 생성과 몇 개의 속성 설정을 선언하는 것이다.
• 삭제(delete)
  • 파일이 더 이상 필요하지 않으면, 디스크 공간을 반납하기 위해 제거되어야 한다.
  • 이러한 용도의 시스템 호출은 모든 시스템에서 항상 존재한다.
• 오픈(open)
  • 파일을 사용하기 전에 프로세스는 파일을 열어야 한다.
  • 오픈 시스템 호출의 목표는 시스템이 속성을 검사하고, 파일의 디스크 주소를 메모리로 읽어, 뒤따라 오는 호출들의 파일 접근을 빠르게 하는 것이다.
• 닫기(close)
  • 모든 접근이 끝나면 속성과 디스크 주소는 더 이상 필요하지 않다. 따라서 이들을 위해 내부적으로 사용되는 테이블 공간을 반환하기 위하여 파일은 닫혀져야 한다.
• 읽기(read)
  • 파일로부터 데이터를 읽는다. 일반적으로 “현재 위치”로부터 바이트들이 읽혀진다.
  • 호출자는 얼마나 많은 데이터를 읽을 것인지를 지정해야 하고 또한 그들을 저장할 버퍼를 제공해야 한다.
• 쓰기(write)
  • 데이터를 파일에 기록하며, 일반적으로 “현재 위치”부터 기록한다.
  • 만약 현재 위치가 파일의 끝이면, 파일의 크기는 증가한다. 만약 현재 위치가 파일의 중간이면 기존 데이터 위에 덮어쓰며, 기존 데이터는 영원히 사라진다.
• 덧붙이기(append)
  • 이 호출은 제한된 형태의 쓰기이다. 단지 파일의 끝에 데이터를 추가하는 기능만 제공한다.
• 탐색(seek)
  • 파일의 임의 접근을 위하여 데이터를 어느 위치부터 읽을지 지정하는 기법이 필요하다.
  • 이를 위해 널리 사용되는 시스템 호출이 탐색이며, 탐색은 파일의 특정 위치로 파일 포인터(현재 위치)를 변경한다.
  • 이 호출이 실행되면 데이터는 이제 해당 위치부터 읽혀지거나 쓰여진다.
• 속성 가져오기(get attributes)
  • 프로세스는 종종 작업을 실행하기 위해 파일 속성을 읽을 필요가 있다.
• 속성 설정(set attributes)
  • 몇몇 속성은 사용자가 설정할 수 있고 파일이 생성된 후 변경이 가능해야 한다. 속성 설정 시스템 호출로 이것이 가능하다.
  • 설정 가능한 속성의 예로 보호 모드 정보가 있으며, 기타 대부분의 플래그들이 설정 가능한 속성에 속한다.
• 명칭 변경(rename)
  • 사용자는 종종 파일의 이름을 변경하며, 명칭 변경 시스템 호출로 이를 실행한다.

디렉터리(Directories)

　파일을 관리하고 추적하기 위해 파일 시스템은 일반적으로 디렉터리(directory) 또는 폴더(folder)들을 가지고 있으며, 많은 시스템에서 이들 역시 파일의 일종이다.

단일 레벨 디렉터리 시스템(Single-level Directory Systems)

　가장 단순한 디렉터리 시스템은 하나의 디렉터리에 모든 파일을 담는 것이다. 떄떄로 이 디렉터리는 루트 디렉터리(root directory)라 불리고, 이 경우 하나의 디렉터리만 존재하기 때문에 이름은 아무런 의미가 없다.
　하나의 디렉터리만을 가진 시스템의 예는 다음과 같다.

　여기서 디렉터리는 4개의 파일을 가지고 있다. 이러한 기법의 장점은 단순함과 파일을 빨리 찾을 수 있는 능력이 될 것이다. 이 기법은 전화기, 디지털 카메라, 휴대용 음악 재생기와 같은 간순한 임베디드 장치에서도 종종 사용된다.
　다음은 Two-level Directory System을 보여준다.

　문자들은 디렉터리와 파일들의 owners를 가리킨다. 이는 Single-level Directory Systems보다 user 입장에서는 사용하기 편해진다.

계층적 디렉터리 시스템

　단일 레벨은 단순한 전용 시스템에 적합하다. 그러나 모든 파일들이 한 디렉터리에 존재해야 한다면, 수천 개의 파일을 가진다면 원하는 파일을 발견하기는 매우 어렵다.
　결과적으로 서로 연관된 파일들을 하나로 묶을 수 있는 기법이 필요하다. 여기서 필요한 것은 계층 구조(디텍터리들로 구성된 트리)이다. 이 기법을 이용하면, 자연스럽게 파일들을 그룹으로 묶는데 필요한 만큼의 디렉터리가 존재할 수 있다. 또한 이 기법을 사용하여, 많은 회사의 네트워크에서 볼 수 있듯이 다수의 사용자가 공통 파일 서버를 공유할 때, 각 사용자는 자신만의 루트 디렉터리와 계층 구조를 가질 수 있다. 이 기법의 예는 다음과 같다.

　여기서 디렉터리 A, B, C는 루트 디렉터리에 존재하고, 각각의 디렉터리는 서로 다른 사용자에게 소송되어 있으며, 이들 중 두명의 사용자는 진행 중인 프로젝트마다 하위 디렉터리를 만들어 사용 중이다.
　사용자가 원하는 개수만큼 하위 디렉터리를 만들 수 있는 능력은 사용자가 지신의 작업을 조직화 하도록 해주는 강력한 도구가 된다. 이러한 이유로 현대의 대부분의 파일 시스템들은 이러한 방식으로 조직화되어 있다.

경로 이름

　파일 시스템이 디렉터리 트리로 조직화된다면, 어떤 파일 이름을 지정하기 위해서 두 가지 서로 다른 기법이 사용되고 있다.

• 절대 경로 이름(absolute path name)
  • 각 파일마다 루트 디렉터리부터 파일까지의 경로들로 구성된다.
  • 예를 들면 경로 /usr/ast/mailbox는 루트 디렉터리가 usr이라는 하위 디렉터리를 가지며, 다시 usr은 ast라는 하위 디렉터리를 가지며, 이는 다시 mailbox라는 파일을 가지고 있음을 의미한다.
  • 절대 경로는 항상 루트 디렉터리부터 시작하며 파일 시스템에서 절대 경로는 유일하다.
• 상대 경로 이름(relative path name)
  • 작업 디렉터리(또는 현재 디렉터리)라는 개념과 함께 사용된다.
  • 사용자는 한 디렉터리를 자신의 현재 작업 디렉터리로 지정할 수 있으며, 이 경우 루트 디렉터리부터 시작하지 않는 모든 경로 이름은 작업 디렉터리로부터 상대적인 것으로 간주된다.
  • 예를 들면 현재 작업 디렉터리가 /usr/ast 라고 할 때, 절대 경로가 /usr/ast/mailbox인 파일은 단순히 mailbox라는 상대 경로로 참조될 수 있다.

　몇몇 프로그램은 작업 디렉터리가 어디는 상관없이 특정 파일을 접근할 필요가 있다. 이 경우 항상 절대 경로를 사용해야 한다.
　철자 검사기가 /usr/lib에서 많은 수의 파일을 읽어야 한다면 다른 대안이 존재하는데, 먼저 철자 검사기가 시스템 호출을 통해 작업 디렉터리를 /usr/lib로 바꾸고, open 호출의 첫 번째 인자로 단지 dictionary만을 전달하는 것이다. 이렇게 명시적으로 작업 디렉터리를 바꾸어서 철자 검사기는 디렉터리 트리에서 자신이 어디에 위치하는 지를 알 수 있고, 따라서 상대 경로로 사용할 수 있다.
　각 프로세스는 자신만의 작업 디렉터리를 가지고 있어 작업 디렉터리를 변경하고 나중에 종료하더라도 다른 프로세스에게는 영향을 미치지 않을 뿐 아니라 파일 시스템에 작업 디렉터리 변경에 대한 어떤 흔적도 남지 않는다. 따라서 프로세스는 언제든 필요할 때 작업 디렉터리를 안전하게 변경할 수 있다. 다른 측면에서 만약 어떤 라이브러리 프로시듀어가 작업 디렉터리를 변경하고 자신의 실행이 끝날 때 전에 원래 디렉터리로 되돌아 가지 않는다면, 프로그램의 나머지 부분은 자신의 위치에 대한 가정이 갑자기 파괴되면서 정상적으로 동작하지 않을 수 있다. 이러한 이유로 라이브러리 프로시듀어는 일반적으로 작업 디렉터리를 잘 바꾸지 않으며, 만약 바꾸어야 한다면 되돌아가기 전에 원래 상태로 복구한다. 　계층적 디렉터리 시스템을 지원하는 대부분의 운영체제 시스템에서 각 디렉터리는 “.”과 “..”과 같은 두 개의 특별한 엔트리를 가지고 있으며, “.”은 현재 디렉터리를 가리키며, “..”은 부모 디렉터리를 가리킨다. 다음 UNIX 파일 트리를 살펴 보자.

　어떤 프로세스의 작업 디렉터리가 /usr/ast 라고 하면, 이 때 트리의 위쪽에 도달하기 위해 ..을 사용할 수 있다.

디렉터리 연산

　디렉터리를 다루는 시스템 호출들은 파일과 관련된 시스템 호출보다 시스템들 간에 차이가 많다. 디렉터리 관련 시스템 호출이 어떻게 동작하는지를 알아본다.

• 생성(create)
  • 디렉터리를 생성한다.
  • 시스템에 의해 자동으로 생성되는 “.”과 “..” 엔트리를 제외하고는 생성된 디렉터리는 비어 있다.
• 삭제(delete)
  • 디렉터리를 제거한다. 비어있는 디렉터리만 제거할 수 있다.
  • ”.”과 “..” 엔트리는 제거할 수 없기 때문에 디렉터리가 이들 엔트리만을 가지고 있으면 빈 디렉터리로 간주된다.
• 디렉터리 오픈(opendir)
  • 디럭터리는 읽혀질 수 있다.
  • 디렉터리에 있는 모든 파일 이름을 나열하기 위해 프로그램은 먼저 디렉터리를 연 다음 그 곳에 있는 모든 파일 이름을 읽어야 한다.
  • 디렉터리는 읽혀지기 전에 열려야 하며, 이는 파일을 연 후 읽는 것과 동일하다. (readdir을 하기전에 opendir을 먼저 해야한다)
• 디렉터리 닫기(closedir)
  • 디렉터리를 읽은 후 내부 테이블 공간을 반환하기 위해 닫아야 한다.
• 디렉터리 읽기(readdir)
  • 열러진 디렉터리의 다음 엔트리를 읽어 반환한다.
• 명칭 변경(rename)
  • 파일의 이름이 변경되듯이 디렉터리 이름 또한 변경될 수 있다.
• 링크(link)
  • 한 파일이 하나 이상의 디렉터리에 존재할 수 있도록 하는 기법이다. 이미 존재하는 파일과 (새로운) 경로 이름을 받아서, 새로운 경로 이름이 이미 존재하는 파일을 가리키도록 연결을 생성한다. 이러한 방식으로 동일한 파일이 다수의 디렉터리에서 존재하게 된다.
  • 파일의 i-node에서 카운터가 증가하는데, 이러한 종류의 링크는 떄떄로 하드 링크(hard link)라 불린다.
• 언링크(unlink)
  • 디렉터리 엔트리를 제거한다.
  • 언링크되는 파일이 단 하나의 디렉터리에만 존재하고 있다면 이 파일은 파일 시스템에서 제거된다.
  • 만약 파일이 다수의 디렉터리에 존재하고 있다면, 지정된 경로 이름만 제거되며 다른 경로는 그대로 존재한다.

파일 시스템 구현

　파일 시스템을 구현하는 사람의 경우 파일과 디렉터리를 어떻게 저장하고, 디스크 공간을 어떻게 관리하며, 모든 작업이 효율적이고 신뢰성 있게 실행되도록 만드는 것에 관심을 가진다.

파일 시스템 배치

　파일 시스템은 디스크상에 존재하다. 대부분의 디스크는 하나 또는 그 이상의 파티션으로 분할되어 사용되며, 각 파티션에는 독립적인 파일 시스템이 존재한다. 디스크의 섹터 0번은 MBR(Master Boot Record)라 불리며 컴퓨터를 부팅하는 용도로 사용된다. MBR의 끝에 파티션 테이블이 존재하는데, 이 테이블은 각 파티션의 시작과 끝 주소를 가지고 있다. 그리고 테이블에서 하나의 파티션이 활성(active)으로 설정되어 있다. 컴퓨터가 꺼지면, BIOS는 MBR을 읽어 이를 실행한다. MBR 프로그램은 활성 파티션의 위치를 파악하고, 부트 블록(boot block)이라 불리는 활성 파티션의 첫 번째 블록을 읽은 후 실행한다. 모든 파티션은 동일하게 부트 블록에서 시작하며, 파티션에 부팅 가능한 운영체제가 존재하지 않아도 마찬가지이다.
　종종 파일 시스템은 다음과 같이 몇 개의 항목들을 가지고 있다.

• 부트 블록(Boot block)
  • 부트 블록에 있는 프로그램은 해당 파티션에 존재하는 운영체제의 부트 프로그램을 메모리에 적재한다.
• 슈퍼 블록(Superblock): 파일 시스템에서 가장 중요한 인자들을 가지고 있으며, 컴퓨터가 부팅할 때 또는 파일 시스템이 처음으로 접근될 때 메모리로 읽혀진다.
  • Magic number to identify the file system type
  • 파일 시스템 유형(type), 파일 시스템 내 블록의 개수, 기타 중요한 관리 정보 등이 있다.
• 가용 블록(Free space mgmt)
  • 비트맵 형태 또는 포인터들의 리스트
• I-nodes
  • 파일에 대한 모든 것을 가진다.
  • 대부분의 file system이 사용하고 있다.
• 루트 디렉터리(Root dir)
  • 파일 시스템 트리의 최 상단의 정보를 가지고 있다.
• 기타 다른 디렉터리나 파일들

파일의 구현

　파일 저장 공간을 구현할 때 가장 중요한 문제는 아마 어느 블록이 어느 파일에 속하는지를 추적하고 관리하는 것이다. 이를 위해 여러 운영체제에서 다양한 기법들이 사용된다.

연속 할당
　가장 간단한 기법은 각 파일을 연속된 디스크 블록에 저장하는 것이다. 다음 사진에서 (a)는 연속 할당의 예를 보여준다.

　위 그림은 디스크의 처음 40개 블록을 보여주며, 왼쪽에서부터 0번 블록이 시작한다. 초기에 디스크는 비어 있다. 이 상태에서 파일 A가 디스크에 기록되어, 0번 블록에서부터 시작하여 네 개의 블록을 차지한다. 그리고 파일 A 바로 다음에 파일 B가 기록되며, 세 개의 블록을 차지한다. 각 파일은 새로운 블록부터 저장되기 시작하므로 만일 파일 A가 3과 1/2 블록만을 차지하고 있다면 마지막 블록의 뒷 부분은 낭비된다.
　연속 할당은 두 가지 장점을 가진다.

• 구현하기가 매우 쉽다.
  • 파일이 위치한 블록을 관리하기 위해 숫자 두 개, 즉 파일의 시작 블록과 블록의 개수만 기억하면 되기 때문이다.
  • 시작 블록을 알면 나머지 블록들은 단순한 덧셈에 의해 계산된다.
• 읽기 성능이 매우 뛰어나다.
  • 단 한 번의 동작으로 전체 파일을 디스크에서 읽을 수 있다. 즉, 단 한번의 탐색 동작만이 필요하다.
  • 그 이후로는 더 이상의 탐색이나 회전 지연시간이 필요 없이 데이터를 디스크의 최대 대역폭으로 읽을 수 있다.

　연속할당은 심각한 단점이 있는데, 시간이 흘러갈수록 디스크 공간이 조각난다는 단점을 가진다. 위 그림의 (b)에서 파일 D, F가 삭제되었다. 파일이 삭제되면 그것이 차지하던 블록은 가용(free) 상태가 되어 몇 개의 연속된 가용 블록이 존재하게 된다.(단편화, fragmentation) 디스크는 그림에서 보듯이 파일과 가용 공간 구멍들이 혼합된 형태를 가진다.
　한 경우에 연속 할당이 적용 가능하고 실제로 널리 사용되었는데 바로 CD-ROM이다. 이 경우에는 파일의 크기를 미리 알 수 있고 또한 CD-ROM 파일 시스템을 사용하면서 이 크기는 절대로 변하지 않는다.

연결 리스트 할당
　다음과 같이 디스크 블록들을 연결 리스트 형태로 관리한다.

　각 블록의 첫 번째 워드는 다음 블록을 가리키는 포인터로 사용되고, 블록의 나머지 공간에 데이터를 저장한다.
　연결 리스트 할당은 다음과 같은 장점을 가진다.

• 연속 할당과 다르게, 남아있는 모든 디스크 블록의 사용이 가능하다.
  • 디스크 단편화로 공간이 낭비되지 않는다.
• 디렉터리 엔트리에는 단지 파일의 첫 번째 디스크 블록의 주소만을 저장하면 된다.
  • 나머지는 첫 번째 디스크 블록부터 추적하여 찾을 수 있다.

　하지만 연결 리스트 할당은 다음과 같은 단점을 가진다.

• 파일을 순차적으로 읽는 것은 간단해 보이지만 임의 접근은 매우 느리다.
  • N번 블록을 읽으려면 운영체제는 첫 블록부터 시작하여 n-1번 블록까지 하나씩 읽어야만 한다.
• 블록에서 수 바이트가 포인터를 저장하기 위해 사용되므로 하나의 블록에 저장되는 데이터 양은 더 이상 2의 지수 배가 아닐 것이다.
  • 많은 프로그램들은 2의 지수 배 크기의 블록에 읽거나 쓰도록 작성되어 있어 다소 비 효율적이다.

메모리에 존재하는 테이블을 이용한 연결 리스트 할당
　연결 리스트 할당의 두 가지 단점은 각 블록에 존재하는 포인터를 메모리 내에 있는 테이블에 저장함으로써 제거될 수 있다. 다음은 위의 예에서 테이블을 사용하면 어떻게 될 것인지를 보여준다.

　파일 A는 디스크 블록 4, 7, 2, 10, 12번에 순서대로 저장되어 있으며, B는 디스크 블록 6, 3, 11, 14번에 순서대로 저장되어 있다. 위 그림의 테이블에서 파일의 끝까지 체인을 따라 갈 수 있는데, 체인은 표시자(-1)로 끝나며, 이는 더 이상 유효한 블록이 없다는 것을 의미한다. 메모리 내에 존재하는 이러한 테이블은 FAT(파일 할당 테이블, File Allocation Table)라 불린다.
　이러한 구조를 이용하여, 한 블록 전체를 데이터 저장에 사용할 수 있다. 더욱이 임의 접근이 쉽다. 비록 파일 내에서 특정 오프셋에 해당하는 정보가 저장된 블록을 발견하기 위해 체인을 따라가야 하지만 체인이 메모리에 존재하기 때문에 이들을 따라가는데 디스크 참조가 필요하지 않다. 디렉터리 엔트리에는 하나의 정수 값(시작 블록 번호)만 저장해도 파일 크기와 무관하게 모든 블록의 위치를 알 수 있다.
　이 기법의 중요한 단점은, 이 기법이 잘 동작하기 위해서는 전체 테이블이 메모리에 존재해야만 한다는 점이다. 디스크 크기가 20GB이고 블록의 크기가 1KB일 때, $\frac{20 \times 2^{30}}{1 \times 2^{10}} = 20 \times 2^{20}$개의 physical block으로 이루어져있다(FAT의 개수). $20 \times 2^{20} = 20 \times 1000000 = 20000000$개의 디스크 블록 당 하나의 엔트리가 대응되어, 테이블에는 2천만 개의 엔트리가 존재한다. 각 엔트리는 최소 3바이크를 필요로 하며, 또는 하나의 엔트리를 4바이트로 구성하면 검색 시간을 빠르게 할 수 있다. 따라서 이 테이블은, 시스템이 메모레 공간에 최적화 되었는지 아니면 시간에 최적화되었느냐에 따라, 60MB($20 \times 10^6 * 3$) 또는 80MB의 메모리 공간을 항상 사용해야 한다. 이는 실용적이지 않으며, 명백히 FAT 기법은 디스크 용량이 커지면 이에 잘 대응하지 못한다.(table is proportional in size to the disk: 디스크가 커질 수록 FAT이 커진다.)

I-node
　어느 블록이 어느 파일에 속하는 지를 관리하는 마지막 기법은 각 파일마다 i-node(index-node)라 불리는 자료 구조를 가지는 것이다. 이 i-node는 파일의 속성들과 파일의 디스크 블록 주소를 가진다. 다음은 간단한 예를 보여준다.

　I-node가 주어지면, 파일의 모든 블록을 발견할 수 있다. 메모리 내 테이블을 이용하여 파일 블록들을 연결하는 기법에 비해 이 기법의 가장 중요한 장점은 어떤 파일을 열면(open) 해당 파일의 i-node만 메모리에 가지고 있으면 된다는 것이다. 만약 하나의 i-node가 n바이트를 차지하고, 최대 k개의 파일을 동시에 열 수 있다면, 열린 파일들의 i-node 배열을 저장하기 위해 필요한 전체 메모리 공간은 kn바이트가 된다. 따라서 시스템은 이 정도의 공간만 미리 예약해 놓으면 된다.
　이 배열은 앞에서 설명한 파일 할당 테이블이 차지하고 있는 공간보다 일반적으로 매우 작다. 그 이유는 모든 디스크 블록의 연결 리스트를 위한 테이블은 디스크 크기에 비례하여 커진다. 만약 디스크가 n개의 블록을 가진다면 테이블은 n개의 엔트리를 가져야 한다. 기스크가 더 커짐에 따라 이 테이블은 그에 비례하여 커진다. 반대로 i-node 기법은 동시에 개방되는 최대 파일 개수만큼의 배열을 필요로 한다.
　I-node 기법에서 한 가지 문제가 있다. 만약 i-node에 디스크 블록 주소를 저장할 수 있는 공간이 유한하고 파일의 크기가 이 한계보다 커진다면 위 그림과 같이 i-node의 마지막 주소가 가리키는 블록에 데이터를 저장하지 않고 다른 디스크 블록들의 주소를 넣는 것이다.

디렉터리의 구현

　파일을 열기 전에 파일을 먼저 개방(open)해야 한다. 파일을 열 때, 운영체제는 사용자가 제공한 경로 이름을 이용하여 디렉터리 엔트리를 찾는다. 이 디렉터리 엔트리는 디스크 블록을 접근하는데 필요한 정보를 가지고 있다. 시스템에 따라, 이 정보는 (연속 할당 기법과 같이)모든 파일 블록의 주소가 될 수 있고, (연결 리스트 기법과 같이) 첫 번째 디스크 블록 주소가 될 수 있고, 또는 i-node 번호가 될 수 있다. 모든 경우, 디렉터리의 주기능은 파일의 ASCII 이름을 데이터를 찾기 위한 정보로 매핑하는 것이다.
　이와 밀접하게 연관된 것이 바로 속성을 어디에 저장하느냐 하는 것이다. 모든 파일 시스템은 파일의 소유자나 생성 시간과 같은 파일 속성을 유지하며, 이들은 어딘가에 저장되어야 한다. 가장 손쉬운 방법 중 하나가 이들을 디렉터리 엔트리에 직접 저장하는 것으로 다음 그림의 (a)이다.

　이러한 단순한 설계에서 디렉터리는 고정된 크기의 엔트리들의 리스트로 구성되며, 파일마다 존재하는 각 엔트리는 파일 이름, 파일 속성 구조체, 하나 또는 그 이상의 디스크 블록의 주소 등을 가진다.
　I-node를 사용하는 시스템의 경우, 다른 대안으로 속성은 디렉터리 엔트리가 아닌 i-node에 저장할 수 있다. 이 경우 디렉터리 엔트리는 파일 이름과 i-node 번호만을 저장하므로 더 짧다. 이 기법은 위 그림의 (b)이다.
　파일 이름을 검색할 때 앞에서 뒤로 디렉터리를 순차적으로 검색한다. 극단적으로 디렉터리 길이가 긴 경우, 이러한 순차 검색은 느릴 수 있다. 검색 시간을 빠르게 하기 위한 방법은 다음과 같다.

• 각 디렉터리마다 해쉬 테이블을 사용한다.
  • 파일 이름을 해슁하여 해쉬 테이블 엔트리를 결정한다. 해당 슬롯부터 시작하는 체인을 따라가며 모든 파일 엔트리를 검사하여 원하는 파일 이름이 존재하는지 검사한다. 만약 원하는 이름이 체인에 없으면 해당 파일은 이 디렉터리에 존재하지 않는다.
  • 매우 빠르게 검색할 수 있지만 관리가 훨씬 복잡하다.
  • 디렉터리에 수 백에서 수 천 개의 파일이 존재하는 것이 일상적인 시스템에서만 고려해 볼 수 있다.
• 검색 결과를 캐시에 남겨놓는 것이다.
  • 검색을 시작하기 전에 먼저 파일 이름이 캐시에 존재하는지 검사한다. 만약 존재한다면, 위치를 바로 파악할 수 있다.
  • 적은 수의 파일들에 대해서 대부분의 검색이 요청될 때만 캐시 기법은 잘 작동한다.

공유 파일

　여러 명의 사용자가 하나의 프로젝트를 위해 일할 때, 이들은 종종 파일을 공유할 필요가 있다. 이를 위해서 공유되는 파일들이 다른 사용자에게 소속된 여러 개의 디렉터리에 동시에 나타나면 편리하다. 다음 그림에서, C의 파일 중 하나가 B의 디렉터리에도 존재하는 것으로 표시되고 있다.

　링크(link)라 불리는 작업을 통해 B의 디렉터리와 공유되는 파일이 연결된다. 파일 시스템은 더 이상 트리가 아니라 DAG(Directed Acyclic Graph) 구조를 가진다.
　공유 파일은 편리하지만 몇 가지 문제를 발생시킨다. 만약 디스크 블록 주소를 디렉터리에 기록하는 구조라면, 파일이 링크될 때 그 주소가 복사되어 B의 디렉터리도 디스크 블록 주소를 가진다. 그리고 만약 B 또는 C 중 하나가 파일의 뒷부분에 데이터를 추가한다면 해당 사용자의 디렉터리에만 새로운 블록 주소가 추가될 것이다. 그리고 다른 사용자에게는 이러한 변화가 보이지 않게 되어 결국 공유라는 목표에 위배된다. 이 문제는 두 가지 방법으로 해결이 가능하다.

• 하드 링크(Hard link)
  • 디스크 블록 주소를 디렉터리에 기록하는 것이 아니라 파일과 관련된 다른 조그만 자료 구조에 기록한다.
  • 디렉터리는 단지 이 자료구조를 가리키는 포인터를 가진다.
  • 단점
    • B가 공유 파일을 링크할 때, i-node에는 파일의 소유자가 C로 기록되어 있다. 링크의 생성은 소유자를 변경하지 않고, 단지 i-node에 있는 링크 개수 만을 증가시켜, 얼마나 많은 디렉터리가 해당 파일을 가리키고 있는지 시스템이 알 수 있도록 한다(Count).
    • C가 파일을 제거한다면 문제가 발생한다. 시스템이 파일을 제거할 때 i-node도 제거한다면, B의 디렉터리는 정당하지 않은 i-node를 가리키게 된다.

    

• 심볼릭 링크(Symbolic link)
  • B가 C의 파일을 링크하려고 할 때 시스템은 LINK 유형의 새로운 파일을 만들어서 B의 디렉터리에 위치시킨다. 이 새로운 파일에는 링크하고자 하는 파일의 경로 이름이 기록되어 있다. B가 이 링크 파일을 읽을 때, 운영체제는 먼저 읽고자 하는 이 파일의 유형이 링크(LINK)임을 확인한 후, 파일에 기록된 경로 이름으로 다시 검색을 실행하여 해당 파일을 읽는다.
  • 실제 소유자만이 i-node를 가리키는 포인터를 가지고 있고 이 파일을 링크한 다른 사용자는 i-node 포인터가 아니라 단지 경로 이름만 가지고 있기 때문에 소유자가 파일을 삭제하면 해당 파일은 삭제되고 이후 다른 사용자가 심볼릭 링크로 이 파일을 접근한다면, 시스템은 이 파일을 찾을 수 없기 때문에 이러한 시도는 실패한다.
  • 심볼릭 링크를 제거하는 것은 원 파일에 전혀 영향을 미치지 않는다.
  • 단점
    • 추가적을 상당한 양의 디스크 접근을 필요로 한다.
    • 심볼릭 링크를 위하여 추가로 i-node가 사용되어, 경로를 저장하기 위해 별도의 디스크 블록이 필요하다.
  • 경로 이름에 파일이 존재하는 네트워크 주소를 추가함으로써 전 세계 어느 기계의 파일도 링크할 수 있다는 장점을 가진다.

파일 시스템의 예

UNIX V7 파일 시스템

　이 파일 시스템은 루트 디렉터리부터 시작하는 트리 형태를 가지고 있으며, 추가적으로 링크를 가질 수 있고, 단방향 비순환 그래프를 형성한다. 파일 이름은 최대 14글자까지 가능하다.
　UNIX 디렉터리에는 디렉터리 내 각 파일마다 이와 대응되는 하나의 엔트리가 존재한다. 각 엔트리는 극도로 단순한데, i-node 기법을 사용하여 파일의 기타 정보는 모두 이곳에 저장되어 있기 때문이다. 디렉터리 엔트리는, 다음과 같이 파일 이름(14 바이트)과 파일의 i-node 번호(2 바이트)로 구성된 두 필드만을 가지고 있다. 이러한 구성은 파일 시스템 당 존재할 수 있는 파일의 개수를 64K( 2 Bytes = 16 bits, $2^{16}$ = 64K)개로 제한한다.

　전체적인 구조는 다음과 같다.

　I-node에는 처음 10개의 디스크 주소들이 저장되며, 따라서 파일이 작은 경우 필요한 모든 정보는, 파일이 열릴 때 디스크에서 메인 메모리로 적재되는, i-node에 존재한다. 파일이 큰 경우, i-node에 있는 주소 중 하나가 간접 블록(single indirect block)이라 불리는 디스크 블록의 주소로 사용된다. 이 블록에는 디스크 주소들이 저장되어 있다. 만약 이것으로도 충분하지 않으면 i-node의 또 다른 주소가 간접 블록들의 주소가 포함된, 이중 간접 블록(double indirect block)이라 불리는, 블록의 주소로 사용된다. 각각의 간접 블록은 다시 수백 개의 데이터 블록을 가리킨다. 이것으로도 충분하지 않으면 삼중 간접 블록(triple indirect block)이 사용된다.
　Disk block이 1KB이고 disk address가 4Bytes일 때 위 파일 시스템에서 허용할 수 있는 한 파일의 최대 크기는 다음과 같다.

허용할 수 있는 최대 파일 크기 $= 10 \times 1\mathrm{KB} + \frac{1\mathrm{KB}}{4\mathrm{Bytes}}(= 2^8) \times 1\mathrm{KB} + 2^8 \times 2^8 \times 1\mathrm{KB} + 2^8 \times 2^8 \times 2^8 \times 1\mathrm{KB}$

　파일이 열릴 때, 파일 시스템은 제공된 파일 이름을 사용하여 디스크 블록의 위치를 파악한다. 경로 이름 /usr/ast/mbox가 어떻게 검색되는지 살펴본다.

• 파일 시스템은 루트 디렉터리의 위치를 찾는다.
  • 루트 디렉터리의 i-node는 디스크에서 고정된 장소에 존재한다. 이 i-node로부터 루트 디렉터리의 위치를 파악할 수 있는데, 이 위치는 디스크 상에서 어느 곳이라도 가능하지만 이 예에서는 블록 1이라고 가정한다.
• 파일 시스템은 루트 디렉터리를 읽고, 경로에서 첫 번째 성분인 usr을 검색하여, /usr의 i-node 번호를 찾는다.
  • I-node 번호를 알면 그 위치를 찾는 것은 단순하다. i-node들은 디스크에서 각각 고정된 위치에 존재하기 때문이다.
• /usr의 i-node로부터 이 디렉터리의 위치를 찾은 후 이곳에서 다음 성분인 ast를 검색한다.
  • ast를 위한 엔트리를 찾으면, /usr/ast 디렉터리의 i-node를 찾을 수 있다.
• 이 i-node에서 해당 디렉터리의 위치를 찾은 후, mbox를 검색한다.
  • 이 파일의 i-node를 메모리로 읽어오고, 이 i-node는 파일이 닫힐 때까지 메모리에서 유지된다.
• 총 6번의 disk access를 함

　모든 디렉터리는 “.”과 “..”를 위한 엔트리들을 가지고 있으며, 이 엔트리들은 디렉터리가 생성될 때 만들어진다. “.” 엔트리는 자기 자신 디렉터리의 i-node 번호를 가지며, “..” 엔트리는 부모 디렉터리의 i-node 번호를 가지고 있다. 루트 디렉터리에 있는 ..은 루트 디렉터리 자신을 가리킨다.

UNIX File System

　classical UNIX system의 Disk layout은 다음과 같다.

　이 layout에서는 i-node는 64 Bytes의 크기를 가진다. i-node는 파일의 속성들과 파일의 디스크 블록 주소를 가진다. Data blocks에는 Disk block의 contents가 저장된다.
　다음은 64 Bytes i-node의 structure를 보여준다.