운영체제(9) Virtual memory

  

1. Review

 
(1) virtual memory management를 하는 이유? locality(지역성) 때문에.
    한정된 메모리의 효율적인 사용
    구현의 효율성(overhead가 안 생기게 등)
(2) Paiging : virtual memory와 physical memory의 size를 같게 해서 효율적으로 관리하는 기법.
(3) Thread of control
    모든 프로그램이 무조건 main memory에 올라올 필요는 없다.
    (물론 main memory에 올라와야만 수행된다.)
    그러므로 program 중 일부만 main memory에 올리자. 
(4) single CPU에서 multitasking을 하는 이유는? I/O에 시간을 많이 사용하기 위해.

 
 

2. Hardware and Control Structures

 
<메모리 관리의 기본적인 두 가지 특성>
(1) 모든 메모리 참조(memory reference)는 [실행 시 동적으로 '물리적 주소'로 변환되는] 논리적 주소다. 
(2) 프로세스는 [실행 동안 main memory에 연속적으로 위치할 필요가 없는] 여러 조각으로 분할 가능하다. 
-> 이 특성들을 가질 경우, execution 동안 프로세스의 모든 페이지 or 세그먼트가 메인 메모리에 없어도 됨.
-> Bad : main memory에 없는 주소가 필요할 때 인터럽트가 생성된다.
    이럴 경우 OS가 프로세스를 차단 상태로 전환한다. 
 
<Real(Physical) and Virual memory>

이 둘은 분리되어 있다 !!
-> 프로세스가 오직 메인 메모리에서만 실행되기 때문에, 해당 메모리를 real memory라고 부른다. 
-> 그러나 user는 [잠재적으로 디스크에 할당된 메모리보다 훨씬 큰 메모리]를 인식한다. 
    이를 virtual memroy라고 부른다. 
-> virtual memory는 효과적인 멀티프로그래밍을 가능하게 한다. 
    user가 메인 메모리의 엄격한 제약을 완화할 수 있게 한다. 
 
<Some example>
[Source program] --> [Absolute Module] --> [Executable Image] 의 과정이 있다. 
(1) 컴파일 : Source program은 가상 주소 공간에서 실행될 수 있도록 컴파일된다. 
    컴파일러는 소스 코드를 읽고, 코드를 컴파일하여 가상 주소 공간에 위치한 Absolute Module을 생성한다. 
    -> Absolute Module : 가상 주소 공간에서 실행 가능한 형태의 목적 코드를 포함한다. 
(2) 로더(Loader) : 로더는 Absolute Module을 가지고 실행 가능한 이미지인 executable image를 생성한다. 
    -> Loader는 가상 주소 공간과 실제 주소 공간 간의 매핑을 수행한다. 
        실행 가능한 이미지를 메모리의 실제 주소 공간에 할당하고, 이를 실행 가능한 형태로 변환한다. 
        virtual과 real 주소 간의 매핑 정보를 페이지 테이블에서 참조하여, 그들 간 변환을 수행한다. 
(3) 실행 : executable image는 실제 주소 공간에서 실행된다. 
    프로그램이 실행되면 OS는 executable image를 실제 주소 공간에 로드하여 실행한다. 
    전에 얻은 매핑 정보를 사용하여, 가상 주소를 실제 주소로 변환한다. 
    -> 가상 주소를 사용하여 실제 주소 공간의 메모리에 접근한다. 
** 가상 주소 공간과 실제 주소 공간의 매핑은 메모리 관리의 일환으로 이루어진다. 
    이는 가상 메모리의 활용 및 보호를 가능하게 한다. 
    프로세스는 메모리 공간의 논리적인 구조를 다룰 수 있고, OS는 메모리의 물리적 할당 관리 가능. 
 
 

3. Locality

 
<Principle of Locality>
(1) 프로세스 내의 프로그램 및 데이터 참조(data reference)가 클러스터링되는 경향이 있음을 의미한다. 
(2) 짧은 기간 동안에는 몇 가지 프로세스만 필요로 한다. 
(3) 따라서, 미래에 어떤 조각이 필요할지에 대한 현명한 추측을 할 수 있다. 
-> 스레싱을 방지하기 위해 가까운 미래에 필요한 프로세스의 일부. 

 
<Locality>
(1) 주소 공간이 논리적으로 분할됨 : {텍스트, 데이터, 스택} or {초기화, 기본, 오류}
(2) Different parts have different reference patterns.
그림 있어도 좋을 듯?
 
