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

Size: px

Start display at page:

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

익 하
4 years ago
Views:

1 1.4 Blocking Block의정의 디스크와메모리사이에데이터전송의단위 물리적레코드라고도함 Sector, Block, Cluster의비교 Sector: Data transfer 의최소단위 Block = n개의 sector로구성 디스크와메모리사이에데이터전송의단위 Cluster: m 개의 sector 로구성되며, FAT 구성단위 Cluster Block 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 18)

2 Blocking 계속 논리적레코드와물리적레코드 논리적레코드 : 사용자정의 ( 예 : 학생, 교수, 과목등 ) 물리적레코드 : 데이터전송의단위 (block) Blocking 이란? 논리적레코드를하나의 block 에저장하는것 Blocking Factor B f = B/R B: 블록의크기, R: 레코드의크기 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 19)

3 Blocking 의종류 고정길이 blocking (fixed length blocking) track 1 track 2 R1 R2 R3 R4 R1 R2 R3 R4 block 하드웨어갭 (gap) 블록의크기가레코드크기의정수배가아닐경우, 낭비공간 신장된가변길이 blocking (spanned variable length blocking) track 1 R1 R2 R3 R3 R4 하드웨어갭 (gap) track 2 R5 R6 R6 R7 구현이곤란, 두블록에걸쳐있는 레코드의경우판독및갱신곤란 비신장된가변길이 blocking (unspanned variable length blocking) track 1 track 2 R1 R2 R3 R4 R5 R6 하드웨어갭 (gap) 다음레코드를저장할수없는경우발생하는낭비공간 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 20)

4 1.5 The Cost of a Disk Access Seek Time 특정 track k( (cylinder) 로 access arm 을이동하는시간 가장많은시간이소요됨 (3ms ~ 15ms) 평균 : desktop HDD - 9ms, mobile HDD - 12ms 다중사용자환경의경우, 특히많은시간소요 average seek time = 1/3oftheworstcase Rotational Delay y( (Rotational Latency) 특정 sector까지 disk 를회전시키는시간 7,200 rpm: 120회전 / 초 8.3ms / 회전, RD = 4.17ms 10,000 rpm: 3ms, 15,000 rpm: 2ms 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 21)

5 Transfer Time Disk khead 를통하여 data 를읽거나쓰는시간 Transfer time = number of bytes transferred number of bytes on a track rotation time Transfer time for one sector? 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 22)

6 Example 1. Average seek time 18 msec Rotational delay 8.3 msec Maximum transfer rate 16.7 msec/track, or 1,226bytes/msec Bytes per sector 512 Sectors per track 40 Tracks per cylinder 10 Cluster size 8 sectors 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 23)

7 Example 1 ( 계속 ) 2,048 Kbytes File (8, bytes records로구성 ) Sequential access 로입력시소요시간 2 records/sector 80 records/track 100 track Track 당한번의 seek time 과 rotational delay Track 입력시간 : ( ) = 43 msec 전체입력시간 : 43 msec 100 = 4.3 seconds Random access 로입력시소요시간 하나의 cluster 입력시간 ( / 5 ) = 29.6 msec 전체입력시간 : 29.6 msec 8,000 = 초 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 24)

8 1.6 Disk as Bottleneck ec Observation disk access time >> CPU 나 network 속도 Solution : multiprogramming, parallelism, buffering Multiprogramming I/O 대기시 CPU 는다른 job 수행 각 process 당 I/O 시간은여전히크다. 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 25)

9 Striping : parallelism 이용 File 을여러개의 disk 에나누어저장 각 disk에서동시에 I/O RAID Disk cache File manager 는별도의 buffer (RAM) 유지 I/O request 시 buffer 참조 locality of reference 이용 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 26)

10 2. Storage as a Hierarchy Types of Devices and Access times Capacities Cost memory media (sec) (bytes) (cents/bit) Primary Registers RAM Core and semiconductors RAM disk and disk cache Secondary Direct-access Serial Magnetic Tape and mass storage Offline Archival backup Removable magnetic disks, optical discs, and tapes 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 27)

