응용 SW 기초 기술 활용(2)

✔가상기억장치 구현 기법/ 페이지 교체 알고리즘

가상 기억 장치의 개요✨✨✨

-보조기억장치의 일부를 주기억장치처럼 사용하는 것

-용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용할 수 있음

-> 사용 주된 이유: 주기억장치보다 큰 프로그램 수행하기 위해서

-프로그램을 여러 작은 블록 단위로 나누어서 가상 기억장치에 보관해 놓고, 프로그램 실행시 요구되는 블록만 주기억장치에 불연속적으로 할당하여 처리

-주기억장치의 이용률과 다중 프로그래밍의 효율 상승

-가상기억장치에 저장된 프로그램을 실행하려면 가상 기억장치의 주소를 주기억장치의 주소로 바꾸는 주소 변환 작업이 필요(Mapping)

-연속 할당 방식에서 발생 할 수 있는 단편화를 해결할 수 있음

 

 

페이징 기법(분산할당기법) 안

-가상기억장치의 보관되어 있는 프로그램과 주기억장치의 영역을 동일한 크기로 나눈 후 나눠진 프로그램을 동일하게 나눠진 주기억장치의 영역에 적재시켜 실행하는 기법

-프로그램을 일정한 크기로 나눈 크기를 페이지라한다. 페이지 크기로 일정하게 나누어진 주기억장치의 단위를 페이지 프레임이라고함

-외부 단편화는 발생하지 않으나 내부 단편화 발생할 수 있음

-Mapping  작업을 위해 페이지 맵 테이블이 필요함

- 페이지 맵 테이블사용으로 비용증가, 처리속도 감소

 

 

세그먼트 기법(분산할당기법) 밖

-가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행시키는 방법

-기억장치의 사용자 관점을 보존 하는 기법

-프로그램을 논리적인 크기로 나눈 단위를 세그먼트(Segment)라고 한다

-각 세그먼트는 고유한 이름과 크기를 갖는다

-내부단편화는 발생하지 않으나 외부 단편화는 발생할 수 있음

-Mapping 작업을 위해 세그먼트 맵 테이블이 필요함

-세그먼트가 주기억장치에 적재될 때 다른 세그먼트에게 할당된 영역을 침범할 수 없으며 이를 위해 기억장치 보호키가 필요

-기억공간 절약하기위해 사용

 

- 고정크기 분할 : 페이지

- 가변크기 분할 : 세그먼트

ex) 5명이 펜션에 놀러갈 때 

- 페이지 : 고정된 크기인 2인실 방을 3개를 주면 1명의 자리가 남게 됨 -> 내부 단편화 발생

- 세그먼트 : 5인실 방을 만들어서 주면 6명의 인원이 놀러올 때 모두가 못 들어가게 됨 -> 외부 단편화 발생

 

페이지 교체 알고리즘

-페이지 부재(PageFault)가 발생 했을 때 가상 기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데 이럴 경우 주기억장치의 모든 페이지 프레임이 사용 중이면 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 기법

 

-OPT(OPTimal replacement, 최적 교체)

->앞으로 가장 오랫동안 사용하지 않을 페이지를 교체

-> 벨레이디(Belady)가 제안한 것으로 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘이다

 

-FIFO(First in First Out)

-> 페이지가 주기억장치에 적재 될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와서 오래 있었던 페이지를 교체

-> 먼저들어온것이 가장 먼저 나감

->이해하기 쉽고, 프로그래밍 설계 간단

-참조페이지 단위가 없는것 -> 부재발생

 

-LRU(Least Recently Used)  Least:가장적은

->최근에 가장 오랫동안 사용하지 않은 페이지를 교체

->페이지마다 계수기(Counter)나 스택(stack)을 두어 현시점에서 가장 오래전에 사용된 페이지 교체

 

-LFU(Least Frequently Used)

-> 사용빈도가 가장 적은 페이지를 교체

-> 활발하게 사용되는 페이지는 횟수가 많아 교체되지 않는다

-NUR(Not Used Recently)

-> 최근에 사용하지 않은 페이지를 교체

-> 최근 사용여부 확인위해 페이지마다 참조비트와 변형비트를 사용

 

-교체우선순위

 

-SCR(Second Chance Replacement, 2차 기회교체)

SCR은 가장 오랫동안 주기억장치에 있던 페이지중 자주 사용되는 페이지의 교체를 방지하기 위함

FIFO기법의 단점 보완

 

Q.다음과 같은 세그먼트 테이블을 가지는 시스템에서 논리주소(가상주소)(2,176)에 대한 물리주소(실기억주소)는?

A.  논리주소(2,176)

2: 세그먼트 번호

176: 변위값

실기억주소는 시작주소 + 변위값

 

✔가상 기억장치 기타 관리 사항

페이지 크기에 따른 특징

-페이지 크기가 작을 경우

-> 단편화와 주기억장치로 이동하는 시간 감소

-> 불필요한 내용이 적재될 확률이 낮아 워킹 셋이 효율적으로 유지

-> Locality에 더욱 일치하여 기억장치에 효율 상승

-> 페이지 맵 테이블의 크기가 커지므로 매핑 속도가 늦어짐

-> 디스크 접근 횟수가 많아져 전체 입출력 시간이 늘어남

 

-페이지가 클 경우

-> 단편화와 주기억장치로 이동하는 시간이 증가

-> 프로세스 수행에 불필요한 내용까지 적재될 수 있음

-> 페이지 맵 테이블 크기가 작아지므로 매핑 속도가 빨라짐

-> 디스크 접근 횟수가 줄어들어 전체적인 입출력 시간이 줄어듦

 

 

Locality

-프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론

-스래싱을 방지하기 휘한 워킹 셋이론의 기반

-프로세스가 집중적으로 사용하는 페이지를 알아내는 방법

-데닝 교수에 의해 구역성 개념이 증명, 캐시 메모리 시스템의 이론적 근거

 

- 시간구역성

-> 프로세스가 실행되면서 하나의 페이지를 일정 시간동안 집중적으로 액세스(읽는다)하는 현상

-> 시간 구역성이 이루어지는 기억 장소: 반복(Loop), 스택(stack), 부 프로그램(sub routine)