기억장치 관리(Memory Management) 배경(Background) Source Program (심볼 주소) Compiler Linkage Editor & Loader Object Module (재배치 가능 주소) Binary Run-time Module (절대 주소) X 14(bytes offset) 74014(R+14) 주소 바인딩(Address Binding) 한 주소 공간에서 다른 주소공간으로의 사상(mapping) 주소 바인딩 시점 ① Compile time : 시작 주소 미리 아는 경우 compile후 absolute code 생성, 시작주소 바뀌면 recompile (예) MS-DOS, COM programming ② Load time : 시작 주소 모를 경우 compile 후 relocatable code 생성(binder가 주소 바인딩), 시작주소 바뀌면 reload만 ③ Execution time : 한 프로세스가 수행도중 다른 memory segment로 이동하는 경우 동적 재배치(dynamic relocation) H/W지원 필요 : relocation register 가진 MMU(p264) 2000 운영체제

배경(Background) 동적 적재(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 중첩(Overlays) 주어진 시간에 꼭 필요한 명령만 메모리에 유지 (예) 2 - pass assembler user 가 전담 -> automatic technique(= virtual memory) 2000 운영체제

논리적 주소 공간과 물리적 주소 공간 (Logical versus Physical Address Space) 논리 주소 물리주소 MMU H/W 논리 주소(logical address) program generated 물리 주소(physacal 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 2000 운영체제

스와핑(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 process size = 100k transfer rate = 1000k 100k/1000k = 0.1sec = 100ms no head seek 가정 ※ RR 1-time quantum > 216ms modified swapping Unix : system load가 클 때만 swapping허용(멀티프로그래밍 정도를 낮춤) PC Windows : user가 swap-in 선택, swap time 결정 PC Windows/NT : full swapping 2000 운영체제

Schematic View of Swapping 2000 운영체제

연속 할당(Contiguous Allocation) ~ 단일 분할 할당(Single-Partition Allocation) ① 배치주소 고정 : ② 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 2000 운영체제

연속 할당(Contiguous Allocation) ~ free hole에서 size n 할당하는 방법 1. First-fit : first hole 2. Best-fit : smallest hole 3. Worst-fit : largest hole (경우에 따라 더 유용) 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 2000 운영체제

연속 할당(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됨으로써) 2000 운영체제

페이징(Paging) ~ p d m-n n 기본 방법(Basic Method) 1. 물리주소 -> frame(고정크기 블럭) 단위로 나눔 2. 논리주소 -> page(frame크기) 단위로 나눔 H/W지원 ① Page table H/W 각 page의 물리 주소공간에서의 시작주소 : base address 논리주소 = page number + page offset 물리주소 = 그 page의 물리적 시작주소 + page offset ② address generation H/W(registers) : p270 Figure 9.6 page table참조하여 물리주소 계산 논리주소 = 2m, page size는 2n : (예) 512(n=9), 1024(n=10), 2048(n=11), 4096(n=12) 외부단편 없음, 내부단편 생김(마지막 page) page size 작을 수록 내부 단편 크기 ? page table 유지 overhead ? disk I/O 시간 ? page size 커지는 것이 추세(2048, 4096, 8192) d p page number page offset m-n n 2000 운영체제

Address Translation Architecture 2000 운영체제

Paging Example 2000 운영체제

페이징(Paging) ~ 논리주소 물리주소 (address-translation H/W) OS가 올바른 물리주소 생성 지원 논리주소 물리주소 (address-translation H/W) OS가 올바른 물리주소 생성 지원 ① 각 프로세스 마다 page table유지 : 그 페이지가 담긴 frame 번호 context-switch time 증가 ② frame 할당 상황 담은 frame table 유지 : 사용가능 frame list ③ 사용자 프로세스가 자신의 주소공간에서 동작하는지 파악 페이징은 동적 재배치(dynamic relocation)의 한 형태 Page Table의 기본 구조(Structure of the Page Table) H/W지원 ① register로 빠르다. page table 크기 작을 때 가능 (예) DEC PDP-11 : 16bits address, page size 8K -> 8 page registers ② memory에 PTBR(Page-Table Base Register)로 접근 느리다(memory에 2회 접근) fast-lookup hardware cache(associative register, translation look-aside buffers; key & value)로 보완 ① 보다 10%의 느린 속도로 2000 운영체제

페이징(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) : 논리주소 공간에서의 유효성 여부 전체주소 공간 : 214 = 16,383 = 2K x 8 페이지 크기 : 2K 프로그램 크기 : 10469(주소: 0 ~ 10, 468) valid : page 0 ~ page 5(마지막 페이지에 내부 단편) 2000 운영체제

페이징(Paging) ~ p d p1 p2 다중 레벨 페이징(Multilevel Paging) 논리주소공간 : 232 ~ 264 : page table이 매우 커짐 페이지 크기 : 4K (232/212 = 220 항목) 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) 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) d p page number page offset 20 bits 12 bits p1 p2 10 bits 10 bits 2000 운영체제

Two-Level Page-Table Scheme 2000 운영체제

페이징(Paging) 역 페이지 테이블(Inverted Page Table) page table이 너무 커서 physical memory 낭비될 경우 각 항목의 값은 virtual page 값 : p282 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 필요 2000 운영체제

Inverted Page Table Architecture 2000 운영체제

Shared Pages Example 2000 운영체제

세그멘테이션(Segmentation) ~ 기억장치의 사용자 관점을 지원하는 기법 기본 방법(Basic Method) 메모리에 대한 사용자 관점 /= 실제 메모리 사용자 관점 : 임의 길이의 논리적 segment들의 집합 segment : 의미적으로(semantically) 정의된 프로그램의 부분들, 예를 들면, main, subroutines, functions, data elements, ... 논리주소 : <segment number, offset> s d 세그먼테이션 처리 segmentation : compiler가 segment 번호 : loader가 Hardware ① segment table 한계(길이), 기준의 쌍 ② address generation H/W p286 Figure 9.17 2000 운영체제

Logical View of Segmentation 1 4 2 3 1 2 3 4 user space physical memory space 2000 운영체제

세그멘테이션(Segmentation) Segment Table의 구현 ① faster registers에 ② memory에 STBR(Segment-Table Base Register) -> Segment Table STLR(Segment-Table Length Register) 2회 memory accesses -> associative registers 보호와 공유(Protection and Sharing) ① 보호 Segment : 의미적으로 정의된 프로그램의 부분 (semantically defined portion of the program Segment table에 보호 비트(protection bit) : read-only, execute-only, writable ② 공유 각 프로세스는 PCB에 연관된 segment table 유지 : dispatcher가 이용 segment로 정의되어 있기만 하면 각 프로세스의 segment table을 통해 공유 (예) 시분할 환경의 text editor : system p207 그림 8.25 참조 단편화(Fragmentation) MVT처럼 외부단편 생김(segment는 variable length이므로) wait until more memory 또는 compaction 2000 운영체제

Sharing of segments 2000 운영체제

페이지화 된 세그멘테이션(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) 세그먼트 = 26 x 210 = 216 34 bits 논리 주소 : 18-bits segment number + 16-bits offset ① 큰 segment(외부단편 문제 있음)를 1K 단어 paging : 6 bits page number, 10 bits offset 각 segment 마다 자신의 page table segment table : <세그먼트 길이(limit), 페이지 테이블 기준 주소>의 쌍 ② 큰 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) 논리 주소 d1 d2 s1 s2 segment number offset 8 bits 10 bits 6 bits 10 bits 2000 운영체제

MULTICS Address Translation Scheme 2000 운영체제

Address-Translation Scheme 2000 운영체제

페이지화된 세그멘테이션(Segmentation with Paging) ~ OS/2 32-bits Version Inter 80386(80486)구조 상의 OS/2 32-bits version segment 최대 개수 : 16K = 214 = 213 x 21 segment 최대크기 : 4G = 232 page size : 4K = 212 한 프로세스의 논리주소공간은 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) 6 segment registers : 동시에 6 개 세그먼트 접근 가능 6개의 8 bytes micro program registers : LDT 또는 GDT 내용을 담을 수 있는 caches s g p 13 bits 1 bit 2 bits segment LDT protection number(~8K) GDT 2000 운영체제

페이지화된 세그멘테이션(Segmentation with Paging) addressing : p292 Figure 9.20 참조 selector -> GDT, LDT entry(base address) + offset = 32 bits 선형주소 (linear address) 232 segment를 4K paging (1K 항목, 각 항목 4 bytes)하면 220 개 항목 -> 4M 테이블 필요 2-level 4K paging p1 p2 d 10 10 12 page swappable directory page table 내 인생의 신조 나는 지식보다 상상력이 더 중요함을 믿는다. 신화가 역사보다 더 많은 의미를 담고 있음을 나는 믿는다. 꿈이 현실보다 더 강력하며 희망이 항상 어려움을 극복해 준다고 믿는다. 그리고 슬픔의 유일한 치료제는 웃음이며 사랑이 죽음보다 더 강하다는 걸 나는 믿는다. 이것이 내 인생의 여섯 가지 신조이다. 로버트 풀검 2000 운영체제

Intel 80386 address translation 2000 운영체제