<Locality of Reference>
프로그램이 마지막으로 액세스한 위치 근처의 메모리에 액세스한다. 

농도가 진한 곳이 군집화되어 사용된 곳, 이런게 'locality'.

 
 

4. Virtual memory

 
<Virtual memory>
[physical memory(물리적 메모리)]에서 [user logical memory(사용자 논리 메모리)]를 분리한 것.
(1) execution을 위해, 프로그램의 일부만 메모리에 있어야 한다. 
(2) 따라서 논리적 주소 공간(virtual)은 물리적 주소 공간(real)보다 훨씬 크다. 
-> 여러 프로세스에서 주소 공간을 공유할 수 있다. -> 보다 효율적인 프로세스 생성 가능. 
-> 동시에 더 많은 프로그램이 실행된다. 
-> 프로세스 로드 or swap에 필요한 I/O가 감소한다. 

virtual memory가 pyhsical memory보다 크다는 것을 보여준다.

 
<Virtual address space>
프로세스가 메모리에 저장되는 방식에 대한 logical view.
stack이 MAX에서 시작하여 (heap이 up되는 동안) down으로 성장하도록 설계한다. [그림 참고]
-> stack과 heap 사이, 사용되지 않은 주소 공간이 hole이다. 
-> 확장할 구멍이 남아 잇는 희소 주소 공간, sparse는 동적으로 연결된 라이브러리 등을 사용 가능.
가상 주소 공간으로의 매핑을 통해 시스템 라이브러리가 공유된다. 
-> page 읽기/쓰기를 가상 주소 공간에 매핑하여 공유 메모리를 제공한다. 
MMU는 logical(논리적) 메모리를 physical(물리적) 메모리로 매핑해야 한다. 
일반적으로 주소 0에서 시작하며, 공백이 끝날 때까지 contiguous addresses(연속 주소)이다. 
-> 한편, 물리적 메모리는 페이지 프레임으로 구성되어 있다. 
Virtual memory는 Demand paging, Demand segmentation을 통해 구현할 수 있다. 
 

 
<Shared Library using Virtual memory>
다음과 같이 shared page, 즉 page block으로 나누어 관리하면 관리가 쉬우면서도 효과적이다. 

 
 

5. Demand Paging

 
<Demand Paging>
로드 시 전체 프로세스를 메모리로 가져올 수 있다.
또는 필요할 때만 page를 메모리로 가져올 수 있다. 
-> 필요한 I/O와 메모리 감소, 불필요한 I/O 없음, 더 빠른 응답, 더 많은 사용자.
swap 기능이 있는 페이징 시스템과 유사하다. 
(+) Lazy swapper : page가 필요할 때까지 메모리로 page를 스왑하지 않는다. 
    여기서 page를 다루는 스와퍼는 pager이다. 

paging system with swapping

똑같은 말을 반복하는 우리 gpt..

 
<Basic concepts>
스와핑을 사용할 때, pager는 다시 스와핑하기 전에 사용할 페이지를 추측한다. 
대신, pager는 해당 페이지만 메모리로 가져온다. 
해당 page 집합을 어떻게 결정할까? -> 수요 페이징을 구현하기 위한 새로운 MMU 기능이 필요하다. 
(1) 만약 필요한 페이지가 이미 memory resident인 경우 -> non demand-paging과 별 차이가 없다. 
(2) 만약 필요한 페이지가 not memory resident인 경우 
    -> storage에서 페이지를 검색하여, 메모리에 로드해야 한다. (프로그램 동작, 코드 변경하지 않고!)
 
