Chapter 10. 파일 시스템 인터페이스(File System Interface) 파일 개념 (File Concept) 보조기억장치에 저장된 관련된 정보들의 모임 파일 속성: 이름, 타입, 위치, 크기, 보호 파일 연산: 생성, 쓰기, 읽기, 재위치, 삭제 열린 파일 정보: per-process open file table file pointer file open count disk location of the file memory-mapped files: 그림 10.1 memory mapping으로 파일의 한 영역을 공유 상호배제 필요 파일 타입: 그림 1.2, magic number(Unix) 파일 구조: 텍스트 파일과 실행 파일 구분 최소한의 구분: 8-bit byte의 연속(Unix, MS-DOS) 내부 파일 구조 논리구조 = 1 byte 물리구조 = 512 bytes 운영체제

Memory Mapped Files 운영체제

File Types – name, extension 운영체제

접근 방법(Access Methods) 순차접근(sequential access) 직접접근(direct access) 기타: ISAM(Indexed Sequential Access Method) 운영체제

디렉토리 구조(Directory Structure) 디렉토리: 파일에 대한 정보를 담고 있는 노드들의 모임 (a collection of nodes containing information about all files) Directory Files F 1 F 2 F 3 F 4 F n 디레토리 구조 및 파일은 디스크에 운영체제

디렉토리 구조(Directory Structure) 단단계 디렉토리: 그림 10.7 모든 파일이 같은 디렉토리에 모든 파일이 유일한 이름을 가져야 함 이단계 디렉토리: 그림 10.8 사용자별 UFD(User File Directory) 파일 공유 어려움 트리구조 디렉토리: 그림 10.9 사용자별 subdirectory 생성 유일한 path name 가짐 비순환 그래프 디렉토리: 그림 10.10 파일과 서브디렉토리 공유가능 구현 방법 : link 사용(Unix), 복사(duplication) 일반적인 그래프 디렉토리: 그림 10.11 트리구조 디렉토리에 link 첨가 cycle 허용되면 탐색시 무한 루프 가능 새 link 추가시 cycle 피하는 것이 어려움 운영체제

단단계 디렉토리(Single-Level Directory) 이단계 디렉토리(Two-Level Directory) 운영체제

트리구조 디렉토리(Tree-Structured Directories) 운영체제

비순환 그래프 디렉토리(Acyclic-Graph Directories) 운영체제

일반적인 그래프 디렉토리(General Graph Directory) 운영체제

일관성 의미 구조(Consistency Semantics) 보호(Protection) 보호 접근타입 제어: 읽기, 쓰기, 실행,첨가, 삭제, 리스트 접근 리스트와 그룹: owner, group, universe 기타 보호: password, 디렉토리 보호(sticky bit) 예: 3 bits rwx(Unix) 일관성 의미 구조(Consistency Semantics) 파일 시스템 관리에 있어서의 일관성 의미 구조(철학) Unix 의미론: Unix file system 열린파일의 변경은 즉시 공유자에게 보여짐 파일의 현재 위치 포인터 공유->하나의 파일 이미지 유지 세션 의미론: Andrew file system (session: 파일 open과 close 사이의 모든 파일접근의 연속) 열린파일의 변경은 즉시 공유자에게 보여지지 않음 파일 변경은 파일 close 후 다른 session에서만 보여짐 불변-공유 파일 의미론 (immutable shared file = read-only file) 파일 이름 불변 파일 내용 변경 불가 운영체제

파일 시스템 구현(File System Implementation) 파일 시스템 구조(File System Organization) 응용 프로그램(application program) 논리적 파일 시스템(logical file system) 디렉토리 구조 파일 구성 모듈(file-organization module) 논리블록 -> 물리블록) 기본적 파일 시스템(basic file system) 장치 드라이버에 read/write 명령) 입출력 제어(I/O control) device drivers와 interrupt handler 장치(devices) 운영체제

할당 방법(Allocation Methods) 연속할당(contiguous allocation): p393(11.15) 디스크 탐구시간(seek time)이 최소 순차접근과 직접접근 모두 동적 기억장치 할당 외부단편 문제 파일 크기 결정(preallocation) 문제 -> extent(다른 연속할당 덩어리)로 연결 파일의 블록주소 : <시작위치, 블록 개수, 다음 extent로 link) 운영체제

Example of Contiguous Allocation 운영체제

할당 방법(Allocation Methods) 연결 할당(linked allocation): p394(11.16) 디스크 블록의 연결 리스트 구성 외부 단편 없음 파일 커져도 문제 없음 pointer space overhead -> block들의 clusters로 보완 신뢰성 떨어짐 -> doubly linked list로 보완 직접 접근이 비효율적 (예) FAT(File Allocation Table): p395(11.17) MS-DOS, OS/2각 각 partition 시작 부분에 테이블의 각 항목 : <블록 번호, 파일에서의 다음 블록 번호> 잦은 참조로 인해 caching 해야 함 운영체제

Linked allocation of disk space 운영체제

FAT (File Allocation Table) 운영체제

