Memory Management Strategies

Memory Management Strategies

1. 목적

 1-1. Virtual memory management의 목적

 - 메모리의 구조에 대해서 잘 알지 못해도 사용자로 하여금 편하게 사용할 수 있도록 하기 위해서.(Abstraction for programming)

 - 한정된 메모리에 대해서 메모리가 부족해도 많이 남은 것처럼 잘 사용할 수 있게 하기 위함

 1-2. Process간 Protection

2. VM(Vitrual Memory)

 - 사용하는 메모리 주소를 2가지(physical, logical)로 나누어 관리하는 기법

 - 프로그램의 전체 주소를 물리적 주소에 두지 않아도 되는 방식.

 - 많은 프로그램은 코드와 데이터를 한번에 필요로 하지 않는다는 사실에서 기반.

3. Binding of Instructions and Data to Memory

 - Instruction 주소와 데이터를 메모리 주소에 할당에주는 타이밍(쉽게말해 변수가 저장될 메모리 주소를 언제 결정해주는지 시간)

 3-1) Compile time.

  - 컴파일 타임에 확정된 주소는 실제 실행 시간에도 실제 메모리 주소에 똑같은 주소에 올라가야 한다.

  - 거의 불가능한 방법이고, 메모리 시작 주소가 바뀔때마다 Recompile 해줘야 한다.

 3-2) Load time

  - 프로그램이 메모리에 올라갈때 할당해주는 방식.(컴파일 시, 0번지 부터 있다고 가정하고 compile)

  - Load 되는 타이밍에 컴파일 시 정해주었던 주소에 실제 메모리 시작주소만큼 더해준다.

  - 위 방법에 비해서 메모리의 어디에 올라가도 수행이 될수 있게되어 좋아졌지만,

  - 명령어가 무수히 많은데 그 값들을 다 Load time에 실제 메모리에 올라갈 주소로 바꿔주면 Overhead가 너무 크다.

 3-3) Execution time

  - 명령어가 실행될 떄 할당.

  - 최초 compile 시에는 0번지를 기준으로 메모리 연산.(이를 logical[virtual] memory라고 한다.)

  - 프로세스가 실행되고 메인 메모리에 올라갔을 때 까지 logical address가 유지되고,

  - 메인메모리에 올라가서도 아직 0번지를 base로 한 주소(local address)를 유지한다.

  - 해당 명령이 실행될 때, 주소를 구하는 연산을 통해서 실제 Physical address가 정해진다.

  - 이때, Logical address를 통해서 Physical address를 구하는 연산은 MMU라는 CPU 내의 메모리 연산을 위한 HW를 통해 수행된다.(Memory Management Unit)

4. Dynamic Loading

 - Loading : 메모리에 프로그램을 올리는 작업

 - 메모리가 부족했던 시절, 무조건 프로그램이 메모리에 올라가는 것이 아니라 실제로 사용되거나 호출될 때, 메모리에 올라간다.

5. Dynamic Linking

 - Exe 파일을 만들 때, 특정 object의 library를 포함하지 않고, 해당 Library 내의 명령을 실행할 떄, Dynamic하게 Link한다.?

 - DLL(Windows), Shared Library(Unix) 파일이 EXE 파일에 포함되지 않아, EXE파일의 크기가 줄어든다.

 - 만약 cout이라는 명령이 포함된 Library을 이용해 실행파일을 만들 떄, 메모리에 cout이 호출된만큼 올라가야 하는데 Dynamic linking을 사용하면 해당 명령이 호출될 때마다 cout이 올라가있는 메모리 한곳에 가서 Linking 해준다.

 - 메모리 효율은 올라가지만 파일상으로 합쳐져 있지 않기 때문에 성능상의 Overhead가 존재한다.

 - EXE파일에 포함되어 있지 않기 때문에, Update 시에도 EXE파일을 새로 만들지 않고 DLL팡리만 수정해주면 된다는 장점이 있다.

6. Memory Swapping

 - 메모리가 부족해도 다른 process를 실행시켜줄 수 있는 방법

 - HDD의 Process와 Main memory의 process를 swap

① swap out : 메모리의 일부 내용을 back

② swap in : 

backing store : HDD

7. Logical vs Physical Address space

 - Logical address와 Physical address는 Compile time과 Load-time address binding 방식에서는 같고, Execution-time address binding 방식에서만 다르다.

 7-1) Logical address

   - 프로그램 내에서 사용하는 주소

   - Compile 시에 0번지를 기준으로 생성(Virtual Address)

 7-2) Physical address

   - Main Memory에서 사용하는 주소

   - Execution time에 결정된다.

