기억장치관리 (Memory Management) 배경 (Background) Source Program ( 심볼주소 ) Compiler Object Module ( 재배치가능주소 ) Linkage Editor & Loader Binary Run-time Module ( 절대주소 ) X 14(bytes offset) 74014(R+14) 주소바인딩 (Address Binding)» 한주소공간에서다른주소공간으로의사상 (mapping)» 주소바인딩시점 1 Compile time : 시작주소미리아는경우» compile 후 absolute code 생성, 시작주소바뀌면 recompile» ( 예 ) MS-DOS, COM programming 2 Load time : 시작주소모를경우» compile 후 relocatable code 생성 (binder 가주소바인딩 ), 시작주소바뀌면 reload 만 3 Execution time : 한프로세스가수행도중다른 memory segment 로이동하는경우» 동적재배치 (dynamic relocation)» H/W 지원필요 : relocation register 가진 MMU(p297) 9.1
사용자프로그램의다단계처리 9.2
동적적재 (Dynamic Loading) 와동적연결 (Dynamic Linking) 동적적재 (Dynamic Loading)» 각루틴들이 call 되었을때적재됨 : runtime 에 load ( 예 ) error routines : 필요할때만적재» 사용자책임 (on users responsibility)» OS 지원 : 동적적재라이브러리루틴제공 동적연결 (Dynamic Linking)» run time 에 linking» ( 예 ) language subroutine library stub 이용 : run-time 에메모리에있으면그곳으로, 없으면 load & link memory resident library routine 의위치를찾아가거나새로 load 하는방법을제공하는 program code» OS 도움필요 : 다른프로세스의 address space 접근지원 (paging)» ( 예 ) shared libraries» ( 예 ) MS.dll (dynamic linking library) (cf.).lib (static linking library) Implicit linking».dll 파일링크».h 파일 ; extern C _declspec(dllimport)void PaintImage(LPSTR filename);» 빈함수정의 ; void PaintImage(LPSTR filename)=0; Explicit linking» Loadlibrary( ExRegularDll.dll ); 9.3
중첩 (Overlays) 중첩 (Overlays)» 주어진시간에꼭필요한명령만메모리에유지 ( 예 ) 2 - pass assembler» user 가전담-> automatic technique(= virtual memory) 9.4
논리적주소공간과물리적주소공간 (Logical versus Physical Address Space) 논리주소 MMU H/W 물리주소 논리주소 (logical address)» program generated 물리주소 (physical address)» 메모리의 Memory Address Register 에적재되는주소 주소공간 (Address Space) 1. logical address space : ~ virtual address 2. physical address space : real address memory mapping H/W = MMU(Memory Management Unit)» 재배치레지스터 (relocation register) 이용 생성된모든주소 + 재배치레지스터값 -> 물리주소» R : base value in relocation register» logical address : 0 ~ max» physical address : R + 0 ~ R + max 9.5
동적재배치 (Dynamic Relocation) 9.6
스와핑 (Swapping) 순환할당스케줄링 : swap-out/swap-in 우선순위스케줄링 : roll-out/roll-in ( 우선순위에따라 ) swap-back 위치» 같은위치 : compile time 또는 load time binding» 다른위치 : execution time binding ready queue 의 processes» memory 에» backing store 에 : swap-in 하기위해다른프로세스 swap-out swap time» swap context-switch time = (transfer time + latency time) x 2 = 216ms» latency time = 8ms» process size = 100k» transfer rate = 1000k» 100k/1000k = 0.1sec = 100ms» no head seek 가정» RR 1-time quantum > 216ms modified swapping» Unix : system load 가클때 OS 가 swapping( 멀티프로그래밍정도를낮춤 )» PC Windows 3.1: user 가 swap-in 선택, swap time 결정» PC Windows/NT : OS 가 full swapping 9.7
연속할당 (Contiguous Allocation) ~ 단일분할할당 (Single-Partition Allocation) 1 배치주소고정 : 2 relocation register + limit register -> 가변 OS size가능 실행시간에필요한 device driver만 load : transient OS code 다중분할할당 (Multiple-Partition Allocation) 1. 고정크기분할 여러개의고정크기분할 다중프로그래밍정도 (degree of multiprogramming) 를제한 ( 예 ) IBM OS/360 MFT2(Multiprogramming with a Fixed number of Tasks) 2. 가변크기분할 hole( 사용가능메모리블럭 ) 에서필요한만큼할당 MVT(Multiprogramming with a Variable number of Tasks) 주로일괄처리환경 외부단편발생가능 OS 지원 : OS 는사용가능 block size 의 list 유지 H/W 지원 : 기준 / 한계레지스터 -> dynamic storage allocation 9.8
연속할당 (Contiguous Allocation) ~» free hole에서 size n 할당하는방법 1. First-fit : first hole (fastest) 2. Best-fit : smallest hole (best) 3. Worst-fit : largest hole ( 경우에따라더유용 ) ( 예 ) 다음장 (c) 에서 100k, 100k, 200k, 160k 할당 OS OS OS OS process 5 process 5 process 5 process 5 process 9 process 9 process 8 process 10 process 2 process 2 process 2 process 2 9.9
기억장치할당예 9.10
연속할당 (Contiguous Allocation) 외부단편과내부단편 (External and Internal Fragmentation) 1) Note : 외부단편 : partition자체가사용되지않음 560K 빈공간에 500K 프로그램담지못함 50% rule : first-fit의경우통계적으로 N 할당블록에대해 0.5N 블록외부단편생김 compaction : 사용가능메모리를한곳으로모음 2) 내부단편 : partition 내부에생긴단편이사용되지않음 3) compaction dynamic relocation인경우에만가능» 각 program마다 base register이용 Compaction + Swapping» roll-back될때dynamic relocation으로 compaction( 적절한위치로 roll-back됨으로써 ) 9.11
압축 (compaction) 9.12
페이징 (Paging) ~ 기본방법 (Basic Method) 1. 물리주소 -> frame( 고정크기블럭 ) 단위로나눔 2. 논리주소 -> page(frame크기 ) 단위로나눔» H/W지원 1 Page table H/W» 각 page의물리주소공간에서의시작주소 : base address» 논리주소 = page number + page offset» 물리주소 = 그 page의물리적시작주소 + page offset 2 address generation H/W(registers) : p270 Figure 9.6» page table참조하여물리주소계산» 논리주소 = 2 m, page size는 2 n : ( 예 ) 512(n=9), 1024(n=10), 2048(n=11), 4096(n=12), 8192(n=13) page number page offset p d m-n n» 외부단편없음, 내부단편생김 ( 마지막 page)» page size 작을수록 내부단편크기? page table 유지 overhead? disk I/O 시간? page size 커지는것이추세 (2048, 4096, 8192) 9.13
페이징예 9.14
페이징 (Paging) ~» 논리주소물리주소 (address-translation H/W) OS 가올바른물리주소생성지원 1 각프로세스마다 page table 유지 : 그페이지가담긴 frame 번호 context-switch time 증가 2 frame 할당상황담은 frame table 유지 : 사용가능 frame list 3 사용자프로세스가자신의주소공간에서동작하는지파악» 페이징은동적재배치 (dynamic relocation) 의한형태 Page Table 의기본구조 (Structure of the Page Table)» H/W 지원 1 register 로» 빠르다. page table 크기작을때가능» ( 예 ) DEC PDP-11 : 16bits address, page size 8K -> 8 page registers 2 memory 에» PTBR(Page-Table Base Register) 로접근» 느리다 (memory 에 2 회접근 ) fast-lookup hardware cache(associative register, translation look-aside buffers; key & value) 로보완 1 보다 10% 의느린속도로 9.15
페이징주소변환하드웨어 (Address Translation Hardware) 9.16
가용프레임 (Free Frames) 9.17
페이징 (Paging) ~» 유효접근시간 (effective access time) (page를 cache에서찾을 ) hit-ratio 80% : 16 registers» i) cache에있으면 20ns(cache access) + 100ns(memory access) -> 120 ns» ii) cache에없으면 20ns + 2 x 100ns ->220ns» 유효접근시간 = 0.80 x 120 + 0.20 x 220 = 140ns (40% slow down) hit radio 98%» 유효접근시간 = 0.98 x 120 + 0.02 x 220 = 122ns (22% slow down) TLB 10~512 개이용하여 80~98% hit-ratio» Motorola 68030 processor : 22 entry TLB» Intel 80486 CPU : 32 entry TBL로 98% hit-ratio» 보호 (Protection) 보호비트 (Protection bit) : read-write, read-only, execute-only 타당 / 비타당비트 (valid/invalid bit) : 논리주소공간에서의유효성여부 전체주소공간 : 2 14 = 16,383 = 2K x 8 페이지크기 : 2K 프로그램크기 : 10469( 주소 : 0 ~ 10, 468) valid : page 0 ~ page 5( 마지막페이지에내부단편 ) PTLR(Page Table Length Register) 사용 9.18
TLB(Translation Look-aside Buffers) 이용페이징하드웨어 9.19
페이지테이블에서유효 (v) 무효 (i) 비트 9.20
페이징 (Paging) ~ 다중레벨페이징 (Multilevel Paging)» 논리주소공간 : 2 32 ~ 2 64 : page table 이매우커짐 페이지크기 : 4K (2 32 /2 12 = 2 20 항목 ) x 4 bytes = 4M page table size 2 레벨 paging : page table 을 4K paging(1k 항목, 각항목 4 bytes) : p286 그림 8.18 유효접근시간 = 0.98 x 120 + 0.02 x 320 = 124ns (28% slow down) page number page offset p d 20 bits 12 bits page number page offset p1 p2 d 10 bits 10 bits 12 bits» VAX : 2 레벨 paging» SPARC(with 32 bits addressing) : 3 레벨 paging» 32bit Motorola 68030 : 4 레벨 paging 5 번 memory access 유효접근시간 = 0.98 x 120 + 0.02 x 520 = 128ns (28% slow down) 9.21
이단계페이지테이블체계 (Two-Level Page-Table Scheme) 0 0 1023 0 1023 1023 0 1023 9.22
페이징 (Paging) 역페이지테이블 (Inverted Page Table)» page table 이너무커서 physical memory 낭비될경우» 각항목의값은 virtual page 값 : p311 Figure 9.14» ( 예 ) IBM System/38 IBM RISC System 6000 IBM RT Hewlett-Packard Spectrum Workstations» 논리주소 (virtual address) : <process-id, page-number, offset> 역페이지테이블에서 <process-id, page-number> search» match 되면그인덱스값이 i 값» 없으면 page fault : 그 process 의 external page table 참조하여 page fault 처리» 물리주소 (physical address) = <i, offset> = i * frame size + offset» page look-up processing 이 time consuming hash table 로보완 : 2 memory accesses(hash table, page table) -> associative memory 로보완 공유페이지 (Shared Pages)» ( 예 ) time-sharing 환경에서 reentrant text editor code 를공유» 재진입코드 (reentrant code, pure code) = non-self modifying code 공유코드의 read-only 성질은 OS 가보장해야» paging : page 단위로 sharing 가능 : 역페이지테이블로는어려움 : 여러 virtual page entries 필요 9.23
역페이지테이블구조 (Inverted Page Table Architecture) 9.24
공유페이지예 (Shared Pages Example) 9.25
세그멘테이션 (Segmentation) ~ 기억장치의사용자관점을지원하는기법 기본방법 (Basic Method)» 메모리에대한사용자관점 /= 실제메모리» 사용자관점 : 임의길이의논리적 segment들의집합 segment : 의미적으로 (semantically) 정의된프로그램의부분들, 예를들면, main, subroutines, functions, data elements,...» 논리주소 : <segment number, offset> s d» 세그먼테이션처리 segmentation : compiler 가 segment 번호 : loader가 Hardware 1 segment table 한계 ( 길이 ), 기준의쌍 2 address generation H/W p315 Figure 9.17 9.26
세그멘테이션예 9.27
세그멘테이션하드웨어 9.28
세그멘테이션 (Segmentation) Segment Table 의구현 1 faster registers 에 2 memory 에 STBR(Segment-Table Base Register) -> Segment Table STLR(Segment-Table Length Register)» 2 회 memory accesses -> associative registers 보호와공유 (Protection and Sharing) 1 보호 Segment : 의미적으로정의된프로그램의부분 (semantically defined portion of the program Segment table 에보호비트 (protection bit) : read-only, execute-only, writable 2 공유 각프로세스는 PCB 에연관된 segment table 유지 : dispatcher 가이용 segment 로정의되어있기만하면각프로세스의 segment table 을통해공유 ( 예 ) 시분할환경의 text editor : p317 그림 9.19 참조 단편화 (Fragmentation)» MVT 처럼외부단편생김 (segment 는 variable length 이므로 ) wait until more memory 또는 compaction 9.29
세그먼트공유 (Sharing of segments) 9.30
Example: The Intel Pentium Supports both segmentation and segmentation with paging CPU generates logical address» Given to segmentation unit Which produces linear addresses» Linear address given to paging unit Which generates physical address in main memory Paging units form equivalent of MMU 9.31
Logical to Physical Address Translation in Pentium 9.32
Intel Pentium Segmentation 9.33
Pentium Paging Architecture 9.34
Linear Address in Linux Broken into four parts: 9.35
Three-level Paging in Linux 9.36
페이지화된세그멘테이션 (Segmentation with Paging) ~ paging+segment» paging : internal fragmentation» segmentation : external fragmentation» ( 예 ) Multics, OS/2 32-bits(Intel 80386) MULTICS» logical address 64K words(= 36 bits) 세그먼트 = 2 6 x 2 10 = 2 16 34 bits 논리주소 : 18-bits segment number + 16-bits offset 1 큰 segment( 외부단편문제있음 ) 를 1K 단어 paging : 6 bits page number, 10 bits offset 각 segment 마다자신의 page table segment table : < 세그먼트길이 (limit), 페이지테이블기준주소 > 의쌍 2 큰 segment table 을 1K 항목 paging : 8 bits page number, 10 bits offset 16 associative registers 이용 <key, value> 24bits frame number 외부단편제거, 내부단편발생, table space overhead 증가 ( 각 segment 마다 page table) 논리주소 segment number offset s1 s2 d1 d2 8 bits 10 bits 6 bits 10 bits 9.37
MULTICS 의페이지화된세그멘테이션 (paged Segmentation) 9.38
MULTICS 의주소변환 (Address-Translation) 9.39
페이지화된세그멘테이션 (Segmentation with Paging) ~ OS/2 32-bits Version» Inter 80386(80486) 구조상의 OS/2 32-bits version» segment 최대개수 : 16K = 2 14 = 2 13 x 2 1» segment 최대크기 : 4G = 2 32» page size : 4K = 2 12» 한프로세스의논리주소공간은 2 partitions» private ~ 8K 개 segments : LDT(local descriptor table) : 각항목 8 bytes» public (shared) ~ 8K 개 segments : GDT(global descriptor table) : 각항목 8 bytes 논리주소 = (16 bits selector, 32 bits offset) s g p 13 bits 1 bit 2 bits segment LDT protection number(~8k) GDT» 6 segment registers : 동시에 6 개세그먼트접근가능» 6 개의 8 bytes micro program registers : LDT 또는 GDT 내용을담을수있는 caches 9.40
페이지화된세그멘테이션 (Segmentation with Paging)» addressing : p321 Figure 9.20 참조 selector -> GDT, LDT entry(base address) + offset = 32 bits 선형주소 (linear address) -> 물리주소로변환 2 32 segment 를 4K paging (1K 항목, 각항목 4 bytes) 하면 2 20 개항목 -> 4M 테이블필요 2-level p1 4K paging p2 d 10 10 12 page swappable directory page table 내인생의신조 나는지식보다상상력이더중요함을믿는다. 신화가역사보다더많은의미를담고있음을나는믿는다. 꿈이현실보다더강력하며희망이항상어려움을극복해준다고믿는다. 그리고슬픔의유일한치료제는웃음이며사랑이죽음보다더강하다는걸나는믿는다. 이것이내인생의여섯가지신조이다. 로버트풀검 9.41
Intel 80386 address translation 9.42