가상 기억 장치(Virtual Memory)

Presentation on theme: "가상 기억 장치(Virtual Memory)"— Presentation transcript:

1 가상 기억 장치(Virtual Memory)
지금까지(9장)는 한 프로세스 전부가 메모리에 적재되어야 실행 가상 기억 장치 : 프로세스가 전부 메모리에 없어도 실행 배경(Background) 프로그램의 일부만 메모리에 적재하여 실행하는 장점 1) 프로그램 크기가 실제 메모리 크기에 제한 받지 않음 2) 멀티 프로그래밍 정도를 높여 CPU 이용율, 처리율 높임 3) swap I/O 양이 적어 각 프로그램이 빠르게 실행됨 virtual memory 작은 physical memory로 매우 큰 가상 기억 장치(user logical memory) 제공 user logical memory /= physical memory overlay를 사라지게 함 주로 요구 페이징(demand paging)으로 구현됨(OS/2 : demand segmentation) p299 그림 10.1 참조 2000 운영체제

2 요구 페이징(Demand Paging) swapping을 하는 paging system과 유사
lazy swapper처럼 동작하는 pager 꼭 필요한 page만 메모리로 가져오는 pager (cf.) swapper : 전체 프로세스에 대해 동작 page가 memory에 : valid/invalid bit로 valid 표시 disk에 : valid/invalid bit로 invalid 표시 memory에 없는 page참조 -> page fault trap to OS(p302 그림 10.4 참조) 순수 요구 페이징(pure demand paging) 아무 page도 메모리에 가져오지 않은 채 실행 H/W 지원 ① page table : valid/invalid bit 포함 ② secondary memory : swap space 또는 backing store S/W 지원 명령어 인출(fetch)시 페이지 부재 발생하면 그 명령어 다시 인출하여 재시작 3-주소 명령어: 명령어 ADD 인출, A 인출, B 인출, A와 B를 더함, 합을 C에 저장 한 명령어가 여러 기억장소를 변경시킬 때 페이지 부재 발생하면 재시작 어려움 (예) IBM 360/370 MVC(move characters), PDP11의 MOV (R2)+, -(R3) 적절한 S/W 적 지원 필요, undo 등 2000 운영체제

3 Valid-Invalid Bit With each page table entry a valid–invalid bit is associated (1  in-memory, 0  not-in-memory) Initially valid–invalid but is set to 0 on all entries. Example of a page table snapshot. During address translation, if valid–invalid bit in page table entry is 0  page fault. Frame # valid-invalid bit 1 1 1 1  page table 2000 운영체제

4 페이지 부재 처리 과정 2000 운영체제

5 페이지 부재 발생 예 MOV (R2)+, -(R3) IBM 360/370 MVC 명령 재시작 시 R2, R3 값은?
Register에 R2, R3 값 저장 IBM 360/370 MVC 미리 블록의 양끝 조사하여 페이지 확보 1 destination 2(fault) source 2000 운영체제

6 요구 페이징의 성능(Performance of Demand Paging)
유효 접근 시간 = (1-p) x ma(memory access time) + p x page fault time 페이지 부재 서비스 시간 1. 페이지 부재 인터럽트 처리 : 1~100s 2. 페이지 안으로 읽어 들임 : 24ms (디스크 동작) 3. 프로세스 재시작 : 1~100s 디스크 동작 회전지연 시간(latency time) : 8ms - sector에 탐구 시간(seek time) : 15ms - track에 전송 시간(transfer time) : 1ms (EID type: Max. External Transfer Rate=100Mbytes/sec, Spindle Speed=7200rpm) 기억장치 접근 시간이 100ns 일 때의 유효 접근 시간 = (1-p) x (100ns) + p x (25 milliseconds) = (1-p) x p x 25,000,000 = ,999,900 x p 10% 이내로 느려지게 하려면 110 > ,000,000 x p 10 > 25,000,000 x p p < = 1/2,500,000 보다 적게 해야 함 swap space I/O : file system I/O 보다 빠름(큰 block들의 contiguous I/O 이므로) from the swap space (처음 시작할 때 swap space로 file copy) from the file system : BSD Unix ① swap-in only(not modified case, 예 binary files) ② swap-out in swap space 2000 운영체제

