지밍이 블로그

# Trashing 

> Trashing이 발생하는 과정

1. 시스템에 충분히 많은 Process가 동작 중

2. 동작중인 프로세스가 요구하는 메모리가 가용한 물리 메모리보다 많아서 Page Fault 발생

3. page fault를 처리하는 동안 프로세스는 block 당하고 CPU Utilization이 낮아짐

4. CPU Scheduler는 시스템이 한가한 것으로 판단하고 더 많은 프로세스를 실행하려고 함

5. Memory는 점점 부족하게 됨

=> Trashing은 모든 프로세스가 하나의 physical memory pool을 공유(global page replacement)하기 떄문에 발생하게 됨 

=> Local Allocation(per-process, per-job)을 통해 Thrashing을 해결할 수 있는가?

: 해결할 수 없음. 특정 프로세스가 과도하게 메모리를 사용하여 다른 프로세스가 영향을 받는 현상은 막을 수 없음.

하지만, 시스템의 메모리가 부족한 상황인 경우 어떤 프로세스가 충분한 메모리를 확보하고 있더라도 메모리가 부족한 다른 프로세스에 의해 페이지 폴트 처리가 지연됨에 따라라 성능이 급격히 나빠지는 현상이 발생

> Trashing이 발생하는 본질적인 이유?

현재 active하게 사용되는 메모리보다, physical memory가 부족하기 때문에 발생

* 결국 해결법은, 불필요한 프로세스를 suspend(swapping)나 terminate시키기. (degree of multiprogramming을 낮추기)

* Smartphone 처럼 Swap Device가 없는 경우 많은 프로세스로 인해 메모리가 부족하게된다면?

: suspend(swapping)을 할 수 없으므로, Android의 Low Memory Killer등을 사용하여 프로세스를 Terminate.

* Trashing을 체계적으로 극복하는 방법은?!

# Working Set

: 어느 시점에 특정 프로세스가 Access하는 page들의 집합(프로세스의 locality)

- 1960년대, Peter Demming이라는 사람이 생각해낸 아이디어

- 특정 프로세스이 수행되는 전체 life time동안 working set은 변함 (sub-routin call, jump)

=> locality도 변하게 됨

* Prepaging(Prefetching) : 실제 page 요청이 있기 전에 향후 Access 될 것으로 예상되는 페이지를 미리 메모리에 로드하는 것

> Working Set을 이용한 Prepaging

* Longterm Scheduler : degree of multiprogramming을 낮추기 위해 프로세스를 계속 모니터링하여 메모리의 사용이 없는 프로세스를 선정하는 스케줄러

  Shorterm Scheduler : 다음에 돌아야하는 프로세스를 선정하는 스케줄러

- How ?? Working Set Parameter - 현재부터 과거동안 access된 page 들

- working set param들의 갯수가 너무 적으면 충분한 working set을 확보하기 어렵고,

working set의 windows 사이즈가 너무 크면 불필요한 page들도 포함하게 됨

=> 적합한 working set을 찾아내야 하는 필요가 있음

> Working Set의 단위

- 시간? 어떤 프로세스가 항상 동작하는 것이 아니므로 시간으로 단위를 잡기는 어려움

-  Page Reference 패턴? Page Reference 횟수?  어떤 페이지는 여러 프로세스에서 엑세스 되므로 불필요하게 Working Set으로 잡힐 수 있음

=> working set을 잡는건 어려운 일임

# Working Set의 approximation

- 가정 : 현재 수행중인 프로세스에서 Trashing이 일어나지 않고 잘 수행중이면, 현재 할당된 page들은 그 프로세스의 working set일 가능성이 높음

-  OS는 프로세스의 Page fault를 가지고 현재 프로세스의 수행 상태를 알 수 있음

=> key point !!

> Resident Set

: 어떤 프로세스가 어느 시점에 메인메모리에 가지고있는 페이지 들

* Resident Set이 의미를 가지려면!?

