File Management.

Presentation on theme: "File Management."— Presentation transcript:

1 File Management

2 Basic Concepts (1) File Linear array of bytes
File is a named, ordered collection of information 블록 저장 장치에 저장된 연속된 바이트스트림 여기에 저장되는 단위는 바이트 여기서 파일은 바이트들의 나열, (우리가 생각하고 있던 파일인 레코드의 나열 보다 더 추상적임) 순서, 이름이 있다. 여기에 저장되는 단위는 블락

3 Basic Concepts (2) 파일 관리자(File Manager) 운영체제의 일부로써 응용프로그램의 요구를 처리
Storing the information on a device Mapping the block storage to a logical view Allocating / deallocating storage Providing file directories Application Program File Manager Block Storage 어플리케이션에서 생각하는 파일을 블락단위로 변환 시켜주는 일을 함. 파일 매니저에서 Blocks File …. Mapping … Byte-stream (Logical View)

4 Information Structure (1)
운영체제에서는 파일을 바이트 스트림으로 취급함. 응용프로그램에서 필요한 레코드 단위는 파일 매니저에서 바이트를 레코드 단위로 변경해줘야함 운영체제에서는 파일을 바이트 스트림으로 취급하고, 응용프로그램에서는 레코드로 취급하기 때문에 중간에 연결 고리가 필요함.

5 Low Level Files Byte-stream File System
Byte-stream file : 양의 정수로 구성된 Byte Sequence File Position : 파일내의 접근된 현재위치를 나타냄 File Manager를 통해 장치내의 블록들로 사상 Low level files 바이트 스트림 파일 시스템 File Postion 파일이 쓰일 위치, 또는 읽을 곳의 위치를 나타낸다. Read할 때 file position을 지정하는 것이 아니라, 파일 시스템에서 가지고 있다가 read함수가 호출되면 file position에서 읽는 것이다. Int seek()  file position을 원하는 위치로 옮겨주는 함수

6 Byte Stream File Interface (1)
fileID = open(fileName) fileName으로 표시되는 파일을 open 해당 File Descriptor 정보는 fileID에 저장 UNIX Interface (예) int open(char *fname, int flags, int mode) fname : 파일 이름 flags 파일 옵션, 파일을 open할 때 세부 동작을 지정 O_RDONLY(읽기 전용), O_WRONLY(쓰기 전용)… mode : 파일 생성시 접근권한을 설정 사용자 및 파일 접근 방법에 대한 제한 close(fileID) fileID로 표시된 파일을 close UNIX Interface int close(int fd) File descriptor  파일에 관한 요약된 정보를 나타내는 것.

7 Byte Stream File Interface (2)
read(fileID, buffer, length) fileID로 표현된 파일로부터 length길이만큼 buffer (주기억장치)에 읽어 들임 UNIX Interface int read(int fd, void *buffer, int length) Return 값으로 실제로 읽어 들인(Actually Read Bytes) 바이트수가 들어온다 write(fileID, buffer, length) fileID로 표현된 open된 파일에 length길이 만큼 buffer 로부터 file에 기록 int write(int fd, void *buffer int length) Return 값으로 실제로 기록된(Actually Write Bytes) 바이트수가 들어온다 seek(fileID, filePosition) fileID로 표현된 open된 파일에 filePosition의 위치로 Current File Position을 이동 int lseek(int fd, int offset, int whence) whence : SEEK_SET (파일의 처음부터), SEEK_END(파일의 마지막으로부터)…

8 Hard disk의 CHS방식과 Byte-stream
(참고) Hard disk의 CHS방식과 Byte-stream CHS 방식 Hard disk의 각 요소들을 C(Cylinder), H(Head), S(Sector)의 번호로 표기 예) C(1), H(2), S(3)  1번 실린더, 2번 헤드, 3번 섹터 Logical Sector 표기 CHS의 세 번호를 0번부터 차례대로 번호를 붙임 예 (실린더 1024개, 헤드 2개, 섹터 18개인 Hard disk) 0번 논리섹터 (C(0), H(0), S(1)), 1번 논리섹터 (C(0), H(0), S(2))… 18번 논리섹터 (C(0), H(0), S(18)), 19번 논리섹터 (C(0), H(1), S(1))… 블록 1개 이상의 Logical Sector로 표기된 섹터들의 연속된 집합 Byte stream 연속된 블록들로 구성된 집합 정보들을 연속으로 접근 / 기록 가능 Blocks 하드디스크에서는 면에 존재하는 원 한 개를 cylinder라고 한다. Logical Sector 표기(블록들) …. Hard disk CHS 표기 … Byte-stream

