Chapter 8: Main Memory, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Chapter 8: Memory Management Strategies Background Swapping Contiguous Memory Allocation Paging Structure of the Page Table Segmentation Example: The Intel Pentium 8.2 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Objectives To provide a detailed description of various ways of organizing memory hardware To discuss various memory-management techniques, including paging and segmentation To provide a detailed description of the Intel Pentium, which supports both pure segmentation and segmentation with paging 8.3 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
1.Background Program must be brought (from disk) into memory and placed within a process for it to be run Main memory and registers are only storage CPU can access directly Register access in one CPU clock (or less) Main memory can take many cycles Cache sits between main memory and CPU registers Protection of memory required to ensure correct operation 8.4 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
1.1 기본하드웨어 A pair of base and limit registers define the logical address space Monitor mode 에서 OS 는 monitor 와사용자메모리전체에무제한접근권한가짐 기준 (base) 과한계 (limit) 레지스터적재명령은특권명령임 8.5 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
1.2 주소의할당 (address Binding) Address binding of instructions and data to memory addresses can happen at three different stages Compile time: If memory location known a priori, absolute code can be generated; must recompile code if starting location changes. Cf. MS-DOS,.COM Load time: Must generate relocatable code if memory location is not known at compile time Execution time: Binding delayed until run time if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps (e.g., base and limit registers) 8.6 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Multistep Processing of a User Program 8.7 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
1.3 논리적주소공간과물리적주소공간 (Logical vs. Physical Address Space) 논리주소 ---MMU H/W- 물리주소 논리주소 (logical address) : program generated. Virtual address 물리주소 (physical address) : memory address register에적재되는주소 Memory mapping H/W = MMU(Memory Management Unit) Hardware device that maps virtual to physical address Relocation register 이용 생성된모든주소 + relocation register value 물리주소 R : base value in relocation register logical address : 0 ~ max physical address : R + 0 ~ R + max 8.8 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
동적재배치 (Dynamic relocation using a relocation register) 8.9 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
1.4 동적적재 (dynamic loading) 와동적연결 (dynamic linking) 동적적재 (Dynamic Loading) 프로세스의모든프로그램이물리적메모리에적재된후에실행되어야한다면프로세스의크기가물리적메모리의크기에제한된다. 모든루틴들은호출이요청될때적재됨 : runtime에 load ( 예 ) error routines : 필요할때만적재 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 ); 8.10 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
2. Swapping CPU scheduler : 순환할당스케줄링 : swap-out/swap-in 우선순위스케줄링 : roll-out/roll-in ( 우선순위에따라 ) CPU scheduler dispatcher : 프로세스선택, 필요하면 swap out and swap 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 =?» 회전지연시간 (latency time) = 8ms» 프로세스크기 (process size) = 10M» 전송율 (transfer rate) = 40MB» 전송시간 (transfer time) = (10/40*1000+8)*2=516ms» no head seek 가정 RR 1-time quantum > 516ms modified swapping» Unix : system load 가클때 OS 가 swapping( 멀티프로그래밍정도를낮춤 )» PC Windows 3.1: user 가 swap-in 선택, swap time 결정» PC Windows/NT : OS 가 full swapping 8.11 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) Main memory usually into two partitions: Resident operating system, usually held in low memory with interrupt vector User processes then held in high memory Relocation registers used to protect user processes from each other, and from changing operating-system code and data Base register contains value of smallest physical address Limit register contains range of logical addresses each logical address must be less than the limit register MMU maps logical address dynamically 8.12 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) 3.1 메모리사상과보호 (memory mapping and protection) Memory mapping MMU 가사상 : 동적으로코드의논리주소에재배치레지스터의값을더하여물리적주소의코드를만들어메모리에적재한다. Memory protection CPU scheduler 가프로세스를교체할때 dispatcher 가 context switch 안에 limit register 과 relocation address 를저장및적재하고 CPU 가생성하는모든주소가 limit register 과 relocation address 를점검하므로다른프로그램의접근을막는다. Hardware Support for Relocation and Limit Registers 8.13 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) 3.2 메모리할당 (memory allocation) 단일분할할당 (Single-Partition Allocation) 배치주소고정 : relocation register + limit register 가변 OS size 가능 실행시간에필요한 device driver 만 load : transient OS code 다중분할할당 (Multiple-Partition Allocation) 고정크기분할 여러개의고정크기분할 다중프로그래밍정도 (degree of multiprogramming) 를제한 ( 예 ) IBM OS/360 MFT2(Multiprogramming with a Fixed number of Tasks) 가변크기분할 hole( 사용가능메모리블럭 ) 에서필요한만큼할당 MVT(Multiprogramming with a Variable number of Tasks) 주로일괄처리환경 OS지원 : Operating system maintains information about: a) allocated partitions b) free partitions (hole) H/W 지원 : 기준 / 한계레지스터 dynamic storage allocation 8.14 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) How to satisfy a request of size n from a list of free holes First-fit: Allocate the first hole that is big enough Best-fit: Allocate the smallest hole that is big enough; must search entire list, unless ordered by size Produces the smallest leftover hole Worst-fit: Allocate the largest hole; must also search entire list Produces the largest leftover hole 기억장치할당예 (c) 에서 100k, 100k, 200k, 160k 할당 First-fit and best-fit better than worst-fit in terms of speed and storage utilization 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.15 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) An example of memory allocation 8.16 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) 3.3 Fragmentation 외부단편 (External Fragmentation ) 프로세스의메모리적재가반복 작은메모리조각 ( 사용이불가능한 ) 50-pecent-rule : first-fit 할당방식의경우통계적으로 N 할당블록에대해 0.5N 블록의영역이단편화즉 1/3 이메모리는사용불가 Compaction : 사용가능메모리를한곳으로모음 내부단편 (Internal Fragmentation) partition 내부에생긴단편이사용되지않음 Compaction 사용가능메모리를한곳으로모음 dynamic relocation 인경우에만가능» 각 program 마다 base register 이용 Compaction + Swapping» roll-back 될때 dynamic relocation 으로 compaction( 적절한 위치로 roll-back 됨으로써 ) 8.17 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.3 연속메모리할당 (Contiguous Allocation) 압축 (compression) 8.18 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4 Paging 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) : Figure 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 page offset m n bit n bit» 외부단편없음, 내부단편생김 ( 마지막 page)» page size 작을수록 내부단편크기? page table 유지 overhead? disk I/O 시간? page size 커지는것이추세 (2048, 4096, 8192) 8.19 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4 Paging(~) Paging Hardware 8.20 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4 Paging(~) Paging Model of Logical and Physical Memory An Paging example of 32 byte memory and 4 byte pages physical memory size = 32 byte=2 5 Frame size=page size= 4-byte =2 2 P.A F # 0 1 2 3 4 5 6 7 8.21 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4 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% 의느린속도로 8.22 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4 Paging(~) 페이징주소변환하드웨어 (Address Translation Hardware) 8.23 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
가용프레임 (Free Frames) 8.4 Paging(~) Before allocation After allocation 8.24 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4.2 하드웨어지원 (Implementation of Page Table Page table is kept in main memory Page-table base register (PTBR) points to the page table Page-table length register (PRLR) indicates size of the page table In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction. The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs) Some TLBs store address-space identifiers (ASIDs) in each TLB entry uniquely identifies each process to provide address-space protection for that process 8.25 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4.2 하드웨어지원 (~) Associative Memory Associative memory(tlb) parallel search Page # Frame # Address translation (p, d) If p is in associative register, get frame # out Otherwise get frame # from page table in memory 8.26 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4.2 하드웨어지원 (~) Paging Hardware With TLB 8.27 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4.2 하드웨어지원 (~)» 유효접근시간 (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 PU : 32 entry TBL 로 98% hit-ratio» 보호 (Protection) 보호비트 (Protection bit) on page table : 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.28 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4.3 Memory Protection Memory Protection Memory protection implemented by associating protection bit with each frame Valid-invalid bit attached to each entry in the page table: valid indicates that the associated page is in the process logical address space, and is thus a legal page invalid indicates that the page is not in the process logical address space 8.29 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
8.4.3 Memory Protection Valid (v) or Invalid (i) Bit In A Page Table 8.30 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
4.4 Shared Pages Shared code One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems). Shared code must appear in same location in the logical address space of all processes Private code and data Each process keeps a separate copy of the code and data The pages for the private code and data can appear anywhere in the logical address space 8.31 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Shared Pages Example 4.4 Shared Pages(~) 8.32 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
4.5 Structure of the Page Table Hierarchical Paging Hashed Page Tables Inverted Page Tables 8.33 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.1 Hierarchical Page Tables Break up the logical address space into multiple page tables A simple technique is a two-level page table 다중레벨페이징 (Multilevel Paging) 논리주소공간 : 2 32 에서 단일페이지테이블페이지크기 : 4K(2 12 ) 페이지테이블개수 :100 만 (2 32 /21 12 = 2 20 20 항목 ) 페이지테이블크기 2 20 x 4 bytes = 4M 2 레벨테이블페이지 10bit page number + 10 bit page number page table 을 4K paging(1k 항목, 각항목 4 bytes) : 8.34 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.1 Hierarchical Page Tables(~) Two-Level Page-Table Scheme 8.35 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.1 Hierarchical Page Tables(~) Two-Level Paging Example A logical address (on 32-bit machine with 1K page size) is divided into: a page number consisting of 22 bits a page offset consisting of 10 bits Since the page table is paged, the page number is further divided into: a 12-bit page number a 10-bit page offset Thus, a logical address is as follows: where p i is an index into the outer page table, and p 2 is the displacement within the page of the outer page table Address-Translation Scheme of 2 level paging structure 8.36 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.1 Hierarchical Page Tables(~) Two-level Paging Scheme Three-level Paging Scheme 8.37 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.2 Hashed Page Tables Common in address spaces > 32 bits The virtual page number is hashed into a page table This page table contains a chain of elements hashing to the same location Virtual page numbers are compared in this chain searching for a match If a match is found, the corresponding physical frame is extracted 8.38 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.2 Hashed Page Tables(~) Hashed Page Table 8.39 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
5.3 Inverted Page Table Only one entry for each real page of memory regardless of the number of processes Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs Use hash table to limit the search to one or at most a few page-table entries Used in the 64 bit UltraSparc, PowerPC 8.40 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Inverted Page Table Architecture 8.41 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
6. 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.42 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
6. Segmentation(~) User s View of a Program Logical address space user space Physical address (memory) space 8.43 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Segmentation Architecture 6. Segmentation(~) Logical address consists of a two tuple: <segment-number, offset>, Segment table maps two-dimensional physical addresses; each table entry has: base contains the starting physical address where the segments reside in memory limit specifies the length of the segment Segment-table base register (STBR) points to the segment table s location in memory Segment-table length register (STLR) indicates number of segments used by a program; segment number s is legal if s < STLR 8.44 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
6. Segmentation(~) Segmentation Architecture (Cont.) Protection With each entry in segment table associate: validation bit = 0 illegal segment read/write/execute privileges Protection bits associated with segments; code sharing occurs at segment level Since segments vary in length, memory allocation is a dynamic storage-allocation problem A segmentation example is shown in the following diagram 8.45 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Segmentation Hardware 6. Segmentation(~) 8.46 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Example of Segmentation 6. Segmentation(~) 8.47 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Example: The Intel Pentium 7. Pentium Segmentation 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 Pentinum 에서논리주소가물리주소로변환되는과정 8.48 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Segmentation unit 7. Pentium Segmentation(~) 논리주소 : (select, offset) select : 16 bit : <s(13),g(1),p(2)> s: segment number, g:gdtor LDT, p: protection information GDT(Global Descriptor Table), LDT(Local Descriptor Table) : 8byte로구성, segment의기준위치과길이등의정보 8.49 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
Pentium Paging 32bit linear address : Pentium paging 0 0 0 2 P.s.f=0 10 Page size flag=1 2 12 0 2 10 2 12 8.50 / 50 Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010
End of Chapter 8, Hanbat National Univ. Computer Eng. Dept. Y.J.Kim 2010