7 그리이스 문자 (Greek Alphabet)
2000 운영체제

8 페이지 대치(Page Replacement)
over-allocation 일 때(page fault가 일어났고 free-frame 이 없을 때, p309 그림 10.5)가능한 조치 1. 그 프로세스 종료 2. 한 프로세스를 swap out : multiprogramming의 정도를 낮춤 3. 페이지 대치(page replacement) : p310 그림 10.6 희생될 frame은 swap space로 보내고 그 자리에 page fault 였던 page를 가져옴 2 page transfers(one out & one in) page-fault service time이 2배 modify(dirty) bit으로 보완 요구 페이징 구현 위해 필요한 알고리즘들 프레임 할당 알고리즘 : 각 프로세스에 몇 개의 frame할당? 페이지 대치 알고리즘 : 어떤 frame을 대치(희생자는)? 2000 운영체제

9 페이지 교체의 필요성 i 3 v i 6 v 2000 운영체제

10 페이지 대치 알고리즘(Page-Replacement Algorithms)
페이지 부재율(page-fault rate)이 가장 낮도록 참조열(reference string)로 알고리즘 평가  주소/페이지 size＃  random number로 특정 프로세스 추적 참조열 예 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. 일반적 : 한 프로세스에 할당된 frame 수가 많아지면 page-fault 수는 적어짐 p312 그림 10.7 참조 2000 운영체제

11 페이지 대치 알고리즘(Page-Replacement Algorithms)
선입 선출(FIFO) 알고리즘 가장 오래된 페이지 대치 FIFO queue사용 구현은 쉬우나 성능이 좋지 않음(교재 예제 15회) Belady의 변이(Belady’s anomaly) 있음 할당된 frame수 증가해도 page-fault수가 증가하는 현상 : p314 그림 10.9 참조 2000 운영체제

12 First-In-First-Out (FIFO) Algorithm
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 3 frames (3 pages can be in memory at a time per process) 4 frames FIFO Replacement – Belady’s Anomaly more frames  less page faults 1 1 4 5 2 2 1 3 9 page faults 3 3 2 4 1 1 5 4 2 2 1 5 10 page faults 3 3 2 4 4 3 2000 운영체제

13 페이지 대치 알고리즘(Page-Replacement Algorithms)
최적(Optimal Algorithm) 알고리즘 가장 오랫동안 사용되지 않을 페이지 대치 Belady의 변이 없음 최소의 page-fault rate(교제 예제 9회) 실제 구현은 어렵지만 (미래 지식필요 : looking forward) 성능이 좋음(9회) 2000 운영체제

14 Optimal Algorithm Replace page that will not be used for longest period of time. 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 How do you know this? Used for measuring how well your algorithm performs. 1 4 2 6 page faults 3 4 5 2000 운영체제

15 페이지 대치 알고리즘(Page-Replacement Algorithms)
최근 최소 사용(LRU; Least Recently Used) 알고리즘 replace the page that has not been used for the longest period of time OPT에의 접근(최근의 과거를 미래에서의 근사치로 이용) looking backward OPT 성능이 좋아 자주 이용됨(교재 예제 page-fault rate 12회) 구현을 위해 H/W지원 반드시 필요 1) 계수기 논리 클록 또는 계수기 이용 page table에 추가한 time-of-use field 값이 최소인 것을 대치 2) 스택 페이지 번호들의 스택 유지(doubly linked list로) : p317 그림 10.12 top : 최근 사용된 page bottom : LRU page Belady의 변이 없음 stack algorithm : memory에는 n 개의 최근 사용된 페이지 2000 운영체제

16 Least Recently Used (LRU) Algorithm
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Counter implementation Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter. When a page needs to be changed, look at the counters to determine which are to change. 1 5 2 3 5 4 4 3 2000 운영체제

17 스택을 이용한 LRU 구현 2000 운영체제