- 프로세스가 fork되는 시점에 프로세스에서 일정한 양의 page frame을 allocation 

- system wide하게 upper bound를 설정.  page fault가 upper bound를 넘어서 발생된다면 해당 프로세스에게 좀 더 많은 frame을 할당(high watermark)

- low bound를 설정. page fault가 low bound보다 낮게 발생된다면 working set windows가 불필요하게 많이 할당되었다는 의미. (low watermark)

<Page Fault 발생 횟수에 따른 운영체제의 Memory 할당 정책>

- Threshold 보다 많이 발생하는 경우 : 해당 프로세스에게 더 많은 메모리를 할당

- Threshold 보다 적게 발생하는 경우 : 해당 프로세스에게 할당된 메모리를 회수

# Memory Management의 Trends

<이슈>

1. Physical Memory의 크기가 커짐

- Page Frame이 넉넉해짐

- Page replacement의 중요도가 줄어들고

- 하드웨어적 서포트가 줄고, 소프트웨어적으로 처리하게 됨

- page의 크기가 커지며,  커버하는 instruction의 크기도 늘어나며 hit rate이 높아지게 됨

2. Virtual Memory의 크기가 커짐

- 64bits with 4K page

-  Large Virtual Memory Management의 중요도가 높아짐

3. Memory Management가 OS의 다른 요소들과 결합

- 과거에 없던 색다른 서비스를 제공 : File System과 접목...

4. Large Page Table의 Handling

- 문제 :

1. page table을 유지하기위해 필요한 공간이 너무 큼

2. page table의 물리 메모리에 연속적인 공간에 존재해야 함 

=> 조각의 단위로 쪼개어 관리하는 기술이 필요

<해결방법>

1. Hierarchical page table ; table space를 줄이진 못하지만 , physical memory상에 조각으로 나누어 적재될 수 있도록

<Two-Level Page Table>

- 32bit 환경에서,

Page Number(22bits), offset(10bits)

=> Page Number = First Level Index(14bits) + Second Level Index(8bits)

* First Level Index == Outer Level Index

- Page Table Entry : 1 word size, 4bytes

- Page Table Size : 2^22 X 4 bytes = 16MB

- 한 page에 존재하는 Page Table Entry의 수 : 256 entries (8 bit)

- 한 Page Table에 존재하는 Page들의 수 : 16K (14 bit)

- First Level Page Table의 크기 : 16K x 4bytes = 64KB

- 공간상의 문제에서 장점을 보이나, 속도면에서의 단점이 있음

2. Hashed page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: hashing기법을 사용하여 page table을 구성

page number를 hash table에서 얻어오기.

3. Inverted page table : page table space의 사이즈를 엄청나게 줄일수 있도록

: 모든 user Process는 독립적인 공간을 같기 떄문에 관리를 위해 별도로 큰 page table을 갖음

- address space 만큼 page table을 갖는게아니라 physical memory만큼 page table을 갖자.

* virtual address space사이즈가 아닌, 실제 시스템에 존재하는 page frame의 갯수만큼 page table을 갖는다.

# Page Replacement Policies

> Page replacement Algorithms

1. Random - 주로 하드웨어 적으로 구현할 때 사용

2. FIFO

- Linked List로 구현

3. Optimal - 가장 먼 미래까지 전혀 사용되지 않을 페이지를 교체. 

* Reference String : Sequenced of Referenced Pages. 어떤 프로세스가 수행하는데 프로세스가 ref했던 시퀀스.

4. LRU - Least Recently Used. 최근에 가장 사용되지 않은 페이지들을 교체. 

Temporal Locality에 기반한 Page Replacement 정책.

Timestamp 사용하여 page frame 하나하나마다 count 정보를 저장해야 하지만 굉장히 오버헤드 크기때문에 Counter 대신 Reference Bit를 사용하기로 함

<Memory Management에서 사용되는 flag bit 종류>

