7장. 교착상태(deadlock)

Size: px

Start display at page:

Download "7장. 교착상태(deadlock)"

윤소 담
5 years ago
Views:

1 11 장. 파일시스템구현

2 목표 local 파일시스템및디렉토리구조의구현을설명 remote 파일시스템구현을설명 블록할당과자유블록알고리즘논의 2

3 11.1 File-System 구조 File system 은보조저장장치 ( 디스크 ) 에위치. 블록단위전송 I/O 효율성향상 block size: one or more sectors sector size: 32 4KB (usually 512B) File systems 은디스크에대한효율적이고편리한접근을제공함 파일시스템의 2 가지설계문제 파일시스템이사용자에게보여지는방법을정의 파일, 파일속성, 파일연산, 디렉토리구조 논리파일시스템을물리적보조저장장치로맵핑하는방법설계 알고리즘, 자료구조 파일시스템의계층적설계 layered file system 3

4 계층적파일시스템 (Layered File System) 메타데이터정보관리, 심볼릭파일이름디렉토리구조, file control block(fcb) - inode protection/security logical block 을 physical block 으로변환 file 공간관리자 device driver 에게명령어제공 physical block(drive, cylinder, track, sector) 사용 memory buffers 와 caches 관리 device driver, interrupt handler - 메모리와디스크간의데이터전송 4

5 File systems 의종류 현재많은파일시스템들이사용되고있음 대부분의운영체제가 2 개이상의파일시스템지원 이동가능한 (removable) 파일시스템 CD-ROM, DVD, floppy disk CD-ROM : ISO 9660 format 디스크기반파일시스템 UNIX : Berkeley Fast File system(ffs) 에기반을둔 Unix 파일시스템 Windows : FAT, FAT32, NTFS Linux : ext2, ext3, ext4(extended file system), 40 개이상의파일시스템지원 분산파일시스템 파일서버에있는파일시스템을네트워크로연결된클라이언트컴퓨터에서마운트하여사용함 5

6 11.2 File-System 구현 파일시스템구현을위한자료구조 on-disk 자료구조 in-memory 자료구조 On-disk 구조 부트제어블럭 (boot control block) (per 파티션 / 볼륨 ) UNIX 부트블럭 볼륨제어블록 (volume control block) (per 파티션 / 볼륨 ) contains # of blocks, block size, free block count, free block pointer, free FCB count, FCB pointer UNIX - superblock, Windows NTFS - master file table 디렉토리구조 (per 파일시스템 ) file names, associated inode numbers 포함 (NTFS: in master file table) 파일제어블록 (per 파일 ) UNIX's inode (NTFS: in master file table) 파일데이터 6

7 UNIX file system* 7

8 In-Memory 자료구조 In-memory 구조 in-memory mount table (partition table) in-memory directory structure 최근에접근한디렉토리들에대한정보 system-wide open file table open file들에대한파일제어블럭 (FCB) 복사본 per-process open file table the system-wide open table의 entry에대한포인터 UNIX - file descriptor, Windows - file handle 8

9 In-Memory File System 구조 buffer 5 File Open buffer cache File Open / File Read 9

10 File Control Block File control block (FCB) 파일에정보로구성되는 storage structure 전형적인 file control block (access control list) logical block 번호 (0 ~ N-1) 10

11 Partitions 과 Mounting partition 은 raw (unformatted) 또는 cooked (formatted) 일수있음 raw partition : file system 이없음 usages: UNIX swap space, some databases, boot information RAID system information cooked partition : a file system 을포함 Mounting root partition 이부트시간에마운트됨 다른 partition 들은부트시간에자동적으로마운트되거나나중에수동으로마운트될수있음 Windows 는각 volume 을분리된이름공간에마운트 ( 예 ) C:, D:.. UNIX 는 partition 의파일시스템을임의의디렉토리에마운트가능 전체적으로하나의디렉토리구조유지 마운팅정보는 in memory mount table 에저장됨 각파티션에있는파일시스템의 superblock 에대한포인터 11

