매체에 따라 순차적인 접근, 직접 접근 방식이 있었다. 하지만 데이터 관리 방법에 따라 순차접근만 가능한 경우도, 직접접근만 가능한 경우도 있다.

디스크에 파일의 데이터를 저장하는 방법은 세가지 방법으로 나눠볼 수 있다. 파일의 크기는 균일하지 않다. 디스크에 다가 파일을 저장할 때는 동일한 크기의 섹터 단위로 나눠서 저장한다. 파일 시스템이라던지 디스크 외부에서 볼 때는 동일한 크기로 저장한 단위를 논리적인 블럭이라고 한다. 즉, 어떤 임의의 크기의 파일을 동일크기의 블럭 단위로 나누어서 저장하고 있는데, 이것은 메모리 관리에서 페이징 기법과 유사하다.

Contiguous Allocation

디스크 상에 연속해서 저장되는 방법이다. 블럭 두개로 저장되는 것은 첫번째 블럭과 두번째 블럭으로 인접하게 저장된다. 디렉토리 파일은 디렉토리 밑에 있는 파일들의 메타데이터를 내용으로 한다고 했었다. 따라서 디렉토리 밑에 지금 파일의 이름들이 있고 메타 데이터도 start, length를 가지고 있는 것을 볼 수 있다. 연속적으로 저장되기 때문에 시작 위치와 길이를 가지고 있는것이다.
list라는 파일은 28번 부터 길이가 4로 연속해서 할당된 것을 알 수 있다. 이러한 할당 방법의 장점과 단점을 알아보자

장점

• Fast I/O
  - 특히 HDD 같은 매체는 대부분의 접근 시간이 헤드가 이동하는 시간이다. (바깥쪽 트랙에서 안쪽 트랙으로 이동)
  • 어떤 파일을 통째로 찾고 싶을 때 한번의 seek/rotation으로 가져 올 수 있는 것이다. start만 찾으면 연속적으로 찾으면 되기 때문에 (물론 데이터가 모두 같은 트랙에 있다는 가정하에)
  • file system용도 말고 swap area용(파일을 저장하는게 아니라 프로세스의 주소공간 중 일부를 물리적인 메모리에서 쫓아내고 나중에 필요할 때 올려놓기 위해 사용되는 곳)
  • swap area는 임시로 저장해놓고 프로세스의 주소공간 (대용량의 크기)를 빠르게 쫓아냈다가 빠르게 올려야하므로 공간 효율성 보다는 속도 효율성이 높은 데이터에 속한다. 디스크를 많이 차지 하더라도 금방 지워질 것이기 때문에 연속할당이 효과적이다.
  • Realtime file
• Direct access 가능
  - 앞에서 부터 5번째 블럭을 보고 싶을 때 앞의 네개의 블럭을 다 봐야 하는가 ? 그렇지 않다. start에서 연속적으로 나열되어 있기 때문에 start에 보고싶은 index를 더해서 블럭을 확인하면 된다.
  

단점

• external fragmentation
  내용이 들어있지 않은 블럭들이 있을 때 새로 들어오는 파일의 크기와 맞지 않을 때 비어있는 공간임에도 활용되지 못한다.
• 파일을 수정하면서 크기가 커질 수 있다. 하지만 인접한 비어있는 블럭에 따라 file의 크기가 커질 수 있는 제약이 있다.
  • 파일 생성시 얼마나 큰 hole을 배당할 것인가?
  • 커질 것을 대비해서 빈 공간을 미리 확보 - 지금은 길이가 3이지만 길이가 5까지 커질것을 대비 해서 5까지 할당 => 5까지만 커질 수 있지 더 커지긴 힘들다
  • 또한 미리 할당하는 것이므로 당장 사용되지 않기 때문에 내부 조각이 발생할 수 있다
    미리 할당하면 낭비될 수 있고, 미리 할당하지 않으면 커질 때 문제가 생길 수 있음

Linked Allocation

파일의 데이터를 연속적으로 배치하지 않고 비어있는 곳이면 들어가도록 하는 것이다. start에서 시작 -> 9번에 가면 두번째 데이터가 어디있는지 적혀있다. 따라서 각각의 블럭에 다음 블럭이 어딘지 적혀있음
마지막 블럭에는 끝났다는 표시를 해놓는다.
시작 위치만 디렉토리가 가지고 있고 그 다음 위치는 파일에 가봐야 알 수 있다.

