[ 운영체제 ] 26. Virtual memory - Frame allocation / Thrashing

https://twinw.tistory.com/107

Allocation of Frames

: 정해진 양의 Free mem을 어떻게 여러 프로세스에 나눠줘야 할까?

 

 

● Allocation 방법

: 하나의 process에서 frame이 줄어든다면

  → Page fault는 늘어나고 , Performance는 줄어든다. 

 

 

1. Equal allocation

 

: m개의 frame ,  n개의 process에게 준다면

 

각 프로세스 당 [ m/n 개 ] 의 프레임을 받는다.

 

---

 

2. Proportional

m 개의 frame에 대해

 

ai = 프로세스 pi 에게 할당된 프레임의 수

si = pi의 크기

S = 전체 프로세스의 크기

 

ai = si / S * m

 

하나의 프로세스에 할당된 프레임의 수

= ( 해당 프로세스의 크기 / 전체 ) * 전체 프레임 갯수

 

 

 

● Replacement 의 대상

 

1. Local replacement

:  현재 프로세스에 있는 Frame만 Replacement의 대상이다.

 

 

2. Global replacement

  : 다른 프로세스에 있는 Frame도 Replacement의 대상이다.

 

  현재 프로세스에 있는 page를 다른 process가 사용할 수 없다. 

 

 

근데 주로 Global Replacement를 사용한다.

 

문제 내면 이런 거 나올 듯
[ @ Replacement 알고리즘을 사용한다. Global일 때와 Local일 때 VICTIM은? ]

 

 

 

Reclaiming Pages

Global page replacement 방식 중 하나이다.

 

1. 비어있는 프레임의 수가 0보다 작아지기 전에 Replacement 페이지를 선택 

2. 빈 프레임 목록이 어느 정도 이하로 떨어지면 page Replacement가 Trigger

 

 

 

---

NUMA ( non- uniform Memory Access )

: 메모리 접근 시간이 현저히 차이가 나는 시스템

 

이래야 효율이 좋다고 한다. 

 

 

 

---

 

Thrashing

● 배경 : Process가 page를 충분히 가지고 있지 않으면, Page-fault가 엄청 많이 일어날 것이다.

 

● 의미 : Process가 Swapping page를 하는데 너무 바쁜 것

 

● 문제점 :

1 . CPU 활용도 떨어짐

2.  다른 Process가 그 시간에 활용도를 높이기 위해 System에 들어오려고 할 수도 있다.

 

 

 

 

 

따라서, Process 는 frame이 얼마나 필요한지 알려서 Thrashing을 막을 수 있다.

 

=> 알아내는 법 : Locality model

 

- Locality : 함께 사용되는 page들의 set

(위 그림)

time a일 때 30- 34, 18-25 페이지가 쓰이고

time b일 때는 31-34 , 24-30 , 18-21 페이지가 쓰인다.

 

 

● Working-Set Model

: 특정 시간동안 Reference된 page들의 Set

 

 

특정 시간을 10으로 잡았을 때

10초동안 쓰인 page set을 Working set으로 만든다.

 

 총 요구량 > 사용 가능한 Frame면 , Thrashing 이 발생할 것이다.

 이유: frame은 작은데 요구량이 많아 왔다갔다 엄청 해야하니까

 

 

Trashing Control 대신 할 수 있는 방법

= Page fault Frequency

page fault frequency 가 너무 높으면 frame을 더 할당하고, 그렇지 않으면 지운다.

 

 

---

Allocating Kernel Memory

https://bubble-dev.tistory.com/entry/OS-%EC%BB%A4%EB%84%90-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%95%A0%EB%8B%B9-%EB%B0%A9%EC%8B%9DBuddy-Slab

 

Kernel memory에서의 Allocation은 더 특별한 조정이 필요하다.

 

Kernel에서는 다양한 사이즈의 data 구조로 이루어진 memory에 요구

 > HW 기기들과 Physical mem들이 직접 교류하여 Kernel이 memory에 있는 정보를 가져다준다.

 

 

● 방법으론 2가지가 있다

 

- Buddy System

: Memory를 고정된 Segment로 나누어서 할당한다.

한 segment는 연속된 page이다.

 

