기억장치 관리(Memory Management)

Slides:



Advertisements
Similar presentations
Dept. Computer Engineering DBLAB 정보처리개론 담당 교수 : 김정석 2009 년도 1 학기.
Advertisements

컴퓨터의 구조 2006년 2학기 컴퓨터의 개념 및 실습.
OS 소개 Introduction 설계목표 기본 용어 Resource Management History.
마이크로 컨트롤러 Microcontroller.
Linux/UNIX Programming APUE (The Environment of a UNIX Process)
제8장. RISC 및 슈퍼스칼라 프로세서 8.1 RISC의 출현 동기 8.2 RISC의 발전 경위
제 4 장 프로세스 Section 1 프로세스의 개념 Section 2 프로세스 스케줄링
제 2장 컴퓨터 구조.
정보통신실습 및 특강(5)
기본 컴퓨터 프로그래밍 Lecture #6.
Operating Systems Overview
AWR DB 보고서 분석.
Chap. 12 Memory Organization
3장. 컴퓨터의 기억장치 학번 : 이름 : 김현화.
7장 : 캐시와 메모리.
임베디드 하드웨어 Lecture #6.
Uniprocessor Scheduling
운영체제 (Operating Systems)
프로세스 관리.
컴퓨터 과학 개론 √ 원리를 알면 IT가 맛있다 컴퓨터 과학도를 위한 첫 전공서 ehanbit.net.
컴퓨터 구조학 정보보호학과.
임베디드 운영체제 (리눅스 중심) Lecture #2.
2.2 CPU 스케줄링의 목적과 유형 스케줄링의 목적
제 3 장 로더와 링커(Loaders and Linkers)
6장. 기 억 장 치 Lecture #6.
컴퓨터 구조.
4장. 컴퓨터 시스템의 구성과 기능 다루는 내용 컴퓨터 분해를 통한 본체 살펴보기 컴퓨터 구성요소 컴퓨터의 기능
+ 가상 메모리 -> 물리 메모리 Selector Offset DIR Page Segmetatation
운영체제 (OS: Operating System)
SunnyKwak (sunnykwak.egloos.com) 2005년 2월 1일
1 마이크로프로세서의 원리 마이크로컨트롤러 AVR ATmega128.
2장 운영 체제의 개요 운영체제의 개념 운영체제의 유형 운영체제의 발전 과정 운영체제의 구성 운영체제 서비스 시스템 구조
Chap. 12 Memory Organization
Computer Architecture
Geek-OS Project 정영진
3주 컴퓨터구조.
운영체제 (Operating Systems)
운영체제 이나현.
Xen and the Art of Virtualization
제3,4,5장 프로세스, 스레드 관리 CPU 스케줄링.
Chapter 10. 파일 시스템 인터페이스(File System Interface)
파일 시스템 인터페이스(File System Interface)
제 1장 시스템 소프트웨어의 개요.
Fault Diagnosis for Embedded Read-Only Memories
Computer System Architecture
Chapter 4 The Von Neumann Model.
제1장 시스템 소프트웨어의 개요 컴퓨터시스템 및 하드웨어 구성 컴퓨터의 구성과 기능 시스템프로그램의 개요
Chap. 12 Memory Organization
제5장 CPU스케줄링(CPU Scheduling)
제10,11,12장 파일시스템 디스크 스케줄링.
컴퓨터 시스템 개관 시스템 프로그래밍 - Lecture #1 신라대학교 컴퓨터공학과 시스템 프로그래밍.
제10장 파일 시스템 인터페이스(File System Interface)
운영체제(Operating System)
기억장치 관리(Memory Management)
운영체제 (Operating Systems) (Memory Management Strategies)
7장 메모리 관리 메모리 관리를 위한 메모리 할당 기법과 경영에 대해 알아본다. 단편화 현상의 원인과 해결 방법을 알아본다.
컴 파 일 러 Compilers.
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
Chapter 12 Memory Organization
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
Lecture #6 제5장 기억장치 (1).
23. Unix 시스템 커널. 개요 커널의 기본 서비스 커널의 특징 참고서적 프로세스 관리 장치 관리 파일 관리 가상 메모리
CHAPTER 04 파일 설계(FiLE Design).
제1장 정리 컴퓨터소프트웨어과 2-A반 주세호.
제9장 가상 메모리 관리.
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
임베디드 하드웨어 Lecture #6.
Machine architecture Programming Language Design and Implementation (4th Edition) by T. Pratt and M. Zelkowitz Prentice Hall, 2001 Chapter 2.
가상 기억장치 (Virtual Memory)
Presentation transcript:

기억장치 관리(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 운영체제

사용자 프로그램의 다단계 처리 2000 운영체제

동적 적재(Dynamic Loading)와 동적 연결(Dynamic Linking) 각 루틴들이 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”); 2000 운영체제

중첩(Overlays) 중첩(Overlays) 주어진 시간에 꼭 필요한 명령만 메모리에 유지 (예) 2 - pass assembler user 가 전담 -> automatic technique(= virtual memory) 2000 운영체제

논리적 주소 공간과 물리적 주소 공간 (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 2000 운영체제

동적 재배치(Dynamic Relocation) 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 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 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 (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 2000 운영체제

기억장치 할당 예 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 운영체제

압축(compaction) 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), 8192(n=13) 외부단편 없음, 내부단편 생김(마지막 page) page size 작을 수록 내부 단편 크기 ? page table 유지 overhead ? disk I/O 시간 ? page size 커지는 것이 추세(2048, 4096, 8192) d p page number page offset m-n n 2000 운영체제

페이징 예 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 운영체제

페이징 주소변환 하드웨어(Address Translation Hardware) 2000 운영체제

가용 프레임(Free Frames) 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(마지막 페이지에 내부 단편) PTLR(Page Table Length Register) 사용 2000 운영체제

TLB(Translation Look-aside Buffers) 이용 페이징 하드웨어 2000 운영체제

페이지 테이블에서 유효(v) 무효(i) 비트 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) 1023 1023 1023 1023 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 운영체제

세그멘테이션 예 2000 운영체제

세그멘테이션 하드웨어 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의 페이지화된 세그멘테이션 (paged Segmentation) 2000 운영체제

MULTICS의 주소 변환(Address-Translation) 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 운영체제