할당 방법(Allocation Methods) 색인 할당(indexed allocation) : p396(11.18) 각 파일에 색인 블록(index block): paging과 유사 직접접근 가능 색인 블록의 memory overhead 색인 블록의 구현 연결 체계(linked scheme) : 다음 색인 블록으로 연결 다중레벨 색인 (multilevel index) : 간접 색인 (예) 블록크기: 4096 bytes = 1024 항목 x 4 bytes pointers 2-level indexing 경우 최대 블록 개수: 1024 x 1024 파일 최대 크기:1024 x 1024 x 4K = 4G 혼합 체계 (combined scheme) : BSD Unix , p411(11.7) 12 direct blocks: 불록주소 = ~48K (4K x 12) 3 indirect blocks: single indirect blocks: ~ 4M (1024 x 4K) double indirect blocks: ~ 4G (1024 x 1024 x 4K) * 4KB-block = 16TB triple indirect blocks: ~ 4T (1024 x 1024 x 1024 x 4K): 실제 사용 않음 Q: 한 파일의 최대 블록 수? Q: 한 파일의 최대 크기? 성능 연속(직접 접근) + 연결(순차 접근) 연속(작은 파일) + 색인(큰 파일) 운영체제

Example of Indexed Allocation 운영체제

Combined Scheme: UNIX (4K bytes per block) 운영체제

가용 공간 관리(Free-Space Management) Bit-vector(Bitmaps) free: 1 allocated: 0 블록번호 = 워드 당 비트수 x 0인 워드 갯수 + 첫번 1 까지의 간격 연결리스트(Linked List): p388(11.20) 그룹화(Grouping) 첫번 블록에 n-1개 마지막은 다음 블록의 포인터 개수(Counting) <첫번 블록 주소, 연속된 free blocks 갯수> 디렉토리 구현(Directory implementation) 선형 리스트(Linear List) linear search 가 문제 해시 테이블(Hash Table) collision이 문제 크기확장 어려움 운영체제

Chapter 12. 대용량 저장장치 구조(Secondary Storage Structure) 디스크 구조(Disk Structure) fixed head moving head p29(Figure 2.5) 참조 b = k + s x (j + i x t) k : sector # j : surface # i : cylinder # s : sectors/track 디스크 스케줄링(Disk Scheduling) FCFS Scheduling(First-Come First Served) 가장 Simple 가장 먼저 도착한 요청을 먼저 처리 장점 : program 하기 쉬움 fair-predictable(공평성이 유지됨) 단점 : 필요없이 지나치게 이동하는 경우 발생 운영체제

Illustration shows total head movement of 640 cylinders. FCFS Illustration shows total head movement of 640 cylinders. 운영체제

디스크 스케줄링(Disk Scheduling) SSTF Scheduling(Shortest-Seek-Time-First) 현재 head 위치에서 가까운 모든 요구를 처리 FCFS 보다 더 효율적, 일반적인 방법 장점 : 전반적인 seek time을 감소시킴 단점 : 근본적으로 SJF algorithm 형태이므로, starvation이 발생할 수 있음 SCAN 입출력 head가 disk의 한쪽 끝에서 다른 끝으로 가면서 처리해 나가며, 다른 끝에 도착하면 역방향으로 이동하면서 요청된 track 에 대한 처리를 해나가는 방법 SSFT 방식에서의 response time에 있어서의 high-variance를 보완 SSFT와의 차이점 : 계속 한 방향으로 진행 장점 : ① thoughput 증가 ② response time 감소 단점 : 밀도가 높은 부분의 요청이 상당히 오랜시간을 대기하게 됨. (대기 시간의 불균등) 보완한 방식 : LOOK-한 방향으로 요청이 있는 곳까지만 head가 이동하고, 현재 방향에서 더 이상의 요청이 없으면, 이동방향을 바꿈 운영체제

SSTF (Cont.) 운영체제

SCAN 운영체제

디스크 스케줄링(Disk Scheduling) C-SCAN SCAN 방식을 보완하여, 대기시간을 좀 더 균등하게 한 기법 한쪽 방향으로 head를 이동해가면서 요청을 처리하는 것은 같으나, 한쪽 끝에 도착하면 반대 방향으로 head를 이동하지 않고 다시 처음으로 와서 처음부터 처리를 진행시킴. 장점: response time 균등 보완 기법 : C-LOOK Disk Scheduling Algorithm의 선택 가장 일반적이고 자연스러운 선택 : SSTF disk를 많이 사용하는 system : SCAN이나 C-SCAN performance에 영향을 미치는 요인 ① request의 type과 수 ② file 할당 기법 (예) contiguously allocated file : head 이동이 제한됨 link file 또는 index file : head 이동 많음, disk space utilization 높음 ③ directory 와 index block 의 위치 운영체제

C-SCAN (Cont.) 운영체제

C-LOOK (Cont.) 운영체제

무엇이 성공인가 자주 그리고 많이 웃는 것 현명한 이에게 존경을 받고 아이들에게서 사랑을 받는 것 정직한 비평가의 찬사를 듣고 친구의 배반을 참아 내는 것 아름다움을 식별할 줄 알며 다른 사람에게서 최선의 것을 발견하는 것 건강한 아이를 낳든 한 뙈기의 정원을 가꾸든 사회 환경을 개선하든 자기가 태어나기 전보다 세상을 조금이라도 살기 좋은 곳으로 만들어 놓고 떠나는 것 자신이 한때 이곳에 살았음으로 해서 단 한 사람의 인생이라도 행복해지는 것 이것이 진정한 성공이다. 랄프 왈도 에머슨 운영체제

Hard 한 걸 Hard 하게 하면 Hard해 진다. 수고하셨습니다! Hard 한 걸 Hard 하게 하면 Hard해 진다. Hard 한 것은 아름답다. 운영체제