<Valid-Invalid bit>
가상 메모리 시스템에서 페이지 테이블의 엔트리에 사용되는 플래그.
각 페이지 테이블 엔트리마다 존재하며, 해당 페이지가 현재 메모리에 올라와 있는지 여부를 나타낸다. 
(1) 페이지 상태 표시 : 페이지가 유효한지 무효한지를 나타낸다. 
    유효한 페이지는 현재 메모리에 로드되어 있는 페이지, 무효한 페이지는 아직 메모리에 로드되지 X 페이지.
(2) 페이지 폴트 감지 : Page fault가 발생하면 해당 페이지의 bit가 무효한 상태인지 확인된다. 
(3) 페이지 교체 : bit를 확인하여 메모리에 로드되지 않은 페이지를 선택, 교체할 수 있다.
-> 페이지 테이블을 사용하여 가상 주소를 물리 주소로 변환하는 과정에서 Valid-Invalid bit를 확인하여
    유효한 페이지만을 메모리에 로드하고, 무효한 페이지는 필요한 시점에 로드한다.
-> 따라서 메모리 사용량을 최적화할 수 있다.  

v는 memory resident, i는 page fault가 일어난 경우

 
<Steps in Handling a page fault>
(1) 페이지에 대한 참조가 있으면, 해당 페이지에 대한 첫번째 참조가 OS에 트랩된다. 
    -> Page fault
(2) OS는 [잘못된 참조인지 -> 중단], [단지 메모리에 없는지]를 결정하기 위해 다른 테이블 참조.
(3) free frame을 찾는다. 
(4) 예약된 디스크 작업을 통해 page를 frame으로 변환한다. 
(5) 메모리의 page를 나타내도록 테이블을 재설정한다. validation bit, v로 바꾼다. 
(6) page default(페이지 오류)를 발생시킨 명령어를 다시 시작한다. 
-> 즉, page fault 발생 시 필요한 page를 [main memory의 page block]에 가져온다. 
    남는 page block이 없다면? 희생양을 정하고, 그것과 replacement 한다. 

 
<Aspects of Demand paging>
(1) 극한의 경우 : 메모리에 아무 page도 없는 상태에서 프로세스가 시작한다. 
    -> OS가 프로세스의 첫번째 명령어로 명령 포인터를 설정한다. 비메모리 상주면? 페이지 오류 뜨게.
    -> 처음 액세스할 때 다른 모든 프로세스 페이지에 대해 Pure demand paging을 실행한다. 
(2) 실제로, 주어진 지침은 여러 page에 액세스할 수 있다. -> multiple page faults
    -> [메모리에서 2개의 숫자를 추가하고, 결과를 메모리에 다시 저장하는] 명령의 가져오기 및 디코딩 고려.
    -> locality of reference 때문에 Pain이 감소한다. 
(3) demand paging에 필요한 하드웨어를 지원한다. 
    -> Page table with valid/invalid bit
    -> 보조 메모리, Secondary memory(swap space가 있는 스왑 장치)
    -> 명령 재시작. 
 
<Page replacement>
data의 변화가 없다 -> 그대로 overwrite
data의 변화가 있다 -> HDD에 가서 원래 꺼 선택 -> 가져온다. 
페이지 교체를 포함하도록 페이지 장애 서비스 루틴을 수정하여, 메모리 과도 할당을 방지한다. 
modify(dirty) bit를 사용하여 페이지 전송의 overhead를 줄인다. 수정된 페이지만 디스크에 기록된다.
-> 논리 메모리와 물리적 메모리를 분리시켜준다. 
    더 작은 물리적 메모리에 대용량의 가상 메모리를 제공할 수 있다. 

Page replacement가 필요한 경우

 
<Basic page Replacement>
쫓아낼 놈(victim frame)을 찾는 알고리즘.
(1) 디스크에서 원하는 page의 위치를 찾는다.
(2) free frame, 빈 프레임을 찾는다. 
    -> 빈 프레임이 있다면 그것을 사용, 없으면 페이지 교체 알고리즘을 사용.
    -> 페이지 교체 알고리즘 : victim frame을 선택. 더러워진 디스크가 있다면 거기에 피해자 프레임 씌운다.