* Reference Bit : Use Bit, Main Memory에 로드된 페이지가 엑세스 되면 Set되는 Bit Flag.

* Resident Bit : 내가 사용려는 page가 1이면 현재 Ram에 존재하고 있을때, 0이면 swap device에 있을 때

* Dirty Bit

> Belay's anomaly : FIFO의 문제점을 명시. 메모리를 늘렸음에도 불구하고 페이지폴트가 더 많이 발생하는 현상

* Stack Algorithm : N개의 Frame으로 구성된 메모리에 로드된 Page들이 항상 N+1개의 Frame으로 구성된 메모리에 로드된 page들의 부분집합이 되는 알고리즘.

절대 Belay's anomaly를 나타나지 않음

ex. LRU ...

(이름이 stack algorithm인 이유는 항상 나가고들어오는 부분이 stack처럼 어느 부분에서만 일어나기 때문에 stack에 비유)

* Page Replacement를 수행할 때, 미래를 예측하여 수행하면 굉장히 효율적일 것이나, 현실적으로는 불가능.

하지만 프로그램은 Locality라는 속성을 가지므로 과거를 통해 미래를 어느정도 예측할 수 있음.

=> LRU algorithm

> LRU

1. reference bits algorithm(8bits)

: reference bits를 하나 두고 8개의 8bits 짜리 register를 붙인 후, 일정한 간격으로 reference bits을 shift right하여 가장 사용이 안된 것을 고름. 

=>  사용여부 체크(00000000이 0이므로 가장 작겠지)

액세스의 여부만으로는 정확한 우선순위를 정하기 어렵기 떄문에, OS는 시간을 일정 간격으로 시간을 나눈 후 해당 interval에서 사용이 되었는지의 여부를 체크

2. Clock Algorithm

: linear한 frame들을 clock처럼 wrap around 형태로 연결 시킨 후, 현재 가리키고있는 임의의 페이지를 가리키는 clock hand로 페이지를 교체할 시점엔 어느페이지를 선택할 지 결정해야 함

* Clock Algorithm에서 교체할 Page를 선택하는 방법 

: Clock Hand가 가리키는 page의 reference bit이 1인경우, 0으로 바꾸고 Clock Hand가 다음 page를 가리키도록 함(최근에 사용되었다는 의미이므로 skip). 이 과정을 반복하다가 reference bit이 0인 page를 만나면 최근에 사용되지 않은 page이므로 해당 page를 교체체.

(UNIX OS 에서 많이 사용되는 알고리즘)

- 모든 reference bit이 1이면 모든 page가 reference 되고 있다는 의미이므로 main memory가 현재 overcommit되고 있다는 의미이며, 모든 페이지가 빈번하게 access되고 있으며 skip구간이 굉장히 많이 되므로 clock hand도 빠르게 회전하게 됨

=> clock algorithm은 LRU algorithm을 기반으로 업그레이드 한 것이지만, 메모리 Over Commit이 일어나게되면 FIFO algorithm으로 전환됨

3. Enhanced clock algorithm

- reference 안됐고 clean한 page

- reference 안됐고 dirty한 page

- reference 됐고 clean한 page

- reference 됐고 dirty한 page

* 기본적으로 clean한 페이지를 dirty한 페이지보다 우선적으로 처리한다. clean하면 swapping시 따로 지워주지 않아도 되므로 비교적 처리가 쉬움.

=> but, clean page라고해서 무조건 내보내는게 좋은 건 아니다. code page일 수 있다?

* Micro Architecture의 MMU기능의 단순화로 reference bit을 지원하지 않는다면?

> FIFO 사용

> Frame Buffering : 단순 FIFO를 기반으로 빈번하게 사용되는 frame을 다이나믹하게 관리하여 유용하게 사용하기 위해 free list를 사용

- used page frame list (linked list)

- free page frame list (linked list)

* Optimization : clean page와 dirty page가 섞여있는 free list에서, swap device와 DMA Controller가 IDLE 하다면, dirty page를 Swap-out하여 clean하게 해주기!

