제9장 가상 기억 장치(Virtual Memory)

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

1 제9장 가상 기억 장치(Virtual Memory)
운영체제 9장 제9장 가상 기억 장치(Virtual Memory) 지금까지(8장)는 한 프로세스 전부가 메모리에 적재되어야 실행 가상 기억 장치 : 프로세스가 전부 메모리에 없어도 실행 9.1 배경(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) p313 그림 9.1 참조

2 9.2 요구 페이징(Demand Paging) swapping을 하는 paging system과 유사
운영체제 9장 9.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(p294 그림 9.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에 저장 한 명령어가 여러 기억장소를 변경시킬 때 페이지 부재 발생하면 재시작 어려움 적절한 S/W 적 지원 필요 : undo 등

3 9.3 요구 페이징의 성능(Performance of Demand Paging)
운영체제 9장 9.3 요구 페이징의 성능(Performance of Demand Paging) 유효 접근 시간 = (1-p) x ma(memory access time) + p x page fault time 페이지 부재 서비스 시간 1. 페이지 부재 인터럽트 처리 : 1~100ms 2. 페이지 안으로 읽어 들임 : 24ms 3. 프로세스 재시작 : 1~100ms 디스크 동작 회전지연 시간(latency time) : 8ms - sector에 탐구 시간(seek time) : 15ms - track에 전송 시간(transfer time) : 1ms 기억장치 접근 시간이 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) ② swap-out in swap space

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

5 9.5 페이지 대치 알고리즘(Page-Replacement Algorithms)
운영체제 9장 9.5 페이지 대치 알고리즘(Page-Replacement Algorithms) 참조열(reference string)로 알고리즘 평가  주소/페이지 size＃  random number로 특정 프로세스 추적 일반적 : 한 프로세스에 할당된 frame 수가 많아지면 page-fault 수는 적어짐 p327 그림 9.7 참조 선입 선출(FIFO) 알고리즘 가장 오래된 페이지 대치 FIFO queue사용 구현은 쉬우나 성능이 좋지 않음(15회) Belady의 변이(Belady’s anomaly) 있음 할당된 frame수 증가해도 page-fault수가 증가하는 현상 : p329 그림 9.9 참조 최적(Optimal Algorithm) 알고리즘 가장 오랫동안 사용되지 않을 페이지 대치) Belady의 변이 없음 최소의 page-fault rate(9회) 실제 구현은 어렵지만 (미래 지식필요 : looking forward) 성능이 좋음(9회)

6 9.5 페이지 대치 알고리즘(Page-Replacement Algorithms) [cont.]
운영체제 9장 9.5 페이지 대치 알고리즘(Page-Replacement Algorithms) [cont.] 최근 최소 사용(LRU; Least Recently Used) 알고리즘 replace the page that has not been used for the longest period of time OPT에의 접근(최근의 과거를 미래에서의 근사치로 이용) looking backward OPT 성능이 좋아 자주 이용됨(12회) 구현을 위해 H/W지원 반드시 필요 1) 계수기 논리 클록 또는 계수기 이용 page table에 추가한 time-of-use field 값이 최소인 것을 대치 2) 스택 페이지 번호들의 스택 유지(doubly linked list로) : p332 그림 9.12 top : 최근 사용된 page bottom : LRU page Belady의 변이 없음 stack algorithm : memory에는 n 개의 최근 사용된 페이지 LRU 근접( LRU Approximation) 알고리즘 ① 참조 비트 추가(Additional-reference-Bits) 알고리즘 ② 2차 기회(Second Chance) 알고리즘 ③ 개선된 2차 기회(Enhanced Second-chance) 알고리즘

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

8 9.6 프레임의 할당(Allocation of Frames)
운영체제 9장 9.6 프레임의 할당(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을 자신의 것 중에서 선택 (예) 덜 사용되는 페이지 선택 : 프레임 개수 고정

9 9.7 스래슁(Thrashing) 전역 대치의 결과로 중간 단계 CPU 스케줄링(swap-in/swap-out) 도입
운영체제 9장 9.7 스래슁(Thrashing) 전역 대치의 결과로 중간 단계 CPU 스케줄링(swap-in/swap-out) 도입 우선순위가 낮은 process에 할당된 프레임수가 최소프레임 수보다 적어 지면 그 프로세스 수행을 중지 시키고 swap-out, 나중에 swap-in 활동하는 page 개수 만큼 충분한 프레임이 없으면 자주 page fault가 일어남 방금 대치된 page가 page fault 스레슁 : high paging activity paging만 해 : paging 시간 > 실행 시간 스레슁의 원인 전역 대치(global replacement) : 다른 프로세스의 page를 대치 극단적 thrashing효과 paging device 대기 -> CPU 이용률 저하 -> 멀티프로그래밍 정도 높임 … 악순환 … paging activity만 하고 있음(paging device의 큐가 길어 유효접근 시간이 길어짐) 지역 대치(local replacement) : 그 프로세스의 page를 대치 제한적 thrashing 효과 : 그 process만 thrashing 원인 : 활동적인 page들을 모두 수용할 수 없을 때 현재 locality 크기 보다 적은 수의 frame이 할당되었을 때 한 프로세스는 locality 사이를 이동하면서 수행됨 locality : 동시에 활동하는 페이지들의 집합 (예) Subroutine

10 9.7 스래슁(Thrashing) [cont.]
운영체제 9장 9.7 스래슁(Thrashing) [cont.] 작업 집합 모델(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로 (책 참조) 페이지 부재 빈도 (Page-Fault Frequency) 페이지 부재율 > 상한 -> frame할당 페이지 부재율 < 하한 -> frame제거 직접적인 thrashing 방지법

11 9.8 기타 고려 사항(Other Consideratons)
운영체제 9장 9.8 기타 고려 사항(Other Consideratons) 프리페이징(Prepaging) 페이지 크기(Page Size) 역 페이지 테이블(Inverted Page Table) 프로그램 구조(Program Structure) Page Size : 128 C program : 열 우선(raw- major) main() main() { { int a[128][128]; int a[128][128]; for(j=0; j<128; j++) for(i=0; j<128; j++) for(i=0; i<128; i++) for(i=0; i<128; i++) a[i][j] = 0; a[i][j] = 0; } } 입출력 상호 잠금(Input/Output Interlock) 실시간 처리(Real-Time Processing) 가상 기억 장치 : 페이지 부재 처리로 예기치 않은 긴 지연 시간 초래할 수 있음 실시간 시스템은 가상 기억 장치를 사용 않음 Solaris 2 : time-sharing과 real-time 지원 위해 ① 어떤 페이지가 중요한지 시스템에 힌트를 줌 ② 특권 사용자가 페이지를 메모리에 잠글 수 있게 함

12 9.9 요구 세그멘테이션(Demand Segmentation)
운영체제 9장 9.9 요구 세그멘테이션(Demand Segmentation) paging device 없을 때의 가상기억 장치 (예) Intel 80286상의 OS/2 세그먼트 기술자(segment descriptor) 세그먼트 크기, 보호 비트, 위치 정보 + 타당/비타당 비트 + 접근 비트(accessed bit) 비타당 비트 설정되었으면 세그먼트 부재 트랩 : trap to OS(Segment fault) free memory space조사(필요하면 compaction) i) 있으면 -> OK ii) 없으면 세그먼트 대치(segment replacement) accessed bit 이용하여 최근 사용된 segment가 head인 queue유지 (매 time slice마다 accessed bit 설정된 segment들을 큐의 head에 넣고 나서 accessed bit clear) tail의 segment를 희생자로 선택 세그먼트 기술자 갱신