(3) 원하는 page를 (새로) 사용 가능한 frame으로 가져오고, page and frame table을 업데이트한다. 
(4) trap을 발생시킨 명령어를 다시 시작하여 프로세스를 계속한다. 
-> 이제 페이지 결함에 대해 2 page transters 가능성이 있으므로 EAT가 증가한다. 

 
** Frame-allocation algorithm
    각 프로세스에 제공할 frame 수, 바꿀 frame을 결정하는 알고리즘.
** Page-replacement algorithm : for 낮은 페이지 오류율. 사용 가능한 프레임 수에 따라 결과가 달라진다. 
 
 

6. Demand Paging Algorithm

 
<알고리즘 과정>

 
<Modeling Page Behavior>

(1) R = r₁, r₂, r₃, ...를 page reference stream(페이지 참조 스트림)이라고 하자. 

    -> r_i는 i^th번째 프로세스에서 참조하는 페이지 번호이다. 

    -> subscript(첨자)는 프로세스의 virtual time이다. 

(2) m의 페이지 프레임 할당이 주어지면, t 시간의 메모리 상태 S_t(m)은 set of pages loaded이다. 

(3) S_t(m) = S_t-1(m) [합집합] X_t - Y_t

    -> X_t는 시간 t에서 가져온 페이지 집합이다. 

    -> Y_t는 시간 t에서 교체된 페이지 집합이다. 

 
<Random Replacement>
Frame 숫자가 0,1,2 중에 존재한다면 변화 없이 그대로.
Frame 숫자가 존재하지 않는다면 0,1,2 행렬 중 아무 위치의 숫자와 randomly 교체한다. 
-> m loaded page frames에서 1/m 확률로 Replaced page, y가 선택된다. 
-> R에 대한 지식이 없다. 성능은 bad. 그러나 실행이 easy. 

참고로 언더바로 적힌 부분이 page faults가 발생한 부분이다.

 
<Belady's Optimal Algorithm>
page를 maximal forward destance로 대체한다. 
즉, 교체가 필요할 경우 미래의 숫자들을 보고 '가장 나중에 쓰일 숫자'를 희생양으로 삼아 교체한다. 

-> y_t = max_{xeS t-1(m)}FWD_t(x) 

-> R에 대해 잘 안다. 성능도 good. 미래는 예측불가이므로, 실행이 불가능한 알고리즘. 

이 경우에 4번째 Frame '1'을 보자. '1'이 없으므로 희생양을 찾아 교체하려 할 때, '1' 뒤에 오는 Frame이 '2'와 '0'이므로 안 쓰이는 '3'을 희생양으로 삼고, '1'로 교체한다.

 
<Least Recently Used(LRU)>
미래를 모르니 -> 과거를 사용하자. page를 maximal backward destance로 대체한다. 
즉, 교체가 필요할 경우 이 전 숫자들을 보고 '사용한 지 가장 오래된 숫자'를 희생양으로 삼아 교체한다.

-> y_t = max_{xeS t-1(m)}BKWD_t(x)  

-> Backward(후방) 거리는 Forward(전방) 거리의 좋은 예측 변수이다. (예측성을 보장한다.)

 
<Least Frequently Used(LFU)>
접근 횟수를 본다. 접근 횟수가 적은 숫자를 희생양으로 삼아 교체한다. 

-> y_t = min_{xeS t-1(m)}FREQ(x) 

 
<First In First Out(FIFO)>
메모리에 가장 오래 저장된 페이지를 희생양으로 삼아 교체한다. 

-> y_t = max_{xeS t-1(m)AGE}(x) 

 
<FIFO, OPTIMAL, LRU를 비교>