9 Structured Files Why Structured Files? 응용프로그램에서의 Record의 사용은 중요
Byte Stream으로 제공되는 가공되지 않은 형식의 Storage Block들을 Record의 Stream으로 전환 기법들 Record-oriented Sequential Files Indexed Sequential Files Inverted Files Databases Multimedia Storage UNIX 시스템에서 응용 프로그램 개발자는 Structured Files를 제공하기 위한 연산들을 직접 구현 몇번째 레코드인가? Raw 형식 : 가공되지 않은 형식의 데이터들의 집합을 의미. 여기에서는 Structured File에서는 데이터들을 쪼개어 Record를 만들고 Field들을 구성하기 전의 단계를 의미 그림 13.5의 message 구조체는 하나의 Mail Record를 나타내며 각 항목은 Field들이다. Inverted Files(역파일): 역색ㅇ인은 레코드의 필드와 주소 또는 필드(보조키)와 기본키의 쌍으로 구성된다

10 Record-oriented Sequential Files
Structured Sequential File: 비부호(non-negative) 정수로 인덱스된 논리 레코드들의 시퀀스 Operations fileID = open( fileName ) close( fileID ) getRecord( fileID, record ) fileID가 가리키는 파일의 현재 위치에서 레코드를 읽음 putRecord( fileID, record ) fileID가 가리키는 파일의 현재 위치에 레코드를 저장함 seek( fileID, position ) fileID가 가리키는 파일에서 지정된 위치로 포인터를 변경함 순차접근장치(Sequential Accessed Device), 임의접근장치(Random Accessed Device) 모두 적용 가능

11 Logical-Physical Record Encoding
Write 과정 논리 레코드를 바이트의 리스트로 변환(Marshal)하는 과정 Marshal : 흩어진 정보들을 일련화된 구조로 정보를 배치 Read 바이트리스트를 역변환(Unmarshal)하여 구조를 재구축 Unmarshal : 일련화된 정보들을 필요에 맞게 재배치 Write (Marshal) … Byte Stream (Device) 논리 레코드 (Memory) Read (Unmarshal)

12 Indexed Sequential File (1)
정보 검색시 탐색시간이 일정치 않음 상호질의 시스템에는 부적합 사용자의 요구에 따라 즉각적이거나 일정한 지연시간 필요  레코드에 Index 필드를 마련하고 별도의 저장소에 Index만을 저장한 Lookup Table을 설치 (빠른 검색 가능) Operations getRecord( fileID, index ) 해당 index가 가리키는 레코드(index field set)을 읽어들임 index = putRecord( fileID, record ) fileID가 가리키는 파일의 지정된 위치에 레코드를 추가한다 추가된 레코드의 index를 결과로 반환한다 deleteRecord( fileID, index ) fileID가 가리키는 파일에서 index가 가리키는 레코드(index field set)을 삭제한다

13 Indexed Sequential File (2)
File (with Index) Index Account # 012345 i 123456 k 294376 … j 529366 965987 Lookup Table 레코드 i j k 키와, 그 키값이 있는 레코드가 몇번째인지 나타나있다. Example (Indexed Sequential File)