12 Virtual File Systems 여러유형의파일시스템에대해서같은 API 를사용할수있도록함 ext3 NTFS 12

13 11.3 Directory 구현 Linear List 디렉터리를 ( 파일이름, 포인터 ) 들의 linear list 로구현 구현하기쉽지만디렉터리검색에시간이소요됨 Hash Table 파일이름에대한 hash 함수값을계산하여 linear list의위치를결정 디렉터리검색시간감소 여러파일들이같은위치로 hash되는충돌상황에대한처리가필요 13

14 11.4 Allocation 방법 파일에대한디스크공간할당방법의고려사항 디스크공간의효율적이용 파일의빠른접근 3 가지주요할당방법 contiguous allocation linked allocation indexed allocation 14

15 연속할당 (Contiguous Allocation) 각파일은디스크의연속된블록들의집합을점유 if start block = b, block i of a file access block b+i 15

16 Contiguous Allocation ( 계속 ) 장점 단점 최소탐색시간 (seek time) 간단함 디렉토리는시작위치와크기만필요로함 Random access : 파일접근이쉬움 파일의블록 i의위치 = b + i (b는파일의 start 디스크블록번호 ) 외부단편화로인한저장공간낭비 동적저장공간할당문제 파일크기를증가시킬수없음 해결책 : (1) pre-allocation but, internal fragmentation (2) 새로운큰연속적인공간을찾아서저장 속도저하 16

17 연결할당 (Linked Allocation) 각파일은디스크블록들의 linked list 로구성 block = pointer 블록들이디스크의 임의의위치에분산가능 17

18 Linked Allocation ( 계속 ) 장점 단점 간단함 디렉토리는시작위치 ( 와마지막위치 ) 만필요로함 공간낭비가없음 연속공간불필요, 외부단편화없음 random access 불가능 임의위치접근이비효율적 뒤에있는블록은여러번의디스크접근필요 연결포인터를위한공간이필요 해결책 : 여러개의연속블록인 clusters 단위로할당 ( 디스크 throughput 향상, 내부단편화발생 ) File-allocation table (FAT) 방식 MS-DOS 에서사용하는디스크공간할당방식 linked allocation 의변형 FAT 는파티션의시작에위치함 FAT 는각디스크블록에대해한 entry 를제공 각디스크블록의 next block number 를저장 FAT 는메모리에캐쉬되어사용 효율적파일접근 18

19 File Allocation Table (FAT) disk partition FAT copied into memory 0 unused block 19

20 인덱스할당 (Indexed Allocation) 인덱스블록사용 디스크블록의 pointer 을저장하는디스크블록 index table index block 20

21 Indexed Allocation ( 계속 ) 장점 단점 random access 가능 (contiguous allocation 의장점 ) 외부단편화없음 (linked allocation 의장점 ) 디렉토리는인덱스블록위치만저장 index block 이필요함 linked allocation 보다 pointer overhead 가더큼 1 개의 index block 파일크기에제한 ( 예 ) 512 word/block : 1 block 은 512 block 의포인터저장 최대파일크기 512 x 512 = 256K word 크기제한의해결책 - 여러개의 index block 을사용 linked scheme multilevel index combined scheme 21

22 Indexed Allocation - Linked scheme Link blocks of index table 파일크기제한없음 disk block directory index table null 22

23 Indexed Allocation - Multilevel index Two level index directory M outer-index index table disk block 4KB/block, byte pointers max file size: x 4KB = 4GB 23

Combined Scheme: UNIX (4KB / block) direct: 12 x 4KB = 48KB single indirect: 1024 x 4KB = 4MB double indirect: 1024 2 x 4KB

24 Combined Scheme: UNIX (4KB / block) direct: 12 x 4KB = 48KB single indirect: 1024 x 4KB = 4MB double indirect: x 4KB = 4GB triple indirect: x 4KB = 4TB bit file pointer 4GB 64-bit file pointer(solaris, AIX) > 4GB UNIX i-node 24

