목표 메모리하드웨어를구성하는다양한방법소개 프로세스에게메모리를할당하는다양한기법설명 현대컴퓨터시스템에서 paging 동작방법논의 8 장. 메모리관리 2 8. 배경지식 메모리보호 Base 와 Limit Registers 사용 프로그램은디스크에서메모리로적재된후실행됨 프로세스 disk program load memory PCB process CPU 가직접접근가능한기억장치 - CPU register, main memory CPU registers CPU clock 에접근가능 main memory 접근에여러 CPU cycle 이소요 processor stall 발생 cache 메모리를 CPU 와 main memory 사이에추가하여 processor stall 빈도를감소시킴 메모리보호 (Protection) 올바른동작을보장하기위해서메모리보호가필요함 메모리보호를위해하드웨어지원이필요, 운영체제는이를관리함 메모리보호방법 프로세스에게독립된주소공간을제공 base register 와 limit register 를사용한방법 프로세스의합법적인 (legal) 주소공간 : base address < base+limit + 프로세스에게독립적인주소공간을제공하기위해서는주소공간이서로중첩되지않게모든프로세스의 base/limit 를설정해야함 3 4
메모리보호 - Base 와 Limit Registers 를사용한주소검사 주소바인딩 (Address Binding) 하드웨어를통한주소검사 합법적인아닌주소에대해서는 trap 을발생시켜서메모리를보호함 주소의표현 source program prog.c compiler prog.o prog.obj linkage editor or loader prog prog.exe symbolic address relocatable address absolute address (count) (start+4) (7404) base 와 limit registers 는특권명령어만값을적재할수있음 운영체제에의해서만적재가능 운영체제는메모리영역접근에제약이없음 사용자메모리영역, 운영체제메모리영역모두접근가능 5 주소바인딩 (Address Binding) 한주소공간에서다른주소공간으로맵핑하는것 프로그램의명령어 / 데이터주소를물리적메모리주소로 바인딩 (logical address) (physical address) 링커 (linker, linkage editor) 와로더 (loader) linker : 모듈을함께묶어서실행파일을생성함 loader : 프로그램실행을위해서프로그램의전부또는일부를메모리에적재함 6 사용자프로그램의다단계처리과정 주소바인딩시점 compile time source program compiler/ assembler relocatable object code other object codes linkage editor (linker) executable binary file secondary storage library cddes load time loader dynamically loaded library in memory binary image dynamic linking execution time main memory Compile time: 컴파일시점에서프로그램이적재될메모리위치를미리안다면, 컴파일러는 absolute code 를생성할수있음 적재될시작위치가변경된다면, 코드를다시컴파일해야함 Load time: 컴파일시점에서프로그램이적재될위치를알지못하면, 컴파일러는 relocatable code 생성해야함 주소바인딩은 load time 에수행됨 - 메모리위치는적재시에결정됨 Execution time: 프로세스가실행도중에메모리위치를이동할수있다면, 주소바인딩은 load time 에할수없고, run time 에수행됨 주소맵핑을위한하드웨어지원이필요 MMU 대부분의운영체제가이방법을사용 정적바인딩 (Static Binding) 과동적바인딩 (Dynamic Binding) Compile time, Load time binding static binding Execution time binding dynamic binding 7 8
논리주소공간과물리주소공간 논리주소 (logical address) 와물리주소 (physical address) logical address(virtual address): 프로그램이사용하는주소 physical address: 물리적메모리장치가사용하는주소 메모리관리장치 (MMU) 논리주소를물리주소로맵핑하는작업을실행시간에수행 프로그램은논리주소만사용하며, 실제물리적주소를알지못함 주소바인딩시점과논리 / 물리주소 compile-time 과 load-time 바인딩 logical addr = physical addr execution-time 바인딩 logical addr physical addr 재배치 (relocation) 레지스터를사용한동적재배치 relocation register = base register recent processor logical address MMU CPU physical address logical = physical address address Memory ( 예 ) Intel 80x86 family: 4 또는 6 relocation registers (CS, DS, ES, SS / FS, GS) 9 0 동적적재 (Dynamic Loading) 동적적재 (Dynamic loading) 실제호출되기전에는각루틴은메모리로적재되지않음 호출될때에메모리에적재되어있지않으면 relocatable linking loader 를호출하여요구하는루틴을메모리에적재한후실행 장점 향상된메모리공간활용 ; 사용하지않는루틴은적재되지않음 많은양의코드가덜빈번히사용되는경우에유용 ( 예 ) 오류처리코드 동적적재는운영체제의특별한지원을필요로하지않음 프로그래머가동적적재를위한설계를책임짐 운영체제는동적적재를지원하는 library 루틴을제공할수있음 동적링크와공유라이브러리 정적링크 (Static linking) 와동적링크 (Dynamic linking) 정적링크 linkage editor 에의해 library 가실행이미지에링크됨 동적링크 library 의링크가실행시간까지미루어짐 Stub library 를어떻게찾는지를알려주는작은코드 library 루틴이메모리에존재하지않으면디스크에서적재함 library 함수를호출하면처음에는 stub 코드가호출됨 stub 는실제 library 함수의주소로대체되어, 다음호출시에는 library 함수를직접호출하여실행 Shared library: 동적링크라이브러리 (dynamic linked library:dll) 공유라이브러리를사용하는모든프로세스는한개의 library 코드만공유하여사용 library 업데이트가용이함 버전정보사용하여구분 동적적재와다르게동적연결은운영체제의도움이필요 운영체제가라이브러리루틴이메모리에있는지여부를검사하며 여러프로세스가라이브러리를공유할수있게해줌. 2
8.2 스와핑 (Swapping) Schematic View of Swapping 스와핑 (Swapping) 실행을계속할수없는 ( 예 : 입출력완료대기 ) 프로세스를메모리에서일시적으로예비저장장치 (backing store) 로내보내고 (swap out), 실행을계속할수있는프로세스를예비저장장치에서메모리로불러오기 (swap in) 하여실행을재개할수있게하는것 ( 다음쪽그림 ) 예비저장장치 (Backing store) 모든프로세스의메모리 image 의복제본을저장할수있을정도의저장용량을가진빠른디스크를사용 - 빠른접근을위해서저장된메모리 image 에대해직접접근이가능해야함 스와핑의효과 " 모든프로세스의물리적주소공간의합 > 물리적메모리크기 " 인경우에도모든프로세스가동시에실행되는것이가능 3 4 스와핑과 Context switching 시간 스와핑과입출력 스와핑동작. CPU scheduler 가 ready queue 에서다음프로세스결정하고 dispatcher 를호출 2. Dispatcher 는다음프로세스가메모리에있는지또는예비저장장치에있는지확인 메모리에없고, 여유메모리영역이없다면, 메모리에있는한프로세스를내보내고 (swap out), 원하는프로세스를메모리로불러오기 (swap in) 를수행 swap out 후 swap in 수행 메모리에없지만여유메모리영역이있다면, 원하는프로세스를메모리로불러오기 (swap in) 를함 swap in 만수행 3. Dispatcher 는 context switching 을수행 Context switch 시간 context switch time > swap in time + swap out time swap 시간의대부분이디스크전송시간 (transfer time) 임 전송시간은스왑되는메모리양에비례함 시간감소방안 : 실제로사용되는부분만불러오기함 (swap in) 메모리요구사항변화발생시에시스템에알려주어야함 5 스와핑되는 (swap out) 프로세스는완전히 idle 상태이어야함 진행중인 (pending) I/O 를갖는프로세스 스와핑하지않음 더블버퍼링 (double buffering) 운영체제 buffer 를통하여입출력연산수행 프로세스가 swap in 될때, 운영체제버퍼와프로세스메모리간에입출력데이터전송 memory process memory I/O 6
여러가지 Swapping 기본스와핑 (Standard Swapping) RR 스케줄링 - quantum이종료된프로세스를 swap out, 여유메모리를다른프로세스에게할당 우선순위스케줄링 낮은우선순위프로세스를 swap out, 높은우선순위프로세스들에게할당 현대운영체제에서는사용하지않음 변형된 (modified) 스와핑 많은시스템에서널리사용 UNIX, Linux, Windows 평상시에는 Swapping 비활성화 여유메모리양이일정기준 (threshold) 이하가되면 Swapping 시작 여유메모리양이증가하면 Swapping 은다시정지됨 또다른변형된스와핑 프로세스의일부만스와핑 swap 시간감소 모바일시스템에서의 Swapping 모바일시스템은대개 swapping 을지원하지않음 영구저장장치로하드디스크대신에플래시메모리를사용 스와핑을하지않는이유 - 플래시메모리는다음특성을가짐 () 공간제약 (2) 허용된쓰기횟수의제한 Swapping 대신사용하는방법 i 는여유메모리가 threshold 보다작아지면응용프로그램에게메모리를반환하도록요청 읽기전용데이터만제거 충분한메모리를반환하지않은응용은프로세스를종료시킴 Android 는여유메모리가충분하지않으면응용프로그램의상태를플래시메모리에저장하고프로세스를종료시킴 빠른재시작가능 7 8 8.3 연속 (Contiguous) 메모리할당 메모리맵핑과보호 주메모리는두부분으로구분 상주운영체제용 인터럽트벡터를포함하는위치사용 대개하위메모리 (low memory) 에위치 사용자프로세스용 상위메모리 (high memory) 에위치 프로세스메모리할당방법 연속 (contiguous) 메모리할당 비연속 (Noncontiguous) 메모리할당 N- user processes high intr vector 0 low 재배치레지스터 (Relocation register) 방법 메모리관리장치 (MMU: memory management unit) 는다음두레지스터를사용하여메모리주소맵핑 재배치 (Relocation) register: 프로세스가배치된물리적주소의시작주소저장 상한 (Limit) register: 논리주소 (0부터시작 ) 의범위를저장 메모리보호 메모리주소범위를하드웨어를사용하여합법적인범위로제한하여이프로세스가다른프로세스와운영체제를수정하는것을방지함 ( 다음슬라이드 ) MMU 는동적으로논리주소를물리주소로맵핑 운영체제와프로세스크기를동적으로변경하는효과적수단제공 ( 예 ) transient code and buffer contiguous noncontiguous 9 20
Hardware support for relocation and limit registers 0 logical address < limit protection 메모리할당 (Memory Allocation) 고정분할방식 (Fixed partition scheme) 메모리를몇개의고정크기영역으로분할 동일크기 (equal size) 분할 다른크기 (unequal size) 분할 각분할은정확히한프로세스를포함할수있음 degree of multiprogramming the number of partition 가변분할방식 (Variable partition scheme) 분할은가변길이및개수를가짐 운영체제는다음정보를관리 allocated partitions free partitions (holes) available 프로세스를수용할수있는크기의 hole 에서메모리를할당 hole 이너무크면, 한부분을할당하고나머지부분은 hole 의집합을반환함. 2 22 Fixed partition Variable Partition Scheme P (20M) hole (36M) P (20M) P2 (4M) (22M) P (20M) P2 (4M) P3 (8M) P (20M) (4M) P3 (8M) P (20M) P4(8M) (6M) P3 (8M) (20M) P4(8M) (6M) P3 (8M) P2 (4M) (6M) P4(8M) (6M) P3 (8M) P2 (4M) (20M) P3 (8M) merging of holes (4M) (4M) (4M) (4M) (4M) (4M) 23 24
동적메모리할당문제 메모리단편화 (Memory Fragmentation) ( 문제 ) free hole의리스트에서크기 n의메모리요청 First-fit: 요청을수용할수있는 first hole을할당 검색시작위치 () 리스트의시작 request 70K (2) 이전 first-fit 검색이종료된위치의 hole Best-fit: 요청을수용할수있는 smallest hole 을할당 리스트가크기순서로정렬되어있지않으면전체리스트를검색해야함. 가장작은크기의남은 hole 생성 Worst-fit: 요청을수용할수있는 largest hole 을할당 전체리스트를검색해야함. Performance first-fit best-fit worst-fit 00K 80K 50K 50K First-fit 와 best-fit 방식이검색시간과기억장치이용률 에있어서 worst-fit 방식보다좋음 Memory Fragmentation 사용할수없는작은메모리영역이존재함 메모리단편화의종류 외부단편화 (External fragmentation) 요청한크기보다작은메모리블록들만존재 전체메모리크기합이요청한크기보다큰경우에도요청한크기의메모리를할당할수없음 내부단편화 (Internal fragmentation) req size 요청한것보다더큰메모리를할당 할당된메모리의일부가사용되지않음 external fragmentation req size internal fragmentation 25 26 단편화 (Fragmentation) 방식의문제 External fragmentation 50-percent rule: N 개의블록이할당되었을때, first-fit 방식은 0.5N 개의블록이외부단편화로사용될수없음 메모리의 /3 을낭비 hole 을추적하는오버헤드가큼 Internal fragmentation 메모리를고정된크기의블록으로분할 hole 의추적이필요없음 할당된메모리는요청한메모리보다더클수있음 할당된메모리의일부영역은사용되지않음 압축 (Compaction) 외부단편화문제에대한해결책. 압축 (compaction) 2. 비연속물리메모리공간허용 paging Compaction segmentation 모든 free memory 를하나의큰블록으로합쳐서재배치. Compaction 은 relocation 이동적이고실행시간에수행될때에만가능 27 28
8.5 페이징 (Paging) Paging 비연속 (noncontiguous) 물리적메모리할당방법중하나 page frame : 물리적메모리를고정된크기의블록들로나눔 ( 크기는 2 n, 대개 52B ~ 8KB). page: 논리메모리를같은크기의블록으로나눔 page 를 page frame 에맵핑 주소변환방식 논리주소를다음과같이구분 상위부분 : page number 하위부분 : page 내에서의 page offset (page size=2 d 이면 d 비트 ) 주소변환 : 논리주소의 page number 를물리주소의 page frame number 로변환 주소변환에 page table 을사용 0 2 3 4 5 6 7 page logical address space mapping 0 2 3 4 5 physical address space page frame logical address page no. (p) mapping physical address page frame no. (f) page size는하드웨어에서정해짐 offset (d) offset (d) d (page size = 2 d ) 29 30 Paging hardware: page table Paging 예 Page Table 각페이지의 base address(page frame number) 들을저장한물리적메모리에있는테이블 page number 가 page table 의 index 로사용됨 page number (p) page frame number(f) page table 은주메모리에위치 3 32
Paging 예 (2) Page 할당 Process A Process B 2 0 6 B-page B-page0 B-page2 프로세스마다자신의 page table 을가지고있으며자신의논리주소공간을가짐 33 Page 할당 모든 free frame 을추적 free frame list 를사용 n page 크기의프로그램을실행시키려면 n free frame 을찾아서 page 를할당하고, 할당된 frame 에프로그램을적재함 주소변환을위해서 page table 을할당된 page frame 번호들로설정 (See next slides) 내부단편화 메모리할당단위 : page frame ( 고정크기 ) 내부단편화발생, 외부단편화없음 내부단편화크기 : 프로세스당 /2 페이지크기 작은페이지크기 ( 장점 ) 작은내부단편화 ( 단점 ) 많은수의페이지로인해큰페이지테이블필요 큰페이지크기 ( 단점 ) 큰내부단편화 ( 장점 ) 작은페이지테이블, 효율적디스크 I/O 일부 CPU 와커널은복수의페이지크기를지원 Solaris : 8KB, 4MB Pentium : 4KB, 4MB 34 Free frames Frame table 과 Page table Frame table physical page frame 당한엔트리 frame 의 free/allocated 여부표시 할당되었으면어느프로세스 ( 들 ) 의어느페이지에서맵핑되었는지를기록 운영체제는각프로세스마다자신의페이지테이블을가짐 하드웨어 page table 을사용하는경우 context switching 시에 page table 도백업해야하므로 context-switch time 증가 PC CPU registers PCB state PC registers page table before allocation after allocation hardware page table ` 35 36
Page Table 의구조 Page table 의하드웨어구현. page table 전용레지스터집합 page table이작을때에만 ( 256) 유용함 2. page table을주메모리에유지 page-table base register (PTBR) : page table 시작주소 page-table length register (PTLR) : page table 크기 () (2) page table registers registers PTBR PTLR memory page table 메모리에있는 Page Table 과 TLB 모든 data/instruction 접근에두번의메모리접근필요 the page table 실제로허용될수없음 the data/instruction Translation Look-aside buffer(tlb) 메모리 2회접근문제를해결하기위하여 TLB라고하는 page table entry용캐시를사용 대개 Associative memory를사용하여구현 새로운 page table 을사용할때마다 TLB 내용은 flush 되어야함 일부 TLB 는 address-space identifier(asids) 를함께저장하여 TLB flush 를필요없게함 memory loaded/modified by privileged instruction TLB page table 37 38 Translation Lookaside Buffer(TLB) Paging hardware with TLB TLB 구성 Associative memory parallel search(fully-associative mapped cache) page number p p2 frame number f f2 (asid, p) f 일부 TLB 는 set-associative mapped cache 사용 Address translation (p, d) p is in page number field of TLB, get the frame number TLB hit Otherwise, get frame number from page table in memory TLB miss ( 그리고 page number 와 frame number 를 TLB 에추가 ) 모든 TLB entry 가사용중이면운영체제는새로운 entry 를위해교체대상 entry 를선택해야함 교체정책 : LRU(least recently used), random 39 40
메모리보호 (Memory Protection) 메모리보호를위해 page table entry 에 protection bit 와 valid bit 추가 Protection bits read-write / read-only / executable-only 정의 page 단위의 memory protection 제공 Valid bit (or valid-invalid bit) V= (valid): legal page ( 페이지가프로세스의논리주소공간에있음 ) V=0 (invalid): illegal page frame no. P V 0 2 3 4 eo eo rw ro - 0 page table i386 page table entry Page Table 에서의 Valid/Invalid bit logical PTBR(page table base register) physical Present PTLR(page table length register) 4 42 공유페이지 (Shared Pages) Shared Pages Example paging 의장점 코드를쉽게공유가능 공유코드 (Shared code) 재진입코드 (reentrant code) 는공유될수있음 재진입코드는수행동안변하지않는 (non-self-modifying) 읽기전용 (read-only) 코드임 두개이상의프로세스가같은코드를동시에실행할때에 물리적메모리에있는한개의코드공유 각프로세스의페이지테이블에서같은페이지프레임공유 프로세스마다별도의데이터저장공간사용 공유코드는모든프로세스의논리주소공간에서같은위치에있어야함 43 44
8.6 Page Table 구조 Page Table 의크기 ( 예 ) 32비트논리주소공간, 4KB 페이지크기 2 32 / 2 2 = 2 20 (M) page table entries page table entry크기가 32-bit(4B) 이면 page table 크기는 2 20 * 4B = 2 22 = 4MB 024 page 크기 최신컴퓨터시스템은 2 32 2 64 정도의커다란논리주소공간을사용 해결책 page table 의크기가상당히커진다 연속메모리공간을사용하는 page table 은 page size 보다훨씬큼 Hierarchical Paging Hashed Page Tables Hierarchical Page table (Multilevel Paging) 다단계 page table page table을하나의연속적메모리를사용하지않고 여러개의작은조각 ( 대개 page 크기 ) 으로나누어서계층적으로구현 0 0 2 p p2 d logical address PTBR f f d page directory physical address page table main memory 45 46 Two-Level Page-Table Scheme (Example) Two-level paging - 80386 the page table is paged the page number is divided into () a 0-bit index into page directory (2) a 0-bit index into page table page size = 2 2 = 4KB, page table size = page directory size = 2 0 x 4B/entry = 4KB (page directory) (inner) 47 48
Multilevel Paging (Example) x86-64 long mode paging Three-level paging 예 2 nd outer page outer page p p2 32-bit 0-bit innner page p3 d 0-bit offset 2-bit page larger than page size page size 64-bit logical address 를 32-bit physical address 로변환하는데 4 번의메모리접근이발생할수있음 64-bit architecture 에서는 hierarchical page table 이부적합함 49 50 Hashed Page Tables 주소공간이 32 비트보다커지면 hashed page table 을사용 hashed page table 논리주소의 page number 의 hash function 값을 hashed page table 의 index 로사용함 hash table 의각 entry 는연결리스트를저장 같은 hash function 값을갖는 page 들의 paging 정보저장 연결리스트원소형식 : <page, page frame, next pointer> hashed page table 을사용한주소변환 논리주소의 page number 와해쉬된위치의연결리스트원소들의 page 번호들과차례대로비교함 match 되면 page 를대응되는 page frame 으로변환함 clustered page table page table 의각 entry 가한개의 page 가아닌여러 page 에대한주소변환정보를저장함 논리주소공간을 sparse 하게사용하는경우유용함 Hashed Page Tables( 계속 ) a chain of elements (virtual, physical) 5 52
clustered page table 8.4 Segmentation virtual page number 의상위부분을 hash function 의입력으로사용 하위부분은 page table entry 를선택하는데 block offset 으로사용 프로그램은세그먼트의집합임 사용자관점의메모리 세그먼트는프로그램의논리적단위 main program, procedure, function, local variables, global variables, common block, stack, symbol table, arrays 세그먼테이션 (segmentation) 논리주소 = <segment number, offset> 2 차원주소 주소맵핑을세그먼트단위로수행하는메모리관리방식 2 차원논리주소를 차원물리주소로변환 53 54 Logical View of Segmentation Segmentation 구조 subroutine 2 stack 3 4 main symbol table 4 2 3 Segment table 프로그램의각세그먼트의주소변환정보저장 table entry 형식 base 세그먼트의 starting physical address limit 세그먼트의길이 세그먼트길이가가변이므로메모리할당은동적할당방법을사용 Segment-table base register (STBR) 현재프로세스의 segment table 의시작주소 Segment-table length register (STLR) 현재프로세스의 segment 개수 segment number s 에대해서 s < STLR 이면 s 는합법적 user space physical memory space 55 56
Segmentation 하드웨어와주소변환 Segmentation 예 STBR STLR 57 58 8.7 Example - Intel IA-32 (Pentium) segmentation 과 segmentation with paging 을지원 (in protected addressing mode) 주소변환과정 logical address : <segment, offset> 2 차원주소 linear address : 차원주소 paging 을사용하지않으면 physical address 와같음 physical address Segmentation 과 Paging segmentation: two segment tables LDT(local descriptor table) GDT(global descriptor table) 3 2 32 translate 46-bit logical address into 32-bit linear address paging selector s g p offset s: segment g: GDT/LDT p: privilege level a two-level paging scheme. dir page offset 0 0 2 translate 32-bit linear address into 32-bit physical address 59 60
IA-32 4 32 IA-32 paging multiple page sizes GDTR LDTR 32 4KB, 4MB page segmentation 32 0 0 2 32-bit entry, 20-bit page frame 2-bit offset paging CR3 22-bit offset 6 62 Page Address Extensions (PAE) ARM paging architecture Multiple page sizes 2 9 9 2-bit offset 64-bit entry, 24-bit page frame 24 + 2 = 36 bit physical address 63 64