# Page Replacement Style

: allocation style

1. Global replacement

: 시스템 단위로 replacement

- 단점 : 메모리를 지나치게 사용하는 동작이 있다면 메모리를 효율적으로 사용하기 어렵다.

- 장점 : 메모리를 모두 고르게 분배하여 사용하면 메모리를 낭비없이 효율적으로 사용할 수 있다.

2. Per-process replacement

3. Per-job replacement(per-user replacement)

* 2,3번의 경우에는 Process나 Job단위로 나누어 replacement되므로 

간섭을 받지 않는다는 장점이 있지만, 어떤 부분은 메모리가 모자를수도, 어떤 부분은 메모리가 남아돌수도 있는 단점이 나타날 수 있음.

=> 할당되는 메모리를 dynamic하게 조절해 줄 수 있는 기능이 추가적으로 필요

: 단위시간동안 Page Fault횟수를 확인하여 메모리가 남는지 부족한지를 판단하여 이용한다.

# Demanding Paging

: 메모리 관리 매커니즘(MMU 매커니즘)을 사용해서 여러 프로세스가 시스템 메모리를 효율적으로 공유할 수 있도록 하는 기술

: 어떤 프로세스가 수행될 때, 집중되는 page들을 필요할 때 읽어들이기.

: 페이지가 요구될 때, 메모리에 불러오는 정책

* Principle of Locality(Locality of Reference)

: 프로그램이 가장 최근에 접근했던 데이터를 다시 접근하거나(Temporal Locality), 

최근에 참조했던 데이터 근처의 주소를 참조하는 경향이 있음(Spatial Locality)

* 90/10 Rule

: 불과 10%의 코드가 프로그램 총 수행시간의 90%를 차지함. (loop)

* Swap Device

: Physical Memory에 저장되지 못한 Page들을 저장하는 디스크의 공간

: 저장 단위인 file은 I/O시에 OS의 여러 기능이 동작해야하므로 굉장히 느리기 떄문에 File과 별도로 direct access가 가능한 low disk block.

: swap device가 가득찬 경우는 file을 swap 영역으로 사용할 수 있음

> Demand Paging의 Policy

: Physical Memory와 Swap Device 사이의 데이터 전송을 최소한으로 발생하도록 함

* Memory Access Latency

레지스터(1 사이클) < L1 캐시(수 사이클) < L2 캐시(수십 사이클) < Main Memory(수백 사이클) < Disk (수백만 사이클)

* Thrashing 

: 프로세스들이 사용하는 페이지들의 크기보다 사용이 가능한 물리 메모리의 크기가 작을 때, 사용하려고 swap-in하는 페이지들에 의해 앞으로 사용할 페이지가 swap-out되면서 반복적으로 Page Fault가 발생하는 현상

> page table entry가 virtual memory management를 지원하려면,

target 주소가 ram이 아닐때를 구분할 수 있는 flag가 필요. 

* Resident Bit 

: 대상 페이지가 물리 메모리에 있는지, 스왑디바이스에 있는지 구별해주는 플래그

> Virtual Memory 사용의 key!

: 값싼 Disk를 사용하여 비싼 메모리를 사용하는 것처럼 구현하여 사용하자.

> Demanding Paging 구현의 기술적 이슈

- Page Fault :  virtual address가 가리키는 page가 physical memory에 없어서 프로세그가 더 이상 진행할 수 없는 상태를 OS에게 알려주는 일종의 소프트웨어 인터럽트

* page fault handler : 인터럽트 서비스 루틴을 수행

<Page Fault Handling>

1. DMA Controller에게 해당 페이지의 주소를 전달

2. DMA Controller는 해당 페이지를 physical memory로 로드

3. DMA Controller의 작업이 끝나면 인터럽트 발생

4. OS는 page fault를 일으킨 프로세스의 수행을 재개

> Page Fault Handling이 다른 인터럽트 처리보다 어려운 경우