요청된 메모리 크기를 수용할 수 있는 최소 크기로 메모리를 쪼개어 할당하며

그러한 메모리 조각을 buddy라고한다. 

 

필요한 만큼만 데이터를 가져갈 수 있다.

ex) 256KB에 10KB 할 일은 없음

 

 

● 장점 : 다른 Buddy들과 합치기 좋다.

 

 

● 단점 : Interneal fragmentation이 일어날 수 있다.

ex) 33바이트일 땐, 64를 쓴다. 대신 31바이트가 비어있는 상태임

 

 

 

 

- Slab allocation

배경 : [ Allcocation 크기 ] 와 [ 요청 크기 ] 의 차이가 있을 때

 

● Cache →  Kernel data

 

● Slab = 1개 이상의 연속된 물리page들의 집합

● Cache = 1개 이상 Slabs의 집합

 

Cache는 Kernel 데이터를 담는다.

 

- Cache가 만들어지면 object 를 free 상태로

- 저장이 되면 , object를 used상태로

 

만약 Slab이 사용된 걸로 꽉 찬다면, 그 다음 (할당되어있는) 비어있는 slab을 사용한다.

 

 

https://hyeo-noo.tistory.com/380

 

● 장점

: Fragmentation 때문에 메모리가 낭비되는 일이 없다.

  + Memory 요청이 빨리 처리된다.

 

---

Prepaging

: page fault를 줄이기 위해 필요할 것 같은 page들을 다 가져오는 기법이다.

 

● 고려할 점

  prepaging Cost   vs  Page faults 에 대응하는 Cost

 

 

요새는 페이지 사이즈가 점점 커지고 있다고 한다.

 

---

TLB Reach

TLB Reach : TLB로부터 접근할 수 있는 메모리 공간의 크기

(Transfer Lookaside Buffer)

 

TLB에 대한 Hit 비율을 높이기 위해서는 TLB가 커져야한다.

따라서 이는 associative memory로 구성되는데, 이는 비쌀 뿐만 아니라 전력을 많이 잡아먹는다.

 

 

 

따라서, TLB Reach 크기 = <TLB의 Entry 갯수> * <page 갯수> 로 판단한다.

근데 주로 page size를 키워서 한다.

 

 

 

---

Inverted  Page Tables

 

: Memory translate 가 필요한 Physical memory 의 크기를 줄여준다.

 

Process에 대한 정보만 알면 되기에 Logical address space 에 대한 정보는 갖고있지 않다.

하지만, Demand paging은 page fault를 처리하기 위해서는 Logical address가 필요함.

 

해결법

--> 프로세스마다 외부 페이지 테이블을 만든다.

 

 

 

---

 

메모리에 대한 인덱스도 MSD로 생각하는 것이 좋다.

가장 왼쪽 인덱스를 가져오고 그 뒤에 작은 인덱스들을 가져와야 Page fault가 없다.

 

ex) 1개 단위로 가져오기  vs 10개 단위로 가져오기

 

 

---

I/O interlock

 

lock을 건 애들은 page replacement algorithm에서 victim으로 안 꼽힘

깍두기 느낌이라고 생각하면 좋을 듯 하다

---

Linux( 그냥 참고용 )

 

● Demand paging

 : 발생 시에, Free frames list에 있는 page들을 할당한다.

  대체로 LRU Clock 알고리즘을 사용하여 Global Page replacement를 한다.

 

 

● Accessed bit

모든 페이지는 referenced될 때마다 체크되는 accessed bit가 있다.

 

 

● 페이지 관리법

- Active list : 사용 중으로 취급되는 페이지들을 담아둔다.

 

- Inactive list : 현재 Referenced 되지 않고, Reclaimed 될 수 있는 페이지들을 담아둔다.

                      + 만약 여기에 있는 page가 reference 되면, 그 페이지는 active list로 간다.

 

 

● Kswapd

: Kernel swap daemon process

 

그냥 Kernel을 메모리로 가져온다.

 

만약 Free mem이 모자라면, inactive list에 있는 page를 스캔하고

                                              free list를 reclaiming한다.

 

 

 

(출처)

 

한동대학교 고윤민교수님 - 운영체제