14 Inverted File 개요 특징 Index가 아닌 필드로 검색시 기존의 Lookup Table은 무용지물
 검색 효율이 Sequential File과 같아짐 인덱스(색인)키들을 모아 다른 속성으로 군집 형성 다른 속성 : 자주 검색의 대상이 되는 Field (Index  File)의 반대 개념 (File  Index : Inverted) 특징 키 값에 속한 레코드들을 모두 인덱스 만으로 신속하게 검출 검색시 유용하게 사용 Inverted File Lookup Table with Inverted File File 키워드 연결된 수 링크 인덱스 링크 … 1 2 3 논문 #1 (Computer) 논문 #2 (Computer, Programming) 논문 #3 (Programming) … Computer 2 … Programming Inverted file은 주로 검색엔지에서 사용된다. 내용, 제목으로 검색이 가능하다. (Example) Inverted File (인덱스가 아닌 키워드로 검색하는 예)

15 More Abstract Files (1) Database 매우 정교한 인덱싱 메커니즘
Schema : 개발자 또는 사용자에게 종합적이고도 포괄적인 데이터 접근 방법 제공 DBMS(Database Management System) : 개발자나 사용자 없이도 DB관리 기능을 포함 (예 : Automatic Reindexing) DDL & DML DDL (Data Definition Language) : 데이터와 데이터의 관계를 서술하는 언어 DML (Data Manipulation Language) : 데이터의 조작에 사용되는 언어 대표적인 것으로 SQL (Structured Query Language)이 있음

16 More Abstract Files (2) Multimedia Storage 데이터 종류의 다양성 요구 사항 파일 관리자
레코드는 여러 다른 유형의 데이터를 포함 숫자, 문자, 그래픽, 이미지, 사운드… 서식화된 텍스트 한 페이지의 용량 : 0.5 ~ 1KB 동일한 페이지의 이미지: 약 10MB 요구 사항 응용프로그램에서 변환할 수 있는 능력 파일 관리자 다양한 데이터 종류에 대한 합리적인 접근 방법 제공 예) 동영상 데이터(대용량)  블록의 크기를 최대화하여 정보접근을 단순화 텍스트 데이터(소용량, 많은 개수)  여러 개의 파일을 빠른 시간내에 검색 가능하도록 인덱스 필드 추가

17 Implementing Low Level Files
Manage blocks 이용 가능한 블록들의 목록을 유지 전체 가용 블록에 대한 링크드 리스트 이용 블록 상태 맵(Block Status Map)을 이용 파일에 블록 할당 디스크립터를 이용하여 블록 정보를 유지한다 블록의 연속 할당 링크드 리스트 인덱스를 이용한 할당(Indexed Allocation)

18 open() Operation (1) open() 개요 Operation 응용프로그램이 파일을 사용할 수 있도록 연결
파일(장치)  운영체제(File Manager)  응용프로그램 해당 파일의 File Descriptor 정보를 이용 File Manager를 통해 파일을 관리 External File Descriptor(장치)  Internal File Descriptor(메모리) open된 파일만이 메모리에 읽혀지므로 Open File Descriptor Operation Locate the on-device (external) file descriptor Extract info. Needed to read / write file Authenticate that process can access the file ① Create an internal file descriptor in primary memory ② ③ Create an entry in a “per process” open file status table Allocate resources, e.g., buffers, to support file usage open()에서 internal file descriptor만으로 정보를 유지할 수 없는 이유는 해당 파일이 여러 프로세스에서 동시에 열린 경우 각 프로세스들마다 File Position을 유지하고 있어야 하지만 커널에서 자체적으로 1개의 Internal File Descriptor안에는 이 정보를 기록하기에 부족하고, buffer와 해당 파일이 존재하는 File System상의 Device Driver들은 파일이 open된 경우에만 활성화되기 때문에 이를 포함하여 Data Structure라고 표현. File작업에 필요한 커널이나 프로세스들에 대한 Data Structure의 표기는 Practical UNIX Programming 책에서 표현 Open은 external file Descriptor를 디스크에서 메모리로 이동시킨다. 이렇게 이동 시키는 이유는 file descrptor가 만약 디스크에 있다면 파일이 open 될때마다 disk에 있는 file dscriptor에 접근하게 될 것이다. 이렇게하면 비효율적이기 때문에…