8. Contiguous Allocation

 - 연속적 할당 : Logical address에서 연속적이면 Physical Address에서도 연속적으로 주소 할당을 해주는 방식

 - 장점 : MMU 제작이 쉽다. (프로세스마다 base address만 관리하면 된다, Base address에 Physical address 시작주소만 더해주면 된다.)

 - 단점 : External Fragmentation이 많이 생긴다.(메모리 효율이 좋지 못하다.)

    - Hole : 메모리가 사용되고 내려갔을 떄 생기는 빈 공간.

    - Hole이 많아지면 메모리 낭비지요. 이 Hole이 있을 때, 빈 공간에 Process를 배치하고 남은 짜투리 공간이 External Fragmentation.

 

 * trap : CPU가 자신에게 Interrupt 걸어서 주최를 O/S에게 넘겨줌

9. Paging

 - Contiguous allocation 방식의 External Fragmentation 문제로 인해 해결책으로 나온 방식

 - Physical Address의 공간이 연속적이지 않다.

 - Logical Memory를 Pages라는 고정된 크기의 블럭으로 나눈다.

 - Physical Memory를 Frames라는 고정된 크기의 블럭으로 나눈다.

  * Frame과 Page의 크기는 2의 제곱수이다.(Page 크기는 Frame크기와 같다)

 - n개의 Page 크기의 프로그램이 실행되면, n개의 비어있는 Frame을 필요로하고, Load한다.

 - Logical address를 Physical Address로 변활할 Page table을 준비한다.

 - Process별 매핑테이블(Page Table)은 MMU에 존재한다.(Page table 크기가 너무커서 CPU에 못넣고, 메인메모리에 위치시킨다., 자주사용하는 주소만 CPU에 별도로 저장.)

 - Locality : 프로그램의 전체 크기의 20%가 수행시간의 80%를 차지한다는 개념으로 Cache 사용의 주된 목적이다.

• Temporal Locality : 100번지가 참조 되었으면 가까운 시일내에 또 참조될 가능성이 크다.

• Spatial Locality : 100번지가 참조 되었으면 96, 104 등의 주변 메모리가 참조될 가능성이 크다.

 - Page Table은 Logical Address의 시작 주소와 각 Page들의 Index를 가지고 있다.

 

- 단점 : External Fragmentation은 해결하였지만 Internal Fragmentation은 여전히 존재한다.

   - Internal Fragmentation : Disk에 파일을 저장할 때, 고정크기의 Sector에 고정크기보다 작은 크기만큼의 데이터를 저장하고 남는공간(Logical Memory를 자르고 마지막에 잘리는 부분은 Page/Frame 크기에 딱 맞지 않을 수 있다.)

10. Memory Protection

 - Frame 별로 Page table에 Valid-invalid bit로 1bit를 추가시켜 줌으로써 구현된다.

 - Valid는 해당 페이지가 유효함을, Invalid는 해당 페이지가 무효함을 알림.

 - 참조하고자 하는 영역이 '0'(Invalid) 상태라는 것은 HDD에 위치해 있다는 의미다.

 - Invalid -> 정말 참조하지 않고 HDD에 존재하기 때문에 OS에 의해서 Trap, OS가 처리

 - Valid -> CPU가 바로 참조

 - Page fault : Paging table에서 메모리를 참조했는데 HDD에 있는 것을 참조한 경우

 - Protection fault : 아에 참조할 수 없는 메모리를 참조한 경우.

11. Segmentation

 - paging과는 달리 고정된 크기말고, 의미있는 단위(segment)로 나누자.

 - Paging과 같이 Contents(Data segment, Code segment) 속성을 고려치 않고 무조건적으로 같은 크기로 자르게 되면 Data segment는 Write가능하고, Code Segment는 Write가 불가능한 문제 등을 초래할 수 있다. 한 블럭에 두 영역이 공존하게 되면 문제가 있다.

 - Logical address는 segment-number와 offset을 갖고 이를 이용해 Physical address생성.(Segment Table 이용)

 - Physical address로 전환 시, 각 Segment의 크기는 모두 달라서 Table을 이용한 Mapping이 아니라 base를 더해준다

 - Segment 단위로 contiguous allocation이 이루어 지는 것이다. (이러면 또 External Fragmentation이 발생한다. 따라서 하이브리드 방식을 사용한다.)

12. Segmentation with Paging

 - 의미있는 단위인 Segment로 자른다.

 - 고정적인 크기로 Segment를 다시 자른다.