25 11.5 Free-Space 관리 Bit vector free space list 를 bit map 또는 bit vector 로구현 n-1 bit[i] = 1 block[i] free 0 block[i] occupied block number 계산 block number = 8 x = 17 the number of bits per word the number of 0-value words bit offset of first

26 Free-Space 관리 ( 계속 ) Bit vector 방식 ( 계속 ) 장점 - 비교적간단, 첫째 free block 및 n 개의연속 free block 찾기쉬움 단점 - Bit map 은추가공간을필요로함 block size = 2 12 B (4KB), disk size = 2 30 B (1GB) 인경우 n = 2 30 /2 12 = 2 18 bits (or 2 15 B = 32KB) 전체 bit vector 를메모리에적재할수없으면비효율적 Linked list (free-list) 단점 - 연속공간을쉽게얻을수없음 장점 공간낭비가없음 26

27 Free Space 관리 Grouping free list 방식의수정 첫번째 free block 에 n 개의 free block 의주소저장 list head a free block a free block Counting n-1 free blocks n-1 free blocks free list는연속된 free block의첫번째주소와블록개수를저장 free list 길이가짧아짐 (list head,3)

28 11.6 효율 (Efficiency) 과성능 (Performance) 효율 성능 디스크할당및디렉토리알고리즘이디스크공간의효율적사용에영향을줌. 디렉토리 entry 에저장되는데이터종류를고려해야함 마지막접근시간을기록한다면비효율적임 disk cache 빈번히사용되는 disk block 을저장하는메모리의부분 buffer cache, page cache ( 가상메모리와결합하여사용 ) free-behind 및 read-ahead 순차접근을최적화하기위한기법 28

29 Page Cache page cache 파일데이터를파일블록이아닌가상메모리의 page 단위로캐쉬 double caching 이발생함 메모리공간낭비 Memory-mapped I/O 는 page cache 를사용 파일시스템 I/O 루틴은 buffer(disk) cache 를사용 I/O Without a Unified Buffer Cache 29

30 Unified Buffer Cache A unified buffer cache memory-mapped pages 와보통 file system I/O 를복사하는데모두같은 page cache 를사용 double caching 발생하지않음 (= page cache) 30

31 11.7 Recovery 파일과디렉토리는주메모리와디스크에모두저장됨 system failure 는데이터손실및데이터비일관성 (inconsistency) 을가져올수있음 일관성검사 (Consistency checker) 디렉터리구조에있는데이터와디스크의데이터블록을비교하여 inconsistency 를찾고, inconsistency 를고침 항상가능하지는않음 Backup 시스템프로그램을사용하여디스크데이터를다른보조저장장치 ( 테이프등 ) 로백업 full backup incremental backup... incremental backup Restore 백업장치로부터데이터를복원하여손실된파일 / 디스크를복구함 31

32 로그구조 (Log Structured) 파일시스템 로그구조파일시스템 (Journaling 파일시스템 ) 파일시스템에대한각 update 를 transaction 으로기록 모든트랜잭션은로그에기록됨 트랜잭션이로그에기록되면, 트랜잭션은 commit( 확정 ) 된것으로간주 이때에, 파일시스템은아직갱신되지않을수있음 로그에있는트랜잭션은비동기적으로파일시스템에기록됨 파일시스템이수정되면, 해당트랜잭션은로그에서삭제됨 파일시스템에기록되는동안시스템이고장나면, 로그에있는모든남아있는트랜잭션은다시수행될수있음 로그에기록되는동안시스템이고장나면, 해당트랜잭션은실행되지않음 파일시스템일관성은유지됨 32

Microsoft PowerPoint - 알고리즘_1주차_2차시.pptx

Microsoft PowerPoint - 알고리즘_1주차_2차시.pptx Chapter 2 Secondary Storage and System Software References: 1. M. J. Folk and B. Zoellick, File Structures, Addison-Wesley. 목차 Disks Storage as a Hierarchy Buffer Management Flash Memory 영남대학교데이터베이스연구실