8 장주메모리 (Main Memory) Questions of the day 1. 내부단편화 (internal segmentation) 와외부단편화 (external segmentation) 사이의차이점을설명하고아래메모리기법들에어느단편화가발생할수있는지밝히세요. 1MFT(Multiprogramming with a Fixed number of Tasks) 2 MVT(Multiprogramming with a Variable number of Tasks) 3 페이징 (paging) 4 세그먼테이션 (segmentation) 5 페이지화된세그먼테이션 (segmentation with paging) 2. ( ) 메모리관점과 ( ) 메모리관점과는다르다? 3. 페이징은나누는크기가 ( 같다 / 다르다 )? 4. 세그먼테이션은나누는크기가 ( 같다 / 다르다 )? 5. 베프가무슨뜻? 8.1
기본하드웨어 베이스 (base) 와상한 (limit) 레지스터가논리주소공간을정의 Monitor mode 에서 OS는 monitor 와사용자메모리전체에무제한접근권한가짐 기준 (base) 과한계 (limit) 레지스터적재명령은특권명령임 8.2
주소의할당 (Address Binding) 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 2Load time : 시작주소모를경우» compile 후 relocatable code 생성 (binder 가주소바인딩 ), 시작주소바뀌면 reload만 3 Execution time : 한프로세스가수행도중다른 memory segment로이동하는경우» 동적재배치 (dynamic relocation)» H/W지원필요 : relocation register 가진 MMU( 그림 8.4) 8.3
사용자프로그램의다단계처리 8.4
동적적재 (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 ExRegularDll.dll dll ); 8.5
중첩 (Overlays) 중첩 (Overlays)» 주어진시간에꼭필요한명령만메모리에유지 ( 예 ) 2 - pass assembler» user 가전담 automatic technique (= virtual memory) 8.6
논리적주소공간과물리적주소공간 (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 8.7
동적재배치 (Dynamic Relocation) 8.8
스와핑 (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 t time = (transfer time + latency time) x 2 =?» 회전지연시간 (latency time) = 8ms» 프로세스크기 (process size) = 10M» 전송율 (transfer rate) = 40MB» 전송시간 (transfer time) =?» no head seek 가정» RR 1-time quantum > 516ms modified d swapping» Unix : system load가클때 OS가 swapping( 멀티프로그래밍정도를낮춤 )» PC Windows 3.1: user가 swap-in 선택, swap time 결정» PC Windows/NT : OS가 full swapping 8.9
연속메모리할당 (Contiguous Memory 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 8.10
연속메모리할당 (Contiguous Memory 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 8.11
기억장치할당예 ( 예 ) 기억장치할당예 (c) 에서 100k, 100k, 200k, 160k 할당 8.12
연속메모리할당 (Contiguous Memory Allocation) 외부단편과내부단편 (External and Internal Fragmentation) 1) Note : 외부단편 : partition 자체가사용되지않음 560K 빈공간에 500K 프로그램담지못함 50% rule : first-fitfit 의경우통계적으로 N 할당블록에대해 05N 0.5N 블록 외부단편생김 compaction : 사용가능메모리를한곳으로모음 2) 내부단편 : partition ii 내부에생긴단편이사용되지않음 3) compaction dynamic relocation 인경우에만가능» 각 program 마다 base register 이용 Compaction + Swapping» roll-back 될때 dynamic relocation 으로 compaction( 적절한 위치로 roll-back 됨으로써 ) 8.13
압축 (compaction) 8.14
페이징 (Paging) g) 기본방법 (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) : 그림 8.7» 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 p m-n page offset d n 8.15
페이징예 0 1 2 3 4 5 6 7 8.16
페이징 (Paging)» 외부단편없음, 내부단편생김 ( 마지막 page)» page size 작을수록 내부단편크기? page table 유지 overhead? disk I/O 시간? page size 커지는것이추세 (2048, 4096, 8192) Solaris: $ pagesize a (8192) Linux:? (4096)» 논리주소 물리주소 (address-translation H/W) OS가올바른물리주소생성지원 1 각프로세스마다 page table유지 : 그페이지가담긴 frame 번호 context-switch time 증가 2 frame 할당상황담은 frame table 유지 : 사용가능 frame list 3 사용자프로세스가자신의주소공간에서동작하는지파악» 페이징은동적재배치 (dynamic relocation) 의한형태 8.17
페이징 (Paging) Page Table 의기본구조 (Structure of the Page Table)» H/W 지원 1register로» 빠르다. page table 크기작을때가능» ( 예 ) DEC PDP-11 : 16bits address, page size 8K 8 page registers 2memory에» PTBR(Page-Table Base Register) 로접근» 느리다 (memory에 2회접근 : 1? 2? 2배로느려짐 ) fast-lookup p hardware cache(associative register, translation look-aside buffers; key & value) 로보완 ( 매칭되면 memory 접근보다 10% 미만의시간소모 ) 8.18
페이징주소변환하드웨어 (Address Translation Hardware) 8.19
가용프레임 (Free Frames) 8.20
페이징 (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 8.21
TLB (Translation Look-aside Buffers) 이용페이징하드웨어 8.22
페이징 (Paging)» 보호 (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) 사용 8.23
페이지테이블에서유효 (v) 무효 (i) () 비트 8.24
페이징 (Paging) g) 다중레벨페이징 (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) : 그림 8.14 유효접근시간 = 0.98 x 120 + 0.02 x 320 = 124ns (28% slow down)» VAX : 2 레벨 paging page number page offset p d 20 bits 12 bits page number page offset p1 p2 d 10 bits 10 bits 12 bits» 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) 8.25
이단계페이지테이블체계 (Two-Level Page-Table Scheme) 0 0 1023 0 1023 1023 0 1023 Q: 이때메모리상의페이지테이블크기는? 8.26
Address-Translation Scheme 8.27
Three-level Paging g Scheme 8.28
해시형페이지테이블 (Hashed Page Tables) 주소공간 (address space) 이 32 bits 보다커질경우자주사용 가상페이지번호가페이지테이블의해시값으로해싱됨» 페이지테이블의각항목은같은위치로해싱된항목들의연결리스트체인을가짐» 각원소의필드 가상페이지번호 사상되는페이지프레임번호 연결리스트상의원소포인터 가상페이지번호는연결리스트를따라가며각원소의가상페이지번호를비교» 매칭이발견되면, 해당물리프레임번호를얻음 8.29
해시형페이지테이블 (Hashed Page Tables) 8.30
페이징 (Paging) g) 역페이지테이블 (Inverted Page Table)» page table이너무커서 physical memory 낭비될경우» 각항목의값은 virtual it page 값 : 그림 817 8.17» ( 예 ) 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 th 되면그인덱스값이 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, inverted 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 필요 8.31
역페이지테이블구조 (Inverted Page Table Architecture) 8.32
공유페이지예 (Shared Pages Example) 8.33
세그먼테이션 (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 그림 8.19 8.34
User s View of a Program 8.35
Logical View of Segmentation 1 1 4 2 3 4 2 3 user space physical memory space 8.36
세그먼테이션예 8.37
세그먼테이션하드웨어 8.38
세그먼테이션 (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 : 그림 8.20 단편화 (Fragmentation)» MVT처럼외부단편생김 (segment는 variable length이므로 ) wait until more memory 또는 compaction 8.39
세그먼트공유 (Sharing of segments) 8.40
사례: The Intel Pentium 지원하는주메모리기법» 순수세그먼테이션 (pure segmentation) 과» 페이지화된세그먼테이션 (segmentation with paging) CPU 는논리주소 (logical l address) 생성하여세그먼테이션유니트에보냄 세그먼테이션유니트는선형주소 (linear address) 생성하여페이징유니트에보냄 페이징유니트 (MMU와동일한역할 ) 는주메모리의물리주소 (physical address) 를생성 8.41
페이지화된세그먼테이션 (Segmentation with Paging) g) Pentium 세그먼테이션 (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 bt 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 ti number(~8k) GDT» 6 segment registers : 동시에 6 개세그먼트접근가능» 6개의 8 bytes micro program registers : LDT 또는 GDT 내용을담을수있는 caches 8.42
페이지화된세그멘테이션 (Segmentation with Paging) g) Pentium 페이징» addressing : 그림 8.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 4K paging p1 p2 d 10 10 12 page swappable directory page table 내인생의신조나는지식보다상상력이더중요함을믿는다. 신화가역사보다더많은의미를담고있음을나는믿는다. 꿈이현실보다더강력하며희망이항상어려움을극복해준다고믿는다. 그리고슬픔의유일한치료제는웃음이며사랑이죽음보다더강하다는걸나는믿는다. 이것이내인생의여섯가지신조이다. 로버트풀검 8.43
Pentium에서의논리주소에서물리주소로의변환 (Logical to Physical Address Translation in Pentium) 8.44
Intel Pentium 세그먼테이션 (Intel Pentium Segmentation) 8.45
Pentium 의페이징구조 (Pentium Paging g Architecture) Page Size flag Pentium 의페이지사이즈는? 8.46
Linux 의삼단계페이징 (Three-level Paging g in Linux) Linux 의선형주소 (Linear Address in Linux) 는 4 부분으로나뉨 : 8.47
Intel 80386 address translation 8.48