장점

• 외부조각이 발생하지 않는다.
  - 아무곳이나 들어가면 되기 때문에

단점

• 직접접근이 불가능하다.
  - 4번째 블럭이 보고 싶다면 첫번째 블럭부터 가서 순차적으로 위치를 찾아 4번째 블럭을 찾아야한다. 즉, 건너띄는 것이 불가능하다.
  • 순차접근만 가능하다.
• 위치가 떨어져있기 때문에 disk가 seek를 계속 해야 되기 때문에 시간이 많이 든다.
• Reliability
  - 섹터들이 bad sector가 날 수 있다. sector가 1000개가 될 때 그 중 하나만 bad sector가 나면 그 뒤에꺼는 다 놓치므로 데이터가 유실될 수 있다.
• Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
  - 512bytes/sector, 4bytes/pointer
  • 디스크에 데이터를 접근하는 단위가 512의 배수 -> 하나의 섹터에 512에서 포인터를 위해 4바이트가 소요되면 512-4 바이트에 데이터가 들어갈 수 있다.
  • 하지만 보통 512 바이트로 데이터를 저장하라고 하기 때문에 하나의 섹터에 저장될 데이터가 포인터때문에 밀린다.

변형

• File allocation table(FAT) 파일 시스템
  - 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

Indexed Allocation

직접접근이 가능하게 하기 위해서 디렉토리에 파일의 위치 정보를 바로 저장하는 것이 아니라 인덱스를 가리키도록 한다. index 블록은 내용이 담여 있는 것이 아닌 위치 정보를 열거 해놓은 정보를 담아놓는다. 따라서 총 5개의 블럭으로 구성되는 것을 확인할 수 있다. 따라서 jeep 파일의 4번째 블록을 보고 싶으면 index 블록을 살펴 4번째 블록에 바로 접근할 수 있다.

장점

외부조각이 생기지 않으면서 직접접근 가능

단점

아무리 작은 파일이라 하더라도 블럭이 두개 필요하다.
index를 위한 블럭, 실제 데이터 블럭
따라서 small file의 경우 공간 낭비 -> 실제로 많은 file들이 small
굉장히 큰 파일의 경우 하나의 index 블럭으로 파일의 모든 index를 표현하지 못한다.
해결방안

• linked scheme : index 블럭에 실제 파일의 위치가 어딘지 적다가 끝까지 갔는데 커버 못하면 끝에 또다른 index 블럭의 위치를 표시
• multi-level index : 하나의 인덱스 블럭이 직접 파일의 위치를 가리키는 것이 아니라 2단계 page table을 사용하던 것처럼 인덱스가 데이터의 위치가 아닌 다른 인덱스 테이블을 가리키도록 하는 것이다. 따라서 공간낭비가 있을 수 있다.

파일을 디스크에 저장하는 방법 세가지에 대해 알아보았다. 이러한 방법들은 이론적으로 할당이 가능하다는 것이고, 실제 파일 시스템에서는 어떤 할당 방법을 어떻게 변형해서 사용하는지 알아본다.

UNIX의 파일 시스템 구조

• Boot block
  unix 파일시스템 뿐만 아니라 어떤 시스템이던 제일 앞에 나오는 것이 약속이다. 컴퓨터 전원을 키면 부팅을 해야한다. 어떤 파일시스템이던 0번 파일을 올려 부팅한다. 따라서 부팅에 필요한 정보가 있다.
• super block
  파일시스템에 관한 총체적인 정보를 담고 있다. 어디가 빈블럭이고 어디가 실제로 파일이 저장된(사용중인) 곳인지, 어디까지가 Inode list인지 등을 관리해준다.
• Inode list
  file의 metadata는 그 파일을 가지고 있는 디렉토리에 저장되어있다고 배웠다. 하지만 디렉토리가 모든 메타데이터를 가지고 있는 것이 아니라 일부만을 가지고 있는데, 실제 파일의 메타데이터들은 별도의 위치에 빼서 보관한다. 이 위치가 Inode list이다. 빨간 색으로 표시된 inode가 파일 하나에 하나씩 할당된다. 또한 메타데이터를 담고 있는 것을 확인할 수 있다. 유의ㅈ할 점은 inode는 파일의 이름을 가지고 있지 않는다. 파일의 이름은 directory file에 있으며 파일 이름 | inode 번호로 저장되어 있다.
  파일의 위치정보는 indexed allocation을 변형해서 사용하고 있다. 각 파일당 inode의 크기는 정해져있다. 따라서 위치를 나타내는 포인터들의 개수도 한정적이다. 이러한 한정적인 포인터로 큰 파일도 나타낼 수 있어야한다. UNIX에서는 direct blocks, single indirect, double indirect, triple indirect 로 파일의 위치정보를 관리한다. 파일의 크기가 굉장히 작다면 direct blocks만을 가지고 위치정보를 나타내고 파일이 크다면 indirect를 이용한다.