13. Page table structure

 - Page table이 너무 커서, 이를 좀더 효율적으로 구성하기 위한 방법

 - Hierarchical Page Tables

 - Hash Page Table

 - Inverted Page Table : Frame별로 Page Table을 관리해준다.(Table이 Process 수만큼 있을 필요가 없기 때문에 테이블이 한개만 있으면 된다.)

 - Shared Page : 하나의 프로그램에서 파생된 여러개의 프로세스의 경우, Data segment는 다르지만 Code segment는 같으므로, 이를 메모리상에 하나만 올려 공유한다.

14. Virtual memory 

 - Physical memory에서 Logical Memory로 분리

 - Logical Memory 영역이 Physical Memory 영역보다 커질 수 있다.

 - Address space가 여러 Process에 공유될 수 있다.

 - 프로세스 생성에 더욱 효율적이다. 

 - 프로세스가 실행되는 시점에 메모리에 올린다는 개념을 기반으로 함. (사용되지 않을 때는 HDD에 있을 수 있다, 사용될 때만 메모리에 올린다., swapping)

 - Page Fault에 대한 처리

 - Page Fault를 허용함으로써 메인 메모리가 업청 큰 것 처럼 보일 수 있다.

 - What's happens if there is no free frame?

- Page replacement : find some page in memory, but not really in use, swap it out

- 메모리가 모두 사용되고 있다면 어떤걸 내려야 할까?

- 앞으로 가장 오래 있다가 쓰일놈을 내리는게 좋다(하지만 그걸 알아내긴 힘들다)

- Locality에 의해서 최근에 참조되었던 곳 가까이에 것이 참조될 것이다.

- 참조되지 않았던 애들은 앞으로도 참조되지 않을 것이다.

15. Page Replacement

 - Free frame이 있을 경우 해당 Frame 사용, Free Frame이 없을 경우, Page replacement 수행

 - 목표는 Page Fault를 줄이자

 15-1) FIFO

- 공정하지만 Page Fault를 줄이기 힘들다.

- Convoy effect(Belady's anormaly) 발생

- 메모리가 3에서 4로 커졌는데 page fault가 늘어남(상식적으로는 메모리가 늘면 Page fault가 줄어야함), FIFO가 부적합하다는 증거

15-2) LRU(Least Recently Used)

- 최근에 가장 덜 사용된 부분을 victim으로 선정

- 과거를 보고 가장 옛날에 사용했던 것을 버림

-

- But, 전에 언제 참조되었는지 도장을 찍어서(Page마다 찍어야함) 관리하기는 구현이 힘들다.(Time stamp)

- Double linked list로 Stack을 구현, Overhead가 크다.

- 결론은 Approximation : 대략구현한다. 너무 정확한 LRU는 Overhead가 크다.

- Reference bit : 1bit 버전의 Time stamp로 1이면 참조됐었다, 0이면 참조 안됐었다. 내릴때는 0인 애들중에 하나 내린다.

- Second chance : 기회를 한번 더 준다. 시계방향으로 주소따라 이동하다가 1을 만나면 0으로 바꾸고 기회를 한번 더 준다. 그렇게 계속 시계방향으로 돌다가 0을 만나면 victim으로 선정.

15-3) NRU(Not Recently Used, 펜티엄에서 사용되는 방식)

 - R(Reference) bit 와 M(Modify) bit, 2가지 비트를 이용.

 - M은 가끔, R은 자주라고 생각하면 된다.

 - Class 1이 희생될 가능성은 Class2가 희생될 확률보다 크다.

 - Victim 순서 : Class0 -> Class1->2->3

 - Page Replacement에서 사용하고 있는 방식

 - Cache 메모리에서 사용하고있다.( Cache 메모리 위에서 write 되었을 때, M에 1 쓴다.)

15-4) LFU(Least Frequently Used)

 - 가장 많이 사용되는 것을 내리자는 알고리즘

 - 말도 안되는 알고리즘, 잊어라.

16. Thrashing 

 - Page Fault가 너무 많이 일어나서 ( 수행되는 Process가 메모리에 비해서 너무 많아서 or Physical Memory가 부족해서) O/S가 계속 그것만 처리하는(Page Replacement, Disk I/O만 계속처리) 현상.

 - A process is busy swapping pages in and out

 - Process가 많아지고 Disk I/O 작업을 기다리느라 CPU가 할일이 없어져서 CPU 사용량이 줄어든다.

 - 메모리를 늘리던가 Process 수를 줄이던가 해야함.

17. Prepaging

 - 어떤 Page가 Fault 됐을 때, 그 주변 애들까지 HDD에서 Memory로 올려 놓는다.

 - Page fault가 줄어든다.(Spatial locality 기반)

 - HDD에서도 연속되게 저장되어있을 가능성이 크니까 쭈-욱 읽어오면 편하다.

 - SSD로 대체될 경우 필요 없어질 수 있다.