18 페이지 대치 알고리즘(Page-Replacement Algorithms)
LRU 근접( LRU Approximation) 알고리즘 ① 참조 비트 추가(Additional-reference-Bits) 알고리즘: 8-bit shift registers 이용하여 참조되면 최상위 비트에 세트하고 매 타이머 인터럽트 마다 한 비트씩 shift-right t0: p0과 p2 참조 p0의 참조비트 p1의 참조비트 p2의 참조비트 t1: p1과 p2 참조 p0의 참조비트 p1의 참조비트 p2의 참조비트 ② 2차 기회(Second Chance) 알고리즘 : p319 Fig 참조 프레임에 들어 있는 페이지들을 원형큐로 유지하면서 참조 비트가 0인 페이지를 탐색하되 참조 비트 값이 1인 페이지들은 0으로 바꾸면서 2차 기회 부여 ③ 개선된 2차 기회(Enhanced Second-chance) 알고리즘 (0,0) 사용되지도 변경되지도 않은 경우 (0,1) 사용되지는 않았지만 변경된 경우 (변경된 후 2차 기회를 받은 경우) (1,0) 사용되었으나 변경되는 않은 경우 (1,1) 사용되고 변경된 경우 2000 운영체제

19 이차 기회 페이지 대치 알고리즘 2000 운영체제

20 페이지 대치 알고리즘(Page-Replacement Algorithms)
계수(Counting) 알고리즘 LFU(Least Frequently Used) 알고리즘 계수 값이 최소인 페이지 대치 MFU(Most Frequently Used) 알고리즘 계수 값이 최대인 페이지 대치 페이지 버퍼링(Page Buffering) 알고리즘 희생될 프레임을 디스크에 기록하기 전에 새 페이지 읽고 희생될 프레임은 빈 프레임의 pool에 더함 확장 변경된 페이지들의 리스트 유지 modify bit set 된 페이지는 idle time에 디스크에 기록하고 modify bit reset pool 내용 기억하고 있다가 (VAX/VMS) 찾는 페이지가 pool에 있으면 바로 이용 없으면 빈 프레임에 읽어 들임 2000 운영체제

21 프레임의 할당(Allocation of Frames)
single-user : free-frame이 없으면 페이지 대치 : 간단 (multi-user) multiprogramming : 여러 프로세스가 메모리에 1. 최소 프레임수 (Minimum Number of Frames) 할당된 프레임 수가 감소하면 page-fault율이 증가 instruction-set 구조 직접 1 주소 형식 : 명령내용, 주소의 내용 : 2 frames 간접 1 주소 형식 : 명령, 주소의 내용이 가르키는 곳의 내용 : 3 frames 2. 할당 알고리즘(Allocation Algorithms) 균일할당(equal allocation) : m/n (m : 프레임 수, n : 프로세스 수) 비례할당(proportional allocation) ① 크기에 비례 최소 프레임수 < ai = Si/S * m (Si : 프로세스 크기, S =  Si),  ai < m ② 우선순위에 비례 ③ 크기 + 우선순위에 비례 3. 전역 대 지역 할당(Global Versus Local Allocation) 페이지 대치 될 때 전역대치(global replacement) : 대치할 Frame을 전체에서 선택 (예) 자신과 우선순위 더 낮은 process의 것 중에서 선택: 프레임 개수 가변 지역대치(local replacement) : 대치할 frame을 자신의 것 중에서 선택 (예) 덜 사용되는 페이지 선택 : 프레임 개수 고정 2000 운영체제

22 스래슁(Thrashing) ~ 전역 대치의 결과로 중간 단계 CPU 스케줄링(swap-in/swap-out) 도입
우선순위가 낮은 process에 할당된 프레임수가 최소프레임 수보다 적어 지면 그 프로세스 수행을 중지 시키고 swap-out, 나중에 swap-in 활동하는 page 개수 만큼 충분한 프레임이 없으면 자주 page fault가 일어남 방금 대치된 page가 page fault 스레슁 : high paging activity paging만 해 : paging 시간 > 실행 시간 2000 운영체제