• data block
  파일의 실제 내용을 보관 (directory file - 파일 이름 | inode 번호)

FAT File System

-FAT
파일의 메타데이터 중 일부(위치 정보)를 FAT에 보관, 나머지는 directory가 가지고 있는다.
심지어 파일의 시작 위치 또한 가지고 있다. Linked allocation에서 bad sector가 있을 때 데이터가 유실될 수 있고, 512 바이트를 모두 활용하지 못한다는 단점이 있었다. FAT은 이를 보완하기 위해 위치 정보를 file내에 저장하는 것이 아니라 FAT이라는 별도의 공간을 활용해 관리한다. FAT의 배열의 크기는 디스크가 관리하는 data block의 개수만큼이다. 배열에는 숫자를 하나 담을 수 있는데, 그 숫자는 해당 블럭의 다음 블럭이 어디 있는지 담고 있다. 따라서 처음에 217번을 보고 다음 블럭을 찾고 싶다면 FAT을 보면 된다. EOF는 파일의 끝을 나타내는 것이다.
Linked allocation을 적용했으나 FAT을 이용해 직접접근이 가능하다. 기존에는 순차적으로 파일들을 찾아 seek를 매번했어야했다. 하지만 FAT을 메모리에 올려놓고 쭉 따라가면 곧바로 해당 파일의 위치를 파악할 수 있다. 디스크에서 2번째, 3번째 파일을 봐야만 알 수 있는 것이 아니다.
Reliability 문제도 해결했는데, 포인터 하나가 유실되더라도 data block과 분리된 FAT에 위치 정보가 있다. 따라서 FAT은 굉장히 중요한 정보를 가지고 있으므로 보통 2copy 이상을 가지고 있어 reliability를 해결할 수 있다.

Free-Space Management

비어있는 블럭을 어떻게 관리할지 알아보자

Bit map or bit vector

각각의 블럭별로 번호가 있다. 따라서 각각의 번호에 bit를 통해 block이 사용중인지를 표시한다. 따라서 bit[i]가 0이라면 i번째 블럭은 빈 블럭이고, bit[i]가 1라면 i번째 블럭은 차있는것이다. bit map의 크기는 블럭의 크기와 같다.

• Bit map은 디스크에 부가적인 공간을 필요로 한다. -> 하지만 많은 공간이 필요하진 않다.
• 연속적인 n개의 free block을 찾는데 효과적이다.
  • 연속할당은 쓰진 않아도 연속으로 비어있는 곳에 넣는 것이 좋다.

Linked List

비어있는 블럭들을 연결해놓는 것이다. 비어있는 블럭이기 때문에 다음에 비어있는 블럭이 어디인지 포인터를 저장할 수 있다. 따라서 다음 빈 블럭을 알기 위해선 해당 블럭을 봐야한다. bit map에 비해 추가적인 공간을 필요로 하지 않는다는 장점이 있으나, 연속적인 가용공간을 찾기 어렵다.

Gouping

linked list방법의 변형
첫번째 free block이 n개의 pointer를 가짐
- n-1 pointer는 free data block을 가리킴
- 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐
비어있는 블럭을 한번에 찾기는 효율적이나, 연속적인 빈 블럭을 찾기에는 효율적이지 못함

Counting

연속적인 빈 블럭들을 표시하기 위해서 첫번째 빈 블럭의 위치와 해당 위치 부터 연속적으로 빈 블럭의 수 또한 가지고 있다.

Directory Implementation

Linear list

• <file name, file의 metadata>의 list
• 구현이 간단
• 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search가 필요

크기를 고정해놓고 관리

Hash table

파일의 이름을 그냥 저장하는 것이 아닌 hash 함수를 적용해서 저장하는 것이다.