순서대로 FIFO, optimal, LRU

 
<Stack Algorithms>
page reference stream, R = 012301401234를 page Frame이 3개, 4개 일 때 각각 풀어보자. 
(각각 Belady's, LRU, FIFO를 사용하여 풀자.)
-> LRU는 Stack Algorithms을 보장한다. 
-> Stack Algorithms : t 시간에 m으로 로드된 페이지도 t 시간에 m+1로 로드된다. 
아무튼, LRU의 성능이 가장 좋다 !!
 
<알고리즘에 대한 대책, 업그레이드 정책>
(1) Clock policy 
    페이지 프레임을 원형으로 배치하여 시각화하였다. 
    각 프레임에 '사용 비트'라고 하는 추가 비트를 연결해야 한다. 
    사용된 비트는 1로 변경, 선택한 페이지의 비트가 1인 경우에는 0으로 변경. 

(2) LFU algorithm : 페이지를 가장 작은 카운트로 대체한다. 
(3) MFU algorithm : 아냐.. 가장 작은 카운트 페이지는 곧 사용될 수도 있어 알고리즘
(4) Page-Buffering algorithm
    다음에 올 것들을 미리 계산하여 가져오는 알고리즘. 
    -> 항상 사용 가능한 free frame pool을 유지, 수정된 페이지 목록을 유지
    -> 가능하면 free frame 내용을 그대로 유지하고, 그 안에 무엇이 있는지 기록
 
 

7. Demand Paging and Thrashing

 
<Thrashing>
page fault(페이지 부재)가 지나치게 빈번하게 발생하여 시스템 성능이 저하되는 현상. 
paging 경쟁이 많아지면 program이 수행 안 되고, page fault로 인한 page replacement가 계속 발생한다.
에너지 사용 多.
-> process가 '충분한' page를 가지고 있지 않을 경우, page-fault rate는 매우 높다. 
-> 낮은 CPU 활용률, 시스템에 추가되는 다른 프로세스, 멀티프로그래밍을 더 하려는 OS를 초래한다.

고정 프레임으로 page를 할당할 경우, page replacement만 발생하여 프로세스는 돌아가지 않는다. 프로세스가 몰려드니까 하나도 처리가 안 되고, 결국 그래프 그림대로 고꾸라진다.

 
<Demand Paging and Thrashing>
Demand paging이 작동하는 이유는 Locality model 때문이다. 
-> 프로세스가 한 지역에서 다른 지역으로 migration(이주)된다. 지역이 중복될 수 있다. 
Thrashing이 발생하는 이유는 ∑ size of locality > total memory size 때문이다. 

local(지역) 혹은 priority(우선) 페이지 replacement를 사용하여 효과를 제한할 수 있다. 

 
<Working-Set Model>

고정 프레임에서 thrashing이 일어난다. (sol) 페이지 프레임을 '동적'으로 할당하자. -> 할당된 page frame에서 반복적으로    (1) page fault가 일어나면 : frame을 더 늘린다. 더 할당한다.     (2) page heat가 일어나면 : frame을 줄인다. 덜 할당한다. -> D > m이면 Thrashing, D < m이면 프로세스 중 하나를 일시중단하거나 스왑 아웃한다. 

1,2,5,6,7&nbsp; : frame을 더 늘린다. 3,4 : frame을 줄인다.

 

 
<Page-Fault Frequency> 
WSS보다 더 직접적인 접근 방식.
실제 속도가 너무 낮으면, frame을 줄인다. 실제 속도가 너무 높으면, frame을 늘린다. 

 
 

8. Other Consederations

 
<Page sizes>
page size가 작을수록, internal fragmentation의 양이 줄어든다. (좋아진다.)
-> 그러나 프로세스당 더 많은 page가 필요하다. 
-> 프로세스당 page 수가 많을수록 page table이 커진다. 
-> 고도의 멀티프로그래밍, 대규모 프로그램에선
    active program의 page table 일부가 main이 아닌 virtual memory에 있어야 한다. 
Page size 선택은 Fragmentation(단편화), Resolution, overhead, Locality(지역성) 등을 다 고려해야 한다.
-> 얘네들이 정비례, 반비례 무슨 관계인지 알아보자...

page size가 크면, 지역성이 커진다. ??

 
<Priority Allocation>
프로세스의 [우선 순위]를 보고, 순위가 낮은 프로세스를 victim으로 선정하여 교체한다.
not fair하지만, 안전하고 확실한 방법이다. 
 
 
 
 
 
 
 
 
 
** 응급 반응 시스템에 가상 메모리를 쓰면 안되는 이유는?
(1) (뭐 올라오고, 꽉 찬 상태에서 뭐 제거할 때, 무엇을 희생양으로 제거할 지 결정하는) 시간이 unpredictable.
(2) thrashing