각 데이터 블록에 번호가 존재하며, block개수는 byte크기로 존재한다. 이 byte크기를 알면 block의 개수를 알 수 있다.
만약 File C를 요청하면 8번 block부터 8개의 block을 return한다.
- 만약 File A와 B가 삭제되어 각각 5개와 6개의 Free block이 생겼는데, 이 Free block에는 7개 이상의 block을 사용하는 File을 만들지 못한다는 단점이 있다. 보통 CD ROM에서 많이 사용되는 방식이다.
Linked List (Chained) allocation
File B를 읽으려면 1번 block부터 다음 블록번호인 8, 3, 14, 28번을 읽으면 끝난다. 만약 다음 블록번호가 -1이면 끝이라는 뜻이다.
이 방법은 block은 next block(meta data) + data(file data)이므로 2^n byte가 최적인 데이터가 아니며, 14번 block을 찾으려면 File B의 1번 block부터 3번 읽어야 하므로 바로 찾기(random access)가불가능하므로 좋지 않은 방법이다.
physical block에는 다음 block번호가 적혀있으며 파일을 읽을때 이를 Link하여 읽을 수 있다.
Linked List (Chained) allocation Using a Table in Memory
next block pointer만 한곳에 모아 관리하도록 하는 방법
메모리에서 file allocation table을 사용한 chain allcation방법.
FAT(File Allocation Table)
파일을 찾을 때 FirstAddress 번호를 이용해 FAT blocks을 보며 찾는다.
이 방법은 보통 용량이 작고 호환성이 높은 디스크, USB drive에서 이 시스템을 사용한다. 용량이 커지면 FAT table의 크기가 커져서 사용하기 힘들기 때문이다.
Allocated block management - Indexed allocation
Index block(24번)에 데이터 block들의 번호가 적혀있다. File B를 찾을 때 24번 Index block에서 데이터를 읽으면 된다.
하지만 index block을 다 쓰면 하나 더 채용하거나 tree 형태로 만드는 등 해결책이 필요하다.
Design of Unix File System
- 위의 해결책으로 미리고정된 위치에(한곳에)index block을 모아놓았고, 이를 UNIX에서는 I-node blocks라 부른다.
- i-node blocks의 0,1번 블록은 전통적으로 사용하지 않고, i-node에는 Data block번호와 파일의 다른속성까지 모두 기록되어있다.
- i-node에는 이름은 존재하지 않으며 이름은 directory에 존재한다!
UNIX Block Addressing
10개의 data block들이 존재하고 10개가 넘어가면 single, double, triple indirect block을 사용한다. single indirect는 512개의 datablock번호를 기록할 수 있고, double은 512^2, triple은 512^3개의 datablock번호를 기록할 수 있다.
Addressing방법은 나쁘지 않기 때문에 UNIX말고도 많이 사용하는 방법이다.
Directory Entry of FAT File System
파일이름 + 확장자(Extension): 8+3, 각 속성과 First block number, 파일의 size값이 존재한다.
Shared Files
shared file을 가지고있는 file system. shared file은 이름은 서로 다르지만 i-node는 동일하다.link count=1이면 B 또는 C만 link, 2이면 B와 C 둘다 link. b의 경우 둘 다 원본(original)이며 구분이 없다.
Shared Files - Symbolic Link
Symbolic Link File (바로가기 파일, 별도의 파일임)
- 기존 shared file은 백업시 원본파일과 링크파일 모두 백업해야하는데, 원본이 삭제되었을 때 link는 삭제되지않고 그대로 남기때문에 무한루프 현상이 발생할 수 있다는 문제점있어 symbolic link file을 도입하였다.
- File Type을 Link File로 새로 정의한다.(special)
- 바로가기파일로 불리며, 파일의 path가 적혀있다.(pathname O)
- OS가 Link File을 읽으면 pathname을 통해 원본 파일을 읽을 수 있다. 따라서 부작용이 작다.
Log-Structured File System (LFS)
- 파일들이 고정된 위치에 존재하면 수정 또는 삭제시 파일 위치로 가서 동작하는데, 이는 HDD의 헤드가 왔다갔다 동작을 많이 해야하므로 성능이 떨어질 수 있다. 이에 log-structured file system을 도입하였다. (헤드가 있는 위치에서 파일을 옮겨다니면서 적자!)
- segment단위로 기록하며, 각 segment들은 i-nodes와 directory entry blocks, data blocks을 가진다.
- 이 시스템은 변경된 내용, write를writing point부터 순차적으로적는다.
Comparison between LFS and FFS
LFS는 순차적으로 변경된 내용들을 적는 반면, FFS(기존 UNIX 시스템)는 고정된 위치에 변경된 내용을 적는다.
LFS: Cleaning(Garbage Collection)
- 디스크 공간은 무한하지 않으므로 사용하지 않는 공간은 재사용하는것이 필요하다.
- Cleaner라는 background process를 통해 LFS는 log를 돌며 old segment들을 제거한다.
Obsolete blocks: 빈 공간, 3개의 segment에만 데이터가 존재한다.
: live block 데이터만 writing point(오른쪽 3개 segment 시작점)에 기록하면 통째로 앞 공간이 비게되어 이 공간을 나중에 다시 사용할 수 있다.
Journaling File Systems
UNIX에서 file을 제거하면 다음과 같은 경우가 발생한다.
file의 directory가 삭제된다
i-node를 free i-nodes(미사용)로 반납한다.
모든 disk block들을 free disk blocks으로 반납한다.
- 사용하다 전기가 나가면(shut down) 파일 시스템을 체크하여 consistant한 상태를 유지해야한다. (일관성 회복)
- 이는 동작시 log(기록)를 남기는 방법으로 처리하며, 파일 시스템 앞부분에 로그기록을 남길수 있는 부분이 존재한다.
-> 전기가 나가게되면 파일 시스템 전체를 다시 시작하는것이 아닌, 로그기록을 찾아서 필요한 부분만 다시 시작할 수 있다.
Journaling
: file system 구조가 변경되기 전에 Logging하는 방식이다. failure에대한 빠른 복구가 가능하며 NTFS, Linux Ext3 FS, Reiser FS등의 시스템이 존재한다.
Determining Block Size
Large block size
- 작은 사이즈를 넣지 못하므로 낭비되는 공간이 존재한다.
- 성능이 좋다.
- FAT의 entry수나 i-node의 block address list의 수가 적다.
Small block size
- space utilization이 좋다.(공간 사용도 높음)
- 성능이 떨어진다.
- FAT 또는 i-node의 수가 많다.
Disk Space Management Block Size
Disk 공간 활용도는 size가 작을수록 높고(4KB), 성능은 블록 크기가 클수록 커진다. 성능을 중시하는 서버는 8KB도 사용하지만 대부분 4KB를 사용한다.
Free space management
할당되지 않은 Free block을 관리하는 방법은 다음과 같다.
* Bit map (bit vector)
- 0이면 free block, 1이면 할당된 block을 나타낸다.
- contiguous free block들을 찾기 쉽다.
* Linked List
- 다음 freeblock이 어딘지 pointer로 적어둔다. 찾을때마다 읽어야하므로 효율이 떨어진다는 단점이 있다.
* Grouping (Indexing)
- index 블록에 여러개의 free block을 등록하는 방식이다.
Bit map
: free block을 bit map으로 관리하는 방법. 공간 차지를 덜하므로 가장 좋은 방법이다. Bitmap은 extra space를 필요로 한다.
EX)
- Block size = 2^12 bytes (4KB)
- Disk size = 2^30 bytes (1GB)
- N = 2^30 / 2^12 = 2^18 bytes (32KB), 32KB의 bitmap이 존재한다.
++ 연속적인 블록을 가져오기 쉽다!
Linked List
Free block list head는 기록되어있고, 이 헤드블록을 기준으로 linked된 다음 free block들을 읽으며 찾는다.
이 방법으로 free block을 할당하려면 block을 읽고 계속 찾아야하므로 성능이 떨어질 수 있다.
Linked List with Grouping (= indexing)
free block이 다른 free block에 대한 index block역할을 한다. index block list head로부터 다음 index block이 link되어있다.(linked list)
예전의 UNIX가 사용했으며 오래 사용하면 여기저기 흩어져있는 block이 많아지므로 성능이 떨어져 느려질 수 있다.
OS - 04. File systems (1)
File Systems
Requirements for long-term information storage
File & File system
File
- 저장공간에 데이터 저장시 저장되는 가장 기본단위이다.(파일 단위로 저장한다)
- byte들의 연속 (OS는 파일 안의 데이터는 관심없고 byte들의 연속이라 생각한다!)
- 유저에 의해 하나의 단위(single entity)로 취급된다.
- 유일한 path name을 가진다.
- 접근 권한이 존재한다.
File system
파일과 관련된 서비스를 유저에게 제공하는 system software
File Naming
.c .gif .pdf .tex .txt .zip 등등의 파일 확장자를 설정할 수 있다.
File Structure
a: 바이트 순서로 나타낸 파일구조
b: 레코드 순서로 나타낸 파일구조
c: 트리로 나타낸 파일구조
File Types
OS는 실행파일을 제외하고 모든 파일의 내용은 신경쓰지 않는다.
- Text: 프로그램 실행 코드
- Data: 초기화된 데이터
File Attributes(속성)
- Protection: 접근 권한!!
- Record length: file size를 나타내며 항상 존재한다.
- Time of last access / change: 파일이 마지막으로 접근 혹은 변경된 시각
File Access Semantic(접근 방식)
: 대부분의 파일 접근방식. 파일을 순차적으로 접근한다.
- id = open(file)
- pread(id, &buf, from, rwbytes)
: 파일에 번호를 주고 어디서부터 몇 bytes를 버퍼에서 읽어달라고 요청하는 방식
- id = open(file)
- lseek(id, SEET_SET, from)
- read(id, &buf, rwbytes)
: r/w pointer를 세팅하고(lseek), r/w하면 눈에보이지 않는 r/w pointer가 자동으로 증가하며 접근하는 방식
Method 2 방식을 프로세스 안에 쓰레드가 1개만 있을때 예전부터 사용해왔지만, 쓰레드가 여러개가 되면서 하나가 파일을 r/w하면 다른 쓰레드는 그 사실을 모르므로 Method 1방식의 pread가 도입되었다.
File Sharing Semantic
- 여러개의 process가 하나의 파일을 r/w하려 하려면 권한 허용이 필요하다! (아니면 lock이 필요하다)
- 파일을 write했을 때 다른 프로세스에 영향이 가는 시기
UNIX: 즉시 새로운 데이터 반영, Andrew File System(분산시스템, 서버 등): 파일이 closed된 이후에 반영
File Operations
Directory(Folder)
Hierarchical(계층적) Directory Systems
우: 계층적 directory구조. 아래의 파일이 위의 파일을 가리킬 수 없다. (Loop x)
File Name and Path Name
Absolute path(절대경로)
- Root Directory에서 본 path. 절대경로의 path는 항상 unique해야한다!
Relative path(상대경로)
- 현재 작동중인 디렉토리에서부터 본 path
Directory Operations
directory들을 관리하는 System calls.
File System Layout
- MBR: Mast Boot Record, 이곳의 Boot code는 partition table을 보고 Boot Block으로 jump동작을 수행한다.
- disk partition을 4개로 쪼개서 사용하며 Superblock에는 전체 형상정보가 답겨있다.
- Free space mgmt(management)
File allocation methods
어떻게 파일에 할당된 데이터 블록을 관리할까?
- Contiguous allocation(연속적 할당)
: 파일 생성시 블록들이 연속적으로 할당된다.
- Chained allocation: non-contiguous allocation(불연속적)
: 다음 블록을 가리키는 pointer가 포함된 chain으로 block이 연결되어있다.
- Indexed allocation: non-contiguous allocation(불연속적)
: Index block이 파일의 data block list를 가진다.
Contiguous allocation
각 데이터 블록에 번호가 존재하며, block개수는 byte크기로 존재한다. 이 byte크기를 알면 block의 개수를 알 수 있다.
만약 File C를 요청하면 8번 block부터 8개의 block을 return한다.
- 만약 File A와 B가 삭제되어 각각 5개와 6개의 Free block이 생겼는데, 이 Free block에는 7개 이상의 block을 사용하는 File을 만들지 못한다는 단점이 있다. 보통 CD ROM에서 많이 사용되는 방식이다.
Linked List (Chained) allocation
File B를 읽으려면 1번 block부터 다음 블록번호인 8, 3, 14, 28번을 읽으면 끝난다. 만약 다음 블록번호가 -1이면 끝이라는 뜻이다.
이 방법은 block은 next block(meta data) + data(file data)이므로 2^n byte가 최적인 데이터가 아니며, 14번 block을 찾으려면 File B의 1번 block부터 3번 읽어야 하므로 바로 찾기(random access)가 불가능하므로 좋지 않은 방법이다.
physical block에는 다음 block번호가 적혀있으며 파일을 읽을때 이를 Link하여 읽을 수 있다.
Linked List (Chained) allocation Using a Table in Memory
next block pointer만 한곳에 모아 관리하도록 하는 방법
FAT(File Allocation Table)
파일을 찾을 때 FirstAddress 번호를 이용해 FAT blocks을 보며 찾는다.
이 방법은 보통 용량이 작고 호환성이 높은 디스크, USB drive에서 이 시스템을 사용한다. 용량이 커지면 FAT table의 크기가 커져서 사용하기 힘들기 때문이다.
Allocated block management - Indexed allocation
Index block(24번)에 데이터 block들의 번호가 적혀있다. File B를 찾을 때 24번 Index block에서 데이터를 읽으면 된다.
하지만 index block을 다 쓰면 하나 더 채용하거나 tree 형태로 만드는 등 해결책이 필요하다.
Design of Unix File System
- 위의 해결책으로 미리 고정된 위치에(한곳에) index block을 모아놓았고, 이를 UNIX에서는 I-node blocks라 부른다.
- i-node blocks의 0,1번 블록은 전통적으로 사용하지 않고, i-node에는 Data block번호와 파일의 다른속성까지 모두 기록되어있다.
- i-node에는 이름은 존재하지 않으며 이름은 directory에 존재한다!
UNIX Block Addressing
10개의 data block들이 존재하고 10개가 넘어가면 single, double, triple indirect block을 사용한다. single indirect는 512개의 datablock번호를 기록할 수 있고, double은 512^2, triple은 512^3개의 datablock번호를 기록할 수 있다.
Addressing방법은 나쁘지 않기 때문에 UNIX말고도 많이 사용하는 방법이다.
Directory Entry of FAT File System
Shared Files
Shared Files - Symbolic Link
Symbolic Link File (바로가기 파일, 별도의 파일임)
- 기존 shared file은 백업시 원본파일과 링크파일 모두 백업해야하는데, 원본이 삭제되었을 때 link는 삭제되지않고 그대로 남기때문에 무한루프 현상이 발생할 수 있다는 문제점있어 symbolic link file을 도입하였다.
- File Type을 Link File로 새로 정의한다.(special)
- 바로가기파일로 불리며, 파일의 path가 적혀있다.(pathname O)
- OS가 Link File을 읽으면 pathname을 통해 원본 파일을 읽을 수 있다. 따라서 부작용이 작다.
Log-Structured File System (LFS)
- 파일들이 고정된 위치에 존재하면 수정 또는 삭제시 파일 위치로 가서 동작하는데, 이는 HDD의 헤드가 왔다갔다 동작을 많이 해야하므로 성능이 떨어질 수 있다. 이에 log-structured file system을 도입하였다. (헤드가 있는 위치에서 파일을 옮겨다니면서 적자!)
- segment단위로 기록하며, 각 segment들은 i-nodes와 directory entry blocks, data blocks을 가진다.
- 이 시스템은 변경된 내용, write를 writing point부터 순차적으로 적는다.
Comparison between LFS and FFS
LFS: Cleaning(Garbage Collection)
- 디스크 공간은 무한하지 않으므로 사용하지 않는 공간은 재사용하는것이 필요하다.
- Cleaner라는 background process를 통해 LFS는 log를 돌며 old segment들을 제거한다.
: live block 데이터만 writing point(오른쪽 3개 segment 시작점)에 기록하면 통째로 앞 공간이 비게되어 이 공간을 나중에 다시 사용할 수 있다.
Journaling File Systems
UNIX에서 file을 제거하면 다음과 같은 경우가 발생한다.
- 사용하다 전기가 나가면(shut down) 파일 시스템을 체크하여 consistant한 상태를 유지해야한다. (일관성 회복)
- 이는 동작시 log(기록)를 남기는 방법으로 처리하며, 파일 시스템 앞부분에 로그기록을 남길수 있는 부분이 존재한다.
-> 전기가 나가게되면 파일 시스템 전체를 다시 시작하는것이 아닌, 로그기록을 찾아서 필요한 부분만 다시 시작할 수 있다.
Journaling
: file system 구조가 변경되기 전에 Logging하는 방식이다. failure에대한 빠른 복구가 가능하며 NTFS, Linux Ext3 FS, Reiser FS등의 시스템이 존재한다.
Determining Block Size
Large block size
- 작은 사이즈를 넣지 못하므로 낭비되는 공간이 존재한다.
- 성능이 좋다.
- FAT의 entry수나 i-node의 block address list의 수가 적다.
Small block size
- space utilization이 좋다.(공간 사용도 높음)
- 성능이 떨어진다.
- FAT 또는 i-node의 수가 많다.
Disk Space Management Block Size
Free space management
할당되지 않은 Free block을 관리하는 방법은 다음과 같다.
* Bit map (bit vector)
- 0이면 free block, 1이면 할당된 block을 나타낸다.
- contiguous free block들을 찾기 쉽다.
* Linked List
- 다음 freeblock이 어딘지 pointer로 적어둔다. 찾을때마다 읽어야하므로 효율이 떨어진다는 단점이 있다.
* Grouping (Indexing)
- index 블록에 여러개의 free block을 등록하는 방식이다.
Bit map
: free block을 bit map으로 관리하는 방법. 공간 차지를 덜하므로 가장 좋은 방법이다. Bitmap은 extra space를 필요로 한다.
EX)
- Block size = 2^12 bytes (4KB)
- Disk size = 2^30 bytes (1GB)
- N = 2^30 / 2^12 = 2^18 bytes (32KB), 32KB의 bitmap이 존재한다.
++ 연속적인 블록을 가져오기 쉽다!
Linked List
Free block list head는 기록되어있고, 이 헤드블록을 기준으로 linked된 다음 free block들을 읽으며 찾는다.
이 방법으로 free block을 할당하려면 block을 읽고 계속 찾아야하므로 성능이 떨어질 수 있다.
Linked List with Grouping (= indexing)
free block이 다른 free block에 대한 index block역할을 한다. index block list head로부터 다음 index block이 link되어있다.(linked list)
예전의 UNIX가 사용했으며 오래 사용하면 여기저기 흩어져있는 block이 많아지므로 성능이 떨어져 느려질 수 있다.
'cs지식 > 운영체제' 카테고리의 다른 글