• linear list + hashing
• Hash table은 file name을 이 파일의 linear list의 ㅊ위치로 바꾸어줌
• search time을 없앰
  - 순차적 탐색이 아닌, file 이름을 해시함수를 적용해 해당 엔트리만 확인하면된다.
• Collision 발생 가능
  - 서로 다른 파일 이름에 대해 같은 값으로 매핑되는 현상

File의 meatadata의 보관위치

• 디렉토리 내에 직접 보관
• 디렉토리에는 포인터를 두고 다른 곳에 보관
  - inode, FAT 등

긴 파일 이름을 지원하는 방식
metadata의 크기는 한정적이다. 하지만 file의 이름은 그렇지 않다. 몇 byte로 제한하는 등의 방법을 사용할 수 없기 때문이다.

• <file name, file 의 metadata>의 list에서 각 entry는 일반적으로 고정 크기
• file name이 고정 크기의 entry 길이 보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
• 이름의 나머지 부분은 동일한 directory file의 일부에 존재
  (앞부분은 저장하다가 벗어나면, 파일의 끝에서 부터 거꾸로 저장되도록 하는것이다. )
  

VFS and NFS

Virtual File System(VFS)

파일시스템의 종류가 많다. 사용자가 파일시스템을 접근할 땐 system call을 해야한다. 이때 file system 별로 다른 system call interface를 사용해야 한다면 사용자가 굉장히 혼란스러울 것이다. 그래서 보통은 어떠한 파일 시스템이 실제로 사용되던 상관없이 개별 파일 시스템 윗 계층에 virtual file system interface를 둔다. 그래서 사용자가 파일 시스템에 접근할 때는 파일시스템의 종류와 상관없이 VFS를 사용하는 것이다.

• 서로 다른 다양한 file system에 대해 동일한 system call interface(API)를 통해 접근할 수 있게 해주는 OS 의 layer
  

Network File System (NFS)

• 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
  • 로컬 스토리지에 있는 파일에 접근할수도 있지만 원격 저장소에 저장되어있는 파일에 접근하고 싶음
• NFS는 분산 환경에서의 대표적인 파일 공유 방법

client, server 컴퓨터가 network로 연결되어있다. client가 VFS를 통해 file system에 접근한다. 이때 접근하는 것이 로컬 스토리지에 있는 것 뿐만아니라 원격 저장소에 있는 것에도 접근할 수 있는 것이다.
client가 요청 -> 내 로컬 스토리지에 있는 것이 아님 -> NFS client 발동 -> 네트워크를 통해 server 연결 -> VFS를 통해 접근

NFS를 지원하려면 server, client쪽에 모두 NFS 모듈이 있어야하고 같은 약속을 해야한다.

Page Cache and Buffer Cache

Page Cache

• virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
  - 사용하는 frame 만 올리고 내쫓기고 하는 것
• Memory-Mapped I/O를 쓰는 경우 file의 I/O 에서도 page cache 사용
  운영체제에게 주어지는 정보가 굉장히 제한적이었다. 이미 메모리에 존재하는 데이터에 대해선 HDD 적인 주소변환만 해서 clock알고리즘 등을 사용했다.
  단위는 page이다.

Memory-Mapped I/O

• File의 일부를 virtual memory에 mapping 시킴
• mapping 시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
  파일을 접근할 때 원래는 open - read/write 시스템 콜, 근데 파일의 일정부분을 메모리영역에 매핑시켜놓고 사용하는 것 -> mapping해놓으면 시스템콜을 하는 것이 아닌 메모리에 변수를 잡아 데이터를 읽고 쓰는 것처럼 사용

Buffer Cache

파일의 데이터를 사용자가 요청했을 때 디스크에서 읽어 사용자에게 전달하기만 하는 것이 아니고, 운영체제에 저장해 다른 사용자가 요청했을 때 운영체제에 저장되어있는 데이터를 전달해주는 것
메모리에 있던 디스크에 있던 CPU 제어권이 운영체제에게 넘어가기 때문에 LRU 등을 사용할 수 있다.

• 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
• File 사용의 locality 활용
  - 한번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전ㄴ달
• 모든 프로세스가 공용으로 사용
• Replacement algorithm 필요 (LRU, LFU등)
  block 단위이다. 보통 512 바이트로 page에 비해 작다.

Unified Buffer Cache