3. Buffer Management age e Disk Buffer (= Disk Cache) Hard ddisk 에내장된메모리 용량 : 8MB ~ 128MB 용도 Read-ahead/read-behind: 특정 track으로이동후, 원하는섹터가나올때까지읽은섹터를저장 Speed matching: disk-to-buffer (7200RPM = 1030

11 3. Buffer Management age e Disk Buffer (= Disk Cache) Hard ddisk 에내장된메모리 용량 : 8MB ~ 128MB 용도 Read-ahead/read-behind: 특정 track으로이동후, 원하는섹터가나올때까지읽은섹터를저장 Speed matching: disk-to-buffer (7200RPM = 1030 Mb/s) buffer-to-computer (SATA 3 6Gb/s) 따라서둘사이의속도를완충 Write acceleration: Not Force 기능구현 Command queuing for multiple commands Page Cache: Computer 의 main memory 운영체제에의해관리 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 28)

12 3.1 Buffer Bottlenecks ec Buffer의정의 : (Page Cache를가정 ) Buffering involves working with large chunks of data in RAM so the number of accesses to secondary storage can be reduced. How many buffers are used? 하나의 I/O buffer 가사용될경우, buffering 효과 하나의문자를입력하여, 다시출력하는경우 적어도두개의 buffer 필요 : input & output I/O bound job 의경우, 여러개의 buffer 필요 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 29)

13 3.2 Buffering Strategies es Multiple Buffering Double buffering I/O 작업과 CPU 작업을 overlapping 2 개이상의 buffer 사용가능 Buffer pooling UNIX 의 buffer cache 개념 buffer replacement : least recently used (LRU) 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 30)

14 Program data area I/O buffer 1 I/O buffer 2 To disk (a) I/O buffer 1 Program data area (b) I/O buffer 2 To disk Double buffering : (a) The contents of system I/O buffer 1 are sent to disk while I/O buffer 2 is being filled ; and (b) the contents of buffer 2 are sent to disk while I/O buffer 1 is being filled.

15 입출력바운드이중버퍼링의시간프레임 장치 버퍼 1 채우기버퍼 2 채우기버퍼 1 채우기버퍼 2 채우기 50 ms 50 ms 50 ms 50 ms... CPU 버퍼 1 버퍼 2 버퍼 1 처리 처리 처리 50 ms 25 ms 25 ms 25 ms 25 ms 25 ms 25 ms... 시간 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 32)

16 프로세서바운드이중버퍼링의시간프레임 장치 버퍼 1 채우기버퍼 2 채우기 버퍼 1 채우기 50 ms 50 ms 50 ms 50 ms 50 ms... CPU 버퍼 1 처리 버퍼 2 처리 50 ms 100 ms 100 ms... 시간 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 33)

17 Example 2 : Buffering 과 Hard Disk 80 Bytes/record, 7 records/block, 24 sectors/track 200 tracks/surface, 20 tracks/cylinder File size = 33,881 blocks (71개의 cylinder에나누어저장 ) Transfer time = 806 Kbytes/sec, Rotational delay = 8.3 msec Average seek time = 30 msec 1. File 을순차적으로입력하는데걸리는시간? 입력시간 = (AST + RD) cylinder 수 + block 당 TT block 수 = ( ) 71 / 1, / ( ) 33,881 = 25.7 sec 영남대학교데이터베이스연구실 Algorithm: Chapter 2 (Page 34)

18 2. 한 block 을처리하는데 0.5 msec 가걸리며, single buffering 을할경우file 을입력하여처리하는데걸리는시간? 전체시간 = 입력시간 + (block 당처리시간 block 수 ) = 25.7 sec sec = 42.6 sec 3. Double buffering 을사용할경우 file 을입력하여처리하는데걸리는시간? 한 block 입력시간 = 25.7 sec / 33,881 = 0.76 msec 입력시간 > 처리시간 (0.5 msec) 이므로 I/O bound job. 전체시간 = ( 입력시간 / block block 수 ) + 마지막 block 처리시간 = 25.7 sec ms

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