23 스래슁(Thrashing) ~ 스레슁의 원인 전역 대치(global replacement) : 다른 프로세스의 page를 대치
paging device 대기, ready queue 비게 됨 -> CPU 이용률 저하 -> 멀티프로그래밍 정도 높임 … 악순환 … paging activity만 하고 있음(paging device의 큐가 길어 유효접근 시간이 길어짐) 지역 대치(local replacement) : 그 프로세스의 page를 대치 제한적 thrashing 효과 : 그 process만 thrashing 원인 : 활동적인 page들을 모두 수용할 수 없을 때 현재 locality 크기 보다 적은 수의 frame이 할당되었을 때 한 프로세스는 locality 사이를 이동하면서 수행됨 locality : 동시에 활동하는 페이지들의 집합 (예) Subroutine 2000 운영체제

24 스래슁(Thrashing) 작업 집합 모델(Working-set Model) △ : working-set window
최근의 △ 회 페이지 참조 working-set : △ 페이지 참조인 페이지들의 집합 p344 그림 9.16 참조 -> prepaging에 좋음 D =  WSSi (Working-Set Size i) D > m(총 사용가능 frame 수)이면 thrashing 예방 : 멀티프로그래밍의 정도를 낮춤 근접 working-set 구현 : 고정간격 timer interrupt 와 reference bit로 (예) 5,000번 마다 인터럽트, reference-bit 메모리로 복사하고 clear, △가 10,000인 경우, 메모리의 2개 reference-bit와 현재 reference-bit 조사하여 1인 비트 있으면 working set에 포함 페이지 부재 빈도 (Page-Fault Frequency) 페이지 부재율 > 상한 -> frame할당 페이지 부재율 < 하한 -> frame제거 직접적인 thrashing 방지법 2000 운영체제

25 Page-Fault Frequency Scheme
2000 운영체제

26 가상기억장치 실례 Windows NT 요구페이징(demand paging)과 클러스터링(clustering)
Faulting page 근처의 여러 페이지들을 메모리로 가져옴 각 프로세스마다 Working-set minimum과 maximum(메모리 여유 있을 때) 배정 Free page frames list 유지 Working-set maximum에서 page fault: local, FIFO 페이지 대치 Free memory가 한계값 이하가 되면 automatic working-set trimming: working-set minimum이상의 페이지들 제거 Solaris 2 Page fault 일어나면 free pages의 list에서 페이지 할당 2 파라미터 minfree와 lotsfree 유지 1초에 4번 free memory 조사하여 minfree 상태가 되면 프로세스는 pageout 시작 -> lotsfree 될 때까지 계속 Pageout = Two-handed-clock algorithm second-chance algorithm과 유사: 처음에 reference bit 0으로 설정, 다음번 조사 때 계속 0인 페이지 대치 lotsfree 상태까지 pageout을 할 수 없으면 swapping 시작 2000 운영체제

27 기타 고려 사항(Other Consideratons) ~
프리페이징(Prepaging) 페이지 크기(Page Size) 역 페이지 테이블(Inverted Page Table) 프로그램 구조(Program Structure) Array A[1024, 1024] of integer Each row is stored in one page (C programming language case) One frame Program 1 for j := 1 to 1024 do for i := 1 to 1024 do A[i,j] := 0; 1024 x 1024 page faults Program 2 for i := 1 to 1024 do for j := 1 to 1024 do A[i,j] := 0; 1024 page faults 2000 운영체제

28 기타 고려 사항(Other Consideratons)
입출력 상호 잠금(Input/Output Interlock) 실시간 처리(Real-Time Processing) 가상 기억 장치 : 페이지 부재 처리로 예기치 않은 긴 지연 시간 초래할 수 있음 실시간 시스템은 가상 기억 장치를 사용 않음 Solaris 2 : time-sharing과 real-time 모두 지원 위해 ① 어떤 페이지가 중요한지 시스템에 힌트를 줌 ② 특권 사용자가 페이지를 메모리에 잠글 수 있게 함 2000 운영체제