Microsoft PowerPoint os10.ppt [호환 모드]

Size: px

Start display at page:

Download "Microsoft PowerPoint os10.ppt [호환 모드]"

옥담 견
5 years ago
Views:

1 파일시스템인터페이스 (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)» 내부파일구조 논리구조 =1byte 물리구조 = 512 bytes

2 Memory Mapped Files

3 File Types name, extension File Type Usual extension Function Executable exe, com, bin or none ready-to-run machinelanguage program Object obj, o complied, machine language, not linked Source code c, p, pas, 177, asm, a source code in various languages Batch bat, sh commands to the command interpreter Text txt, doc textual data documents Word processor wp, tex, rrf, etc. various word-processor formats Library lib, a libraries of routines Print or view ps, dvi, gif ASCII or binary file Archive arc, zip, tar related files grouped into one file, sometimes compressed

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

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

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

7 단단계디렉토리 (Single-Level Directory) 이단계디렉토리 (Two-Level Directory)

8 트리구조디렉토리 (Tree-Structured Directories)

9 비순환그래프디렉토리 (Acyclic-Graph Directories)

10 일반적인그래프디렉토리 (General Graph Directory)

11 보호 (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) 파일이름불변 파일내용변경불가

12 파일시스템구현 (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)

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

14 Example of Contiguous Allocation

15 할당방법 (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 해야함

16 Linked allocation of disk space

17 FAT (File Allocation Table)

18 할당방법 (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)» triple indirect blocks: 실제사용않음 Q: 한파일의최대블록수? Q: 한파일의최대크기? 성능» 연속 ( 직접접근 ) + 연결 ( 순차접근 )» 연속 ( 작은파일 ) + 색인 ( 큰파일 )

19 Example of Indexed Allocation

20 Combined Scheme: UNIX (4K bytes per block)

21 가용공간관리 (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 이문제» 크기확장어려움

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

23 FCFS Illustration shows total head movement of 640 cylinders

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

25 SSTF (Cont.)

26 SCAN

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

28 C-SCAN (Cont.)

29 C-LOOK (Cont.)

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

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

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 영남대학교데이터베이스연구실