• 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨
• buffer도 page 단위로 관리
• 물리적인 메모리를 관리하는 루틴에 page, buffer 같이
• 공간구분을 하지 않고 똑같이 페이지 단위로 할당해 사용
  - 파일 입출력을 위해 필요 -> page cache를 buffer cache 용도로 사용
  - 프로세스의 주소공간 중 page 필요 -> page cache 사용
  - 그때그때 필요할 때 할당받아 사용
  

I/O without a unified buffer cache

기존의 방식
read/write system call -> 운영체제가 파일 시스템에 있는 내용을 자신의 buffer cache로 옮겨옴 -> 사용자에게 전달 -> 자신의 주소 영역 중 page에 copy해서 사용

memory mapped I/O -> system call -> 자신의 주소 공간 중 일부를 file에 mapping -> mapping을 해도 디스크의 파일을 읽어오는 것은 동일 -> 해당 내용을 page cache에 copy -> 지금부터는 사용자 프로그램이 자신의 page cache에 memory에 읽고 쓰듯이 사용
mapping만 해놓고 memory에 올리지 않으면 page fault가 남 -> 운영체제로 CPU가 넘어감
이미 만약 mapped 된 영역이 주소공간에 올라와있으면 커널없이 사용

둘의 진행방향은 같으나, 운영체제의 도움을 얼마나 받는지 다르다. memory-mapped은 운영체제를 부르지 않고 자신의 주소영역에서 사용하는 것이 장점이다. 어떻게 하던 buffer cache를 거쳐야 함

I/O using a unified buffer cache

공간을 따로 나누어놓지 않고 필요에 따라 할당해서 사용
경로가 더 단순해짐
read/write -> system call -> 운영체제로 CPU 제어권이 넘어감 -> 메모리에 올라와있는 데이터는 copy, 올라와있지 않다면 디스크에서 읽어와 copy 해 전달

memory mapped -> 자신의 주소 영역 중 일부를 file system에 maping -> 사용자 프로그램의 주소영역에 page cache 매핑 -> 한번 더 copy해서 올라가는 것이 아닌 page가 주소영역에 mapping됨

프로그램이 file system에 실행파일 형태로 저장되어 있다가 실행파일을 실행시키면 프로세스가 된다. 프로세스가 되면 프로세스만의 독자적인 주소 공간인 virtual memory가 만들어진다. 주소 변환 HDD 에 의해 virtual 메모리 중 당장 필요한 것은 물리적인 메모리에 올라가고 나머지는 디스크의 swap area에 있는다.

여기서 간과한 것이 code 부분이다. code부분은 메모리에 올라간다음 쫓겨날 때 swap area로 내려가지 않는다. code는 read-only이기 때문에 file system의 실행파일에 저장되어있으므로 swap area에 저장할 필요가 없다.

memory mapped I/O 를 사용하는 대표적인 예제가 실행파일을 실행시켜 생긴 virtual memory의 code 부분이다. file systme의 파일 내용이 그대로 프로세스의 주소 영역에 mapping된 것이다. 만약 이 프로그램이 특정 코드로 접근하는데 메모리에 없다면 swap area에서 올리는 것이 아닌 file system에서 올려 사용한다.

실행 파일 뿐만 아니라 데이터 파일도 file system에 저장되어있다.
B프로그램이 실행되다가 데이터 파일을 memory mapped 형태로 사용하고 싶다면 운영체제에게 해당 데이터 파일을 해당 프로그램의 주소공간에 mapping해달라 요청한다. 운영체제는 mapping해주고 프로그램이 실행되면서 mapping된 곳에 접근할 때 안올라와있다면 page fault가 나 운영체제가 file system에서 읽어와 memory로 올리는 것이다. 이 이후부터 접근할 때는 OS의 도움을 받지 않고 스스로 사용한다. 하지만 이 내용이 쫓겨날 땐 swap area로 쫓겨나는 것이 아닌 file system 에 변경 내용을 쓰고 쫓겨난다.

read/write system call을 통해 사용할 수도 있음 -> memory의 내용을 copy해서 전달
memroy mapped -> memory의 내용을 주소공간에 mapping해서 사용

• 직접 접근 -> 더 빠름
• 한번 더 copy의 오버헤드가 없음
• buffer cache를 mapping 해놓는 것이기 때문에 share해서 사용하면 일관성 문제가 있을 수 있다. read/write는 copy를 해서 사용하므로 일관성 문제는 없다.

출처

Operating System Concepts 10th
KOCW 강의 - [운영체제] 이화여자대학교 반효경 교수