: 인터럽트는 수행중인 instruction에 의해 변화된 상태를 되돌렸다가 page fault 처리가 끝난 후 해당 instruction을 재개해야하기 때문

=> page fault 모든 수행에 일어날 수 있으므로 instruction 재개가 굉장히 어렵기 때문에 에외적으로 처리하게 됨 (virtual memory를 지원하기가 어려움)

* MOVE (SP)+, -(R2)

: SP가 가리키는 메모리 location의 값을 R2의 값을 하나 감소시킨후 copy하라.

* VAX의 경우는 애초부터 virtual memory를 지원하도록 설계하였는데 

CISC Instructiond은 restart가 어렵기 때문에 마이크로 코드로 다시 프로그램되어있으므로 마이크로 코드로 리버스 시킴(페이지폴트 발생시 인스트럭션 수행중의 변화시켰던 모든 레지스터 state를 복구하고 핸들링이 끝나면 다시 이전의 instruction이 restart되도록)

* 요즘은 RISC 방식으로 구현되며, RISC는 restartable하게 구현

> 정리

과거에는 프로그램이 수행될 떄, 프로그램과 관련한 모든 메모리가 전부 물리메모리에 있어야 하므로 비싼 메모리의 가격이 문제가 되었음.

비싼 메모리를 줄이고 싼 디스크를 swap device로 사용하는 virtual memory management라는 기술이 발전하였음.

Virual Memory Management는 virtual memory address를 physical memory address로 전환해주는 하드웨어인 MMU의 지원이 꼭 필요함

> HW 트렌드가 변화되면서 여러가지 대응해야 할 이슈

swap device를 쓸 수 없는 과거상황으로 돌아가는 경우

"스마트폰" 디스크가 없고  solid state disk(flash memory)를 secondary disk로 사용

flash memory는 ROM으로 Erase횟수가 제한이 있으므로 swap device로 사용할 경우 수명이 급격히 줄어들게 됨

> Demanding Paging은 페이지가 요구될 때 메모리에서 불러오므로 페이지가 요구되는 시점에 ram regident하지 않고 그 때 요청을 하게되면 page fault가 발생할 수 있으며 속도가 매우 느려질 수 있음 => 미리 예측하는 policy를 갖도록 하자!

* 이상적인 Page Selection Policies

:  앞으로 사용될 페이지를 미리 메인메모리로 가져와서 페이지 폴트가 발생하지 않도록 하는 방법

1. Demand paging : 

- pure demanding paging

- 프로세스가 시작할 때 메모리에 0개의 페이지로 시작하며, 엔트리 포인트에 들어갈 때 처음 인스트럭션부터 page fault가 발생하여 초반부에 엄청난 page fault가 일어나게 됨. 이후 충분한 페이지를 잡으면 원활하게 프로세스가 동작하게 됨.

- 가장 단순하지만, 프로세스가 생성되서 시작을 할 때 너무 오랜 시간이 소요됨.

2. Prepaging : 앞으로 사용될 페이지를 예측해서 미리 Main Memory로 로드하는 방법

- 한페이가 요청되면 인접한 페이지까지 로드

   => 효과적인 prepaging 방안 : Spatial Locality에 기반하여 page fault가 발생한 근처에 있는 페이지들을 Main Memory에 로드

3. Request Paging : 논리적으로 연관성이 있는 페이지들을 미리 Main Memory에 로드

- 과거에 사용했던 기법

- 예. Overay

=> 사용자가 결정해서 사용해야하는 불편함이 있음.

=> Working Set 대두!

> 여러가지 관점

1. 어떤 페이지를 언제 물리메모리로 불러올 것인지. Page selection policy

2. 스와핑 대상을 고르기. Page replacement policy

3. replacement를 수행할 때, 전체 프로세스들 중에서 고를지, 특정 그룹의 프로세스들에서 고를지. Page replacement style

4. page들을 어떤프로세스에게 page frame을 할당할때. Page placement style