19 open() Operation 중의 File Manager 자료구조
External file descriptor를 찾아서(파일 디렉토리를 이용하여) 메모리에 올린다. 이때 Open file Descriptor로 메모리에 올림. 프로세스가 요청한 파일을 그 프로세스가 사용할 수 있는 권한을 가지고 있는지 확인하기 위해서 file descriptor가 필요한다. 2. 권한을 가지고 파일을 사용할 수 있다면 Process-File Session을 프로세스가 가지고 있다. 어디까지 썼고 어디까지 읽었는 등의 정보가 담겨 있다. 변경이 있으면 변경 내용을 process-File Session에 저장함. open() Operation 중의 File Manager 자료구조

20 UNIX Open and Close (1) BSD Unix에서의 open ① ③ ②
int open( char *path, int flags [, int mode] ) Operation ① 파일 시스템에서 파일 디스크립터를 구함 ② 파일 디스크립터와 프로세스 정보로부터 파일에 관한 정보를 추출 프로세스가 파일에 접근할 수 있는지 검증 ③ 파일과 프로세스의 상호작용 상태를 추적하기 위해 File Status Table 에 항목을 생성 ④ 파일 사용에 필요한 리소스를 할당// 파일을 사용하기 위한 메모리 할당을 받는다. Buffer Disk ① Open을 하게 된다면 Inode 생성 , 요청한 파일을 사용하기 위한 file status table이 만들어진다. 그리고 open file table에 등록이 된다. file status table에 파일에 대한 정보가 들어있기 때문에 프로세스마다 한개씩 가지고 있으면서 이 정보에 따라 파일을 읽고 쓰기를 함. Mode UID Time stamps Size blocks Count …… File status Table 위치가 들어간다. Open file table에.. ③ ② Application process File Manager

21 UNIX Open and Close (2) close()는 I/O와 관련된 모든 작업을 완료하라고 파일 관리자에게 지시
ref = 0인 경우에만 실제 자원을 정리 process34 process128 process34 process128 process34 process128 stdin stdin stdin stdin stdin stdin Open File Table 1 stdout 1 stdout 1 stdout 1 stdout 1 stdout 1 stdout 2 stderr 2 stderr 2 stderr 2 stderr 2 stderr 2 stderr 3 3 3 3 3 3 4 4 4 4 4 4 …… …… …… …… …… …… ① ② File Status Table ref = 1 ref = 1 ref = 1 offset offset offset …… …… …… Process34가 파일을 읽었을 때 파일을 어디까지 읽었는지등의 정보가 있다. 만약 같은 파일을 두 프로세스가 open을 했다면… 프로세스당 한개씩의 File Status Table이 만들어진다. 운영체제에서 inode 중 type은 어떤 프로세스가 호출했는지 구별할 수 있다. 응용프로그램 ref = 2 ref = 1 i-node (Memory Image) Type Type …… …… 운영체제 File File File Device

22 두 프로세스의 파일 쓰기 두 프로세스가 파일에 쓰기를 하는 경우
두 프로세스 모두 정상 수행되지만 OS에서는 정의되지 않은 동작이므로 결과를 예측할 수 없다. 파일 쓰기 예 P1 P2 file_desc = open( “lock.test", O_WRONLY ); if( file_desc == -1 ) { // 생성실패 } else { // 생성 성공 } 쓰기전용으로 열기 쓰기 시도 쓰기 시도 두개 프로세스가 동시에 파일에 쓰기를 하는 경우는 유닉스에서 정상 수행 되지만 어떤 결과가 올지는 모른다. File1 모두 허용

23 레코드 단위 잠금 여러 프로세스가 한 파일을 영역별로 나누어 사용 fcntl을 이용해서 파일 내의 레코드 단위 잠금 제어
F_RDLCK, F_UNLCK, F_WRLCK P1 P2 P3 파일 쓰기 예 RECORD record; struct flock region1; file_desc = open( “lock.test", O_RDWR | O_CREAT ); region1.l_type = F_RDLCK; // F_WRLCK region1.l_start = 10; region1.l_len = 20; … fcntl( file_desc, F_SETLK, &region1 ); close( file_desc ); unlink( “lock.test” ); 10 region1 F_RDLCK 공유 잠금(P1) 30 40 region2 F_RDLCK 공유 잠금(P2) 50 region3 F_WRLCK 배타 잠금(P3) 100

24 Last inode modification
UNIX File Descriptor Field Description Mode 소유자와 다른 사용자에 대한 접근 권한 정보 UID 파일을 생성한 사용자의 ID Group ID (GID) 파일에 그룹 접근 권한을 가진 사용자들을 식별하기 위한 ID Length in bytes 파일의 바이트 수 Length in blocks 파일을 구현하기 위해 사용된 블록 수 Last modification 파일에 마지막으로 쓰여진 시간 Last access 파일이 마지막으로 읽혀진 시간 Last inode modification inode가 마지막으로 변경/수정된 시간 Reference count 파일을 참조하는 디렉터리 수; 모든 디렉터리에서 파일이 삭제되었는지 하확인하기 위해 사용하는 참조 카운트로 0이 되면 실제 파일을 삭제하고 공간을 해제한다 Block references 파일에 할당된 블록을 가리키는 포인터와 간접 포인터

25 Block Management 파일에 저장 블록(storage block) 할당을 관리하는 것 File and Blocks
여러개의 블록들로 구성 길이 m인 파일의 필요 block 수 N은 (Block의 크기 : k) 기본전략 연속 할당(Contiguous Allocation) 링크드 리스트(Linked List) 색인 할당(Indexed Allocation) 파일을 만든다는 것은 블락들이 할당되는 것이다. 파일의 저장 블록을 할당 관리  block management N을 구할 때는 무조건 올림! 블록 할당 방법 연속 할당 링크드 리스트 색인 할당 3가지가 존재한다.

26 Contiguous Allocation
N개 블록을 보조기억장치에 N개의 연속된 블록으로 매핑 수시로 변화하는 파일 크기를 지원하기 어려움 추가시 : 디스크의 분할된 영역보다 큰 파일은 저장 불가 삭제시 : 파일의 크기가 다양하므로 단편화 진행 File1 File2 Unallocated Space 785 809 16384 16404 First Block : 785 Number of blocks : 25 … File1’s File Descriptor First Block : 16384 Number of blocks : 21 File2’s File Descriptor Head Position : 234 Head Position : 498 연속적으로 할당 장점 785블락이 234 트랙에 있다고 하면 그 다음 것들을 금방 찾을 수 있다. 지역성 때문에 쉽게 찾을 수가 있다. 파일의 크기가 수시로 변할 경우는 중 늘어날 경우 809이후에 다른 놈이 사용하고 있다면 문제가 발생할 것이다. 삭제시에도 프레그멘테이션이 발생할 수 있다.

27 Linked List를 활용한 방법 (1) 개요 블록의 헤더 특징 각 블록마다 헤더를 두어 블록끼리 연결
블록에 할당된 바이트 수 다음 블록을 가리키는 포인터 특징 블록의 임의할당이 가능 매 블록마다 다음 블록의 위치를 기록 다음 블록을 추가할 때 블록이 연속되지 않아도 된다 파일 크기를 늘리거나 줄일 수 있음 Block의 삽입 및 삭제 가능 블록 마다 헤더를 가지고 있다. 헤더는 링크드 리스트를 만들고 크기를 결정한다. 위치에 상관없이 임의할당할 수 있다. 다음 블록 추가할 때 위치가 상관이 없다. 파일의 크기를 줄이거나 늘리는 것이 마음대로 가능하다. 단점은 검색시 링크드 리스트이기 때문에 오래걸리고 일정하지 않다.

28 Linked List를 활용한 방법 (2) One-way Linked Blocks 단일 연결리스트로 구성된 데이터 블록
디스크립터는 리스트의 시작 위치만 유지함 seek() 연산(탐색)은 느리다 임의의 block을 접근할 때 해당 파일의 처음부터 접근해야 함 맨 왼쪽에 있는 것이 file state block이다. Length를 두는 이유는 항상 크기가 일정하지 않기 때문에 이 변동을 쉽게 처리하기 위해서 두었다. (데이터 바이트의 수) 검색시 디시크 I/O가 자주 발생하므로 속도가 느리다.

29 Linked List를 활용한 방법 (3) Doubly Linked Blocks 블록 탐색시 현재의 위치에서 양방향 탐색 가능
 탐색 시간 단축 단방향 링크드 리스트에서 한 블락의 링크가 깨졌을 경우를 대비하여 처음 File Status Table이 마지막 블락을 가리키면서 첫번째를 가리키게 된다.

30 Indexed Allocation 헤더 정보를 추출해서 인덱스로 관리 탐색(seek)을 선형적으로 할 수 있다
인덱스를 하나로 연결할 수 있다(대용량 파일) 다중 인덱싱  간접 인덱싱(Indirect indexing) 헤더 정보를 가지고 있는 인덱스를 가지고 관리한다. File statues table에서는 index를 가리키고 인덱스는 각 헤더를 가지고 있고 그 각 헤더는 하나의 블락을 가리키고 있다. Index는 1block 이고 보통 1block은 256byte이다. 하나의 헤더를 가지고 있는 것이 32bit라고 가정하면 256/4  64개의 블락을 가리킬 수 있다. 다중 인덱싱은 처음 index의 헤더가 가리키는 것이 블락이 아니라 또 다른 index 인것이다.

31 UNIX File Structure The inode File Descriptor + Index blocks (15)
12 direct pointers 1 single, double, triple indirect pointer Each block is 4KB (8 sectors) Super block Partition을 대표하는 block Partition의 선두에 위치, 위치는 고정 Booting 정보, Partition의 크기, i-node list의 위치 정보 등이 내장 How big can UNIX files be? (Each indirect index can point 1000 disk addresses) Direct block : 0~11 block Single indirect : 12 ~ 1011 block Double indirect : 1,012 ~ 1,001,011 block Triple indirect : 1,001,012 ~ 1,001,001,011 block But UNIX file can expand only 2GB!! File Position is 32-bit integer with 1 sign bit (231byte  2GB) Recently, a newer version of UNIX machine implements the file position to 64-bit. This can allow from OS 263bytes long file. 64 bit file system with 1 sign bit(263 = 8 * 1018 = 8 exa-bytes = 8,000,000 tera-bytes) File Descriptor는 파일을 누가 만들었는지 등의 파일 정보가 들어있다. Inode에서 12개의 direct pointer는 바로 블락을 가리키는 것이다. Single indirect 는 인덱스를 한번 거쳐서 블락(데이터)에 접근하는 것. Double indirect는 인덱스를 두번 거쳐서 블락(데이터)에 접근하는 것. Triple indirect는 인덱스를 세번 거쳐서 블락(데이터)에 접근하는 것. Direct 블락을 가리리는 것은 파일의 크기가 작은 경우 이를 이용하고 파일의 크기가 큰 경우에는 indirect 블락을 이용한다. File Position is 32-bit integer with 1 sign bit (231byte  2GB) 최근에는 file position을 64 bit까지 늘려서 2^63byte까지 사용할 수 있다. 1.Super block은 파일 시스템을 대표하는 블록으로서 Booting 정보(만일 해당 FS가 root 즉, booting용인 경우에는 이 정보로 File System을 마운트), Partition의 크기(전체 크기 및 블록당 섹터수등), i-node list의 위치 정보(i-node list가 몇번 블록에 존재하는지, i-node가 나타낼 수 있는 정보가 몇 블록의 크기를 나타내는지), 마운트 여부 등을 포함한다. 2.비록 UNIX의 Index addressing이 많은 수의 블록들을 커버할 수 있다고는 하나 파일의 사용의 주체는 프로세스이다. 프로세스는 해당 파일을 open하여 사용할때 File Position을 이용하게 되는데 과거의 UNIX들은 이를 32bit로 구성했었다. 이 32비트 정수가 부호가 있는 이유는 (-)연산, 즉 File Position을 뒤로 후퇴시킬 경우에 이용하며, 이로 인해 1bit는 부호비트가 되어 2^31 바이트만큼이 사용된다. inode k inode N Data blocks inode2 inode1 inode list Super block

32 Disk Blocks (Clusters)
DOS FAT File System MS-DOS, Windows등에서 사용 Block을 Cluster의 단위로 사용 한 Cluster는 4~64개의 Sector(512byte)로 구성 FAT (File Allocation Table)를 두어 다음 Cluster의 위치로 Linked List를 표현 예 : 2  15  6  32번 Cluster에 파일이 있을 때 BPB(Boot Parameter Block) 1st copy of FAT 2nd copy of FAT 1개의 하드디스크 또는 1개의 Partition Directory Data Storage Area (Clusters) Directory abc.txt 시작 클러스터 번호 rrr.txt … 디스크의 관리를 cluster 단위로 함. FAT( cluster를 관리함) 전체 디스크 공간을 cluster 단위로 생각하고 이를 관리한다. 디렉토리에 있는 abc.txt는 2번 cluster에서 시작한다. 테이블에서 링크드 리스트 형식처럼 연결되어 있고 이를 보면 몇번 cluster를 사용한지 알수 있게 된다. File Allocation Table 15 32 8 16 24 32 40 2 6 15 32 6 1 3 2 4 끝 Disk Blocks (Clusters)

33 Unallocated Blocks 미할당 블록(Unallocated blocks)을 관리하기 위한 자료 구조 필요
연결 리스트(Linked List) 미할당 Block들을 하나의 거대한 파일로 정의 Block이 파일에 할당될 때마다 미할당 List에서 제거 Very Large 공간적 지역성(Spatial Locality)를 관리하기 어렵다 Block Status Map (“Disk Map”) Bit per Block 예 : 1GB disk가 4KB block들을 가지고 있을때 1bit가 1block을 나타낼 때 256K Entry(32KB)의 공간만이 필요 인접한 여유 블록을 찾기 쉽다 디스크 복구 정보로 유용하게 이용할 수 있다 cf. 공간적 지역성(Spatial Locality): 한번 참조된 곳에서 계속 참조될 가능성이 높은 것 시간적 지역성(Temporal Locality): 한번 참조되면 다음에 또 참조될 가능성이 높은 것 Free space는 어떻게 관리할 것인가 1.링크드 리스트 자유 공간끼리 링크드 리스트로 연결해 놓은다. 아무리 큰 공간이라고 제약이 없다. 하지만 블락이 파일에 할당될 때마다 리스트에서 제거해줘 관리해야한다. 연속적으로 집어 넣을 수 없기 때문에 관리에 어려움이 있다. 2. Block status map 하나의 테이블이라고 볼 수 있다. bit들이 나와 있고 1이 있는 그 번째 블락은 사용되고 있고, 0이 있는 그 번째 블락은 사용되지 않고 있다. 디스크 관리를 위해서 map을 위한 장소가 따로 정해져있다.

34 Managing the Byte Stream (1)
Packing and unpacking blocks Unpacking (Reading) Must read-ahead on input Read 작업 중 Block의 경계선에서 미리 1Block분의 I/O 발생  실제 읽는 시간보다 먼저 읽어 짐 Packing (Writing) Must write-behind on output Write 작업 중 Block의 경계선에 도달해야 I/O 발생  실제 쓰는 시간보다 나중에 기록 됨 Seek Random Access Device에서 특정 Position i 에 대하여 Block을 찾음 Bi = (k : Block size) Block의 위치를 정한 후 Memory로 Read 작업 File Management의 성능을 향상하기 위하여 커널 내에 Buffer를 두게 되는 경우 읽기 작업은 언제나 응용프로그램에서 해당 File Position을 읽기 이전에 일어난다. 예를 들어 open() System Call이 호출되면 맨 처음 블록에 접근하게 되므로 Buffer에는 응용프로그램의 요청이 없이도 첫번째 블록이 읽혀져 대기하게 된다. 마찬가지로 순차적으로 데이터를 읽을때 각 블록의 경계선에서 1개 분량의 블록이 먼저 읽어지게 되고 해당 블록의 2번째 바이트 부터는 이미 메모리에 저장되어 있으므로 I/O는 일어나지 않는다. 쓰기 작업도 읽기 작업과 마찬가지고 해당 File Position에 기록하다가 블록의 경계선에서 I/O가 일어난다. Seek은 응용프로그램에서 파일의 특정 위치로 File Position을 이동시키는 연산이다. 이럴 경우 Buffer가 파일의 모든 부분을 가지고 있을 수는 없으므로 File Position이 해당 블록의 경계를 넘을 경우 자동적으로 커널은 현 Buffer내의 내용을 무시하고 새로 작성하게 된다. 이를 구하기 위한 공식은 File Position i를 블록의 크기로 나눈 값이 되며, 예를 들어 1001 File Position을 블록 크기 256에 넣을 경우, 커널은 해당 파일의 4번째 블록을 Buffer로 불러 들인다.

35 Managing the Byte Stream (2)
Inserting / deleting bytes in the interior of the stream Each operation may occur a fragmentation in one block bk bi bi+1 bk+r … Blockj new bi+1 new bi + 2 new bk+r+1 New Blockj + 1 A byte insertion (unused) (a) Before Insertion (b) After Insertion

36 Managing the Byte Stream (3)
Block I/O Buffer several blocks Storage Device에서 연속으로 읽기 / 쓰기 동작은 평균 seek time을 줄임 수개 혹은 수십개 정도의 block을 미리 Memory에 읽음으로써 성능 향상 (Chapter 5.2절 Buffering 참고) 미리 읽어 놓음 Buffering

37 Directories 논리적으로 연관된 파일과 서브 디렉터리들의 집합 파일 매니저에서 디렉터리 제어 명령을 제공
Enumerate 해당 디렉터리가 참조하는 파일과 중첩된 디렉터리 목록을 반환한다 (“ls” command) Copy 파일에 대한 신규 복사본을 만든다(“cp” command) Rename 파일의 이름을 변경한다 (“mv” command) Delete 디렉터리에서 파일을 제거한다 (“rm” command) Traverse 한 디렉터리에서 다른 디렉터리로 이동하면서 디렉터리 계층구조를 탐색한다(“find” command)

38 Directory Structures How should files be organized within directory?
단일 디렉터리 (Flat name space) 모든 파일이 디렉터리 하나에 보관 계층 디렉터리 (Hierarchical name space) 디렉터리에 파일과 하위 디렉터리를 보관 트리 구조 관리 : 자식 노드(파일/디렉터리)는 오직 하나의 부모 노드(디렉터리)만 가질 수 있다 비순환 그래프(Acyclic Graph) 비순환그래프로 파일을 조직하는 방법 자식 노드가 여러 개의 부모 노드를 가질 수 있다 파일이나 디렉터리 공유를 지원한다 공유의 필요성이 높기 때문에, 디렉터리 구조에서는 유향 비순환그래프(Directed Acyclic Graph:DAG)에 기반한 계층 구조 사용 D F Flat D F Strict Hierarchy D Acyclic Graph D D F F F F D : Directory F : File

39 Directory Implementation
장치 디렉터리(Device Directory) 장치(파일 시스템)도 파일처럼 취급 가능 Storage Device들은 자체적인 File System으로 구성 모든 장치에 대한 파일에 대한 루트가 있으면 관리가 용이 디바이스 루트 디렉터리 특정 Directory들은 Storage Device로 연결 가능 UNIX의 mount root user1 user2 system Device Z Device A Device B

40 Mounting File Systems Foo folder에 FS 를 mount 함.

41 Heterogeneous File Systems
mount: 다양한 장치에 구현된 파일 시스템과 파일 매니저를 연결 파일 계층 구조는 다른 파일 시스템을 조합해서 구성 가능 In Linux File System 다양한 FS 지원을 위해 VFS (Virtual File System) 개념 사용 시스템 종속적인 부분과 독립적인 부분으로 나눔 서로 다른 운영체제가 다를 경우 하나로 만들어 주는 것 virtual file system이라는 것이 있다…. 리눅스에서 사용하고 있음