Ch.9-1) Memory Management Strategies

#Overview

https://ko.wikipedia.org/wiki/%EA%B0%80%EC%83%81_%EB%A9%94%EB%AA%A8%EB%A6%AC

가상 메모리 - 위키백과, 우리 모두의 백과사전

http://egloos.zum.com/sweeper/v/2988689

 

: 프로그램에서 메모리에 접근하기 위해서는 반드시 Memory address가 존재해야 한다.

: Address에는 총 두가지 종류가 있는데, 바로 Virtual Address Space와 Physical Address Space 두가지가 있다.

 

- Virtual Address

: Virtual memory란 RAM을 관리하는 방법의 하나로, 각 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식을 말한다. Physical memory보다 실제 Memory 공간을 더 써서 Physical memory의 한계를 극복하기 위해서라도 각 프로세스의 Virtual memory의 합은 Physical memory의 합보다 클수 밖에 없다.

=> 실제 메모리에 탑재되기 전에 CPU상에서 갖고 있는 가상 주소를 말한다.

 

- Physical Address

: 실제로 해당 프로세스가 실행될때 접근해야 하는 물리적 주소이다. 따라서 각 프로세스가 Disk에 있다가 직접 Memory에 탑재되었을 때에는 프로세스에 접근하기 위해서 Virtual Address를 Physical Address로 반드시 Translation해주어야 한다.

 

 

 

: 따라서 CPU가 보고있는 해당 프로세스 주소인 Virtual address를 갖고 있지만, 직접 메모리에 해당 프로세스를 로딩하기 위해서는 해당 프로세스의 Virtual address를 Physical Memory로 Translation을 해줘야 한다.

 

 

 

 

=> 만약 A page가 메모리에 없다고 가정해보자. 해당 페이지를 수행하기 위해서는 반드시 메모리에 로딩되어야 한다.

: Disk 접근 시간이 메모리 접근 시간보다 오래 걸리기 때문에 가능한한 메모리에서 해당 페이지를 찾는 성공률인 Hit ratio를 높여야 한다. => 자주 사용하는 page는 되도록 memory에 로딩해 놓는것이 좋다.

 

=> 따라서 마침 메모리 공간이 협소할 때, 메모리에서 필요없는 데이터는 쫓아내야 한다. 

이를 Page replacement라고 한다. Disk에 있는 A는 메모리에 로딩하고, 특정 페이지나 프로세스를 memory에서 쫓아내야 한다. : 이는 매우 중요한 policy이다.

 

 

 

 

=> 따라서, 9 & 10장을 통틀어서

 9장에서는 Address translation, Memory Protection에 대해 학습하고,

 10장에서는 Page replacement와 Kernel에 memory를 allocate하는 방법을 배우게 된다.

 

 

---

 

# Background

-1) Memory Protection

: 9장에서의 중요한 개념은 Address Translation과 Memory Protection이다.

: 메모리 관리에서는 하드웨어가 쓰일 수가 있다.

=> Address translation을 매번 메모리 접근 시에 수행되어야 하기 때문에 빠르지 않으면 점점 메모리 수행 시간이 느러느려진다. : 따라서 하드웨어의 목적은 이 둘을 빠르게 하기 위함이다.

 

- Address Translation과 Memory protection을 효과적으로 빠르게 수행하기 위해서 제공하는 하드웨어에는

 1) Register 와 2) TLB가 있다. 이를 Memory Management Unit이라고 한다.

 

 

 

 

: 운영체제는 각 프로세스들이 메모리에 올라왔을 때 다른 프로세스의 메모리 공간에 접근하는 것을 막아야 한다.

=> 이때, Memory protection을 지원하기 위한 하드웨어가 두가지 있는데, 바로 Base register와 Limit register이다.

: 각 프로세스는 contiguous allocation, 즉 연속적으로 저장되게 되는데, 이 특징 때문에 두 레지스터를 이용하여

 Memory protection을 할수 있게 된다.

 

= 우선, Base Register는 해당 프로세스가 저장된 시작 값이고, Limit Register는 해당 프로세스에게 할당된 메모리의 크기의 값이다.

 

따라서, 그림에서의 예시를 보면, 메모리 접근시 현재 base register값인 30004보다 작다면, A process를 의미한다.

그리고 만약 Base register+Limit register의 값보다 큰 값에 접근했다면, C Process에 접근했음을 의미하는 것이다.

=> 어떤 경우에든, 현재 가리키고 있는 공간인 B process가 아닌 아예 다른 공간에 접근했다는 것을 알 수 있다.

: 따라서 Memory Protection policy를 위반하게 된다.

 

: 이를 메모리에 저장하면 상당히 오래 걸리므로, 레지스터에 저장해놓는다면 매우 빠르게 현재 주소가 B 영역인지 

아닌지 확인이 가능하다.

 

 

 

 

 

=> 우선 CPU 스케줄러가 실행할 프로세스를 바꿀때,

가장 먼저 해야할 일은 Base/Limit Register를 업데이트하는 일이다.

 

: Base register와 Limit Register를 사용하는 기법은 Contiguous allocation에만 해당하는 기법이다.

 

1) 만약 address값이 Base register의 값보다 크거나 같다면 Yes, 아니라면 Memory protection을 위반했으므로 No 로 빠져서 System call을 실행한다.

2) 두번째로 만약 Address값이 Base Register+ Limit Register를 더한 값보다 작거나 같다면, 최종적으로 Memory Protection을 지켰으므로, 메모리에 올바르게 접근한 것이다.

: 역시 두번째 사항에 해당하지 않는다면, System call을 실행하게 된다.

 

 

# Memory Management Unit ( MMU)

: 이는 메모리 관리를 효과적으로 하기 위해 지원되는 하드웨어이다. Base, Limit register역시 MMU의 일종이다.

- 주로 Virtual Address를 Physical Address로 바꿔주는 역할을 한다.

 

 

 

-  user process에 의해 생성되는 모든  프로세스의 virtual address값에 Relocation register값이 더해진 후

  프로세스가 메모리로 보내진다.

: User program은 주로 Logical address (= virtual address)를 다루기 때문에, 절대 Real Physical address는 신경 쓰지 않는다. 따라서 Relocation register값을 더해줌으로써 실제 Physical address값으로 translation이 가능하게 된다.

 

Logical address값에 메모리에서 프로세스의 시작 주소인 Relocation register값을 더하면 physical address의 값이 된다.

 

=> MMU의 핵심은 MMU가 없다면 시작주소를 메모리에 저장하게 되므로, 레지스터에 접근하는 시간보다 접근 시간이 훨씬 늘어난다. 따라서 MMU를 사용하면 불필요한 메모리 접근 시간을 줄일 수 있게 되는 것이다.

 

---

 

# Address Binding

: Address binding이란 프로세스가 접근해야 하는 변수나 함수에 대한 주소가 정해짐을 말한다.

=>프로그램을 실행하기 위해선 Compile &linking을 통해서 실행파일이 만들게 된다.

이 때, secondary storage인 disk나 SSD에 binary 포맷으로 저장된다. 이 프로그램을 실행하려면 메모리로 로딩이 되어야 하는데, 이때, 어떤 주소로 프로세스를 올릴 것인지 결정해야 한다.

 

-> 이 때 CPU가 명령문을 실행함으로써 발생하는 메모리 주소를 Logical Address 혹은 Virtual address 라고 한다.

그리고 실제로 접근해야 하는 메모리 주소를 Physical address라고 하는데, Logical address와 physical address 는 서로 다를 수 있다.

 

 

 

- Symbolic address

: 프로그램 소스 코드 상에서 표현하는 변수의 address들을 말하며, 주로 symbol 형태로 표현된다.

ex) int a, char b....

 

- Relocatable address

: 이때, 컴파일 되게 되면 주소가 바뀌게 된다. relocatable address란 프로그램의 시작 주소로부터 얼마나 떨어진 지점에서 실행되는지에 대한 offset을 의미한다. 이 offset 값에 따라 절대 주소가 달라진다.

 

-Absolute address

: 그리고 마지막으로 linker나 loader가 위의 relocatable address를 absolute 주소로 바꿔준다.

실제 physical address로, 메모리로 프로세스를 올릴 때 수치로 표현되는 절대 주소를 결정하게 되는 것이다.

#### 궁극적으로 숫자 주소로 표현되는 Absolute address를 찾는게 목적인 것이다. ####

 

 

 

 

 

 

 

=> 즉, Absolute address를 찾아야지만 메모리에 올릴 수도 있는 것이다.

:이 절대 주소가 결정되는 시점에 따라 세가지 바인딩 모델이 존재한다.

 

1. Compile time binding

: 컴파일 하는 시간에 absolute address가 결정된다. 만약 프로그램의 실제 시작 주소가 바뀌면 매번 다시 컴파일을 해야 한다. 항상 그 주소에 프로그램이 위치한다는 보장이 없다.

CPU에서 명령어를 실행할 때 이미 주소가 결정되어있어야 하므로 logical address와 physical address가 같다.

<virtual memory를 따로 사용하지 않는 다는 의미와 일맥상통하다>

 

2. Load time binding

: 프로그램이 컴파일 된 후에 메모리에 올라갈 때 절대 주소가 결정됨을 의미한다. 

: 컴파일 된 프로그램 내의 각 변수나 명령어의 주소는 특정 값을 기준으로 정해진다 (relocation address)

: 그리고 메모리에 올라가 CPU에서 각 프로그램이 올라간 시작 주소인 Base register 값에

Relocatable address를 더하여 주소를 만들어 낸다.

 

=> 역시 이렇게 CPU 내에서 계산되고 발생한 Logical 주소는 physical address와 같게 된다.

: Load time binding으로 주소가 결정된 프로그램은 한번 메모리에 올라가면 종료될 때 까지

그 위치에 존재하게 된다. 주로 Loader에서 발생한다.

 

: 현재 OS의 메모리 관리는 virtual memory를 사용하기 때문에 Disk로 쫓겨나서 다시 메모리로 로딩될 때

아예 다른 주소에 로딩 될 수도 있다.

: 따라서 한번 정해진 주소를 계속 사용하게 되는 Compile time, Load time binding은 현대에서 사용하지 않는다.

 

 

3. Execution time (run time binding)

: 실행 시점 주소 바인딩은 메모리에 올라간 후 최종적으로 명령어가 실행 될 때까지 address binding이 미뤄져서 

마지막 순간에 절대 주소가 계산되는 것을 의미한다.

 

: 주로 프로그램의 메모리 위치가 매번 바뀌기 때문에 이러한 방법을 사용한다.

=> 따라서, CPU에서 나온 virtual address는 최종 실행 시점에서 MMU를 거쳐서 실제 주소로 translate되어서 접근하게 되고, 또는 Address mapping table을 이용해서 translation 할 수도 있다.

 

: CPU에서 나온 주소는 virtual(logical address)이고, MMU를 통해 바뀐 주소가 메모리의 실제 주소인 Physical binding이므로, 실행 시점 주소 바인딩에서는 두 주소가 다르다.

 

 

# Logical address란?

: CPU에 의해서 생성되는 주소로, virtual address와 같은 말이다.

 

# Physical address란?

: memory unit에서 보이는 실제 주소이다.  

 

Logical address==physical address

: compile time & load time binding에서는 같다. (메모리에 올라갈 때 이미 주소가 결정되어있음)

 

 

 

 

 

Logical address != Physical address

=>매번 수행 될 때마다 주소가 바뀌는게 가능한 Execution time binding에서만 가능하다. 

: MMU 또는 Memory mapping table에 의해서 logical address가 physical address로 translate되어 

직접 실행될 때 주소가 결정된다. : 즉, 매번 execute될 때마다 주소가 바뀌는 것을 의미한다.

 

 

---

 

 

 

=> 리눅스에서의 process address space를 한번 살펴보도록 하자.

 

: 우선 local 변수는 stack에 저장되고, 동적할당 메모리인 dynamic memory는 heap에 저장된다.

또, 전역변수인 glob 변수는 data영역에 저장되며, 코드 부분은 text영역에 저장된다.

: 이런 변수들이 저장되는 user space, 즉 프로세스 space는 virtual memory를 사용하므로 physical memory의 용량은 작더라도 큰 메모리 공간을 가질 수 있다.

=> Virtual address는 프로그램이 보는 주소를 의미하며, 실제로 실행될 때 결정되는 physical memory와는 다르다.

 : 따라서, MMU든 memory mapping table을 통해서든 반드시 address translation이 필요하다.

 

 

 

 

=> 실제로 process address space를 출력해보았을때, 매우 큰 주소 공간을 갖는 것을 볼 수 있다.

: 이는 프로세스가 보는 주소 공간이며,  physical memory가 절대 아니기 때문에

=> 반드시 address translation이 필요한 부분이다.

 

---

프로그램은 메모리에 올리는 Load과정과, 라이브러리 파일과 연결해주는 Linking과정을 통해 최종적으로 메모리에 올라가게 된다. 메모리에 올라가서도 지속적으로 메모리 공간을 차지하지 않고, 운영체제의 필요에 의해 지속적으로 Swap-in 되거나 Swap-out 되고는 한다.

# Dynamic Loading

: Dynamic Loading은 한정적인 메모리 공간 때문에 고안된 방법이다.

: 프로그램 함수들 중에 호출이 안되는 routine이 있으면 아예 메모리로 로딩하지 않는 기법을 말한다.

=> 메모리 공간이 한정되어있으므로, 사용되지 않는 모듈까지 메모리에 올리기에는 공간이 부족하다. 따라서 때에 따라 필요한 routine만 그때그때 올려주는 방법이다.

 

-> 즉, Loading을 가능하면 뒤로 미루는 것이다. Dynamic loading은 OS로부터 별다른 Support가 필요하지 않다.

: Library등을 필요로 하지 않는다.

 

 

 

https://jhnyang.tistory.com/42

[운영체제]Static Linking vs Dynamic Linking(shared Library) 정적링킹 vs 동적링킹

 

#Dynamic Linking

: 역시 Dynamic loading과 비슷하게 Loading을 최대한 execute되기 전까지 나중으로 미루는 것이다.

=> 기존 Linking과정에서는 프로그램이 compile될 때  Standard.c와 같은 library를 프로그램과 합쳐서 Linking을 해서 매번 프로세스 메모리 공간에 해당 라이브러리를 프로세스와 함께 올린다.  이는 매번 프로그램이 실행될 때마다 같은 라이브러리 파일이 메모리 공간에 여러번 올라가게 되므로 메모리 공간이 낭비되는 현상이 발생한다.

 

: 그리하여 나온 방법이 실행 전까지는 Linking을 하지 않고, 실행이 될 때 특정 라이브러리 파일이 최로로 한번 메모리에 올라가고, 이 라이브러리를 사용하는 프로세스들은 Stub 포인트를 이용해 라이브러리의 routine을 참조하게 된다. 그리하여 같은 라이브러리를 메모리에 여러번 올리는 것을 방지하여 메모리 낭비를 막는다.

 

=>이는 OS의 도움이 반드시 필요하다.

: OS가 반드시 각 라이브러리의 루틴이 어디에 존재하는지 알아야 하며,

해당 루틴에 접근하기 위해 다양한 프로세스의 주소 공간에 접근할 수 있는 권한을 주어야 한다.

 

- Stub이란?

: Stub은 나중에 실제로 라이브러리를 dynamic하게 링킹할 때 어떻게 해야 하는지에 대한 정보를 담고 있는 코드 조각으로, 컴파일하고 링킹할 때 바이너리 파일이 산출되는데, 이 바이너리 file을 library에 어떻게 링킹해야 하는지에 대한 정보를 담고 있다. 그리고 해당 라이브러리를 호출할 때, stub은 해당 라이브러리의 주소로 대체되고, 그 주소에 있는 라이브러리의 routine을 수행하게 된다.

: 만약 프로그램이 standard.c library에 링킹해야 한다면, 해당 라이브러리를 통째로 loading하는 대신에 stub을 해당 루틴의 주소값으로 대체해서 그 주소에 있는 routine을 실행하게 된다.

: Linking을 execute뒤로 미루면 실행 시간이 줄어들며, shared library에 매우 효과적이다.

 

ex) 매번 게임을 업데이트 할 때 새로 다운 받지 않고, 필요한 부분만 업데이트 해서 사용하는 것도 Dynamic Linking의 예시이다.

 

 

 

 

 

 

- 위 예시에서 확인할 수 있듯, Static Library에서는 프로그램 실행 시에 각 Library를 무조건 포함시키게 된다.

: 따라서 프로그램마다 Library를 카피해야 한다. 이는 메모리를 훨씬 많이 낭비할수 밖에 없는 방법이다.

: 만약 프로그래머들이 가장 최신 버전의 Library를 사용하고 싶다면, 항상 relink해야 한다.

: 라이브러리가 모든 프로크램에 링킹된다면, 메모리 낭비가 심각해질 수 밖에 없다. (cout/cin은 거의 모든 코드에 있음)

 

-하지만 Shared Library를 통해 라이브러리를 공유하게 된다면, Library를 한곳에 저장해두고, 해당 Library의 루틴이 실행 될 때만 stub 포인트를 이용해 해당 stub을 Library 주소로 대체하여 라이브러리의 루틴을 실행하게 된다.

: 이는 메모리 이용 측면에서 효과적이며, Library를 자주 업데이트해야 할 때도 효과적이다.

=> 새로운 라이브러리 업데이트될때마다 하나의 라이브러리 공간만 업데이트 하면 되기 때문이다.

 

$$ 정리하자면, Shared library는 runtime에 실행되는 object module로, stub에 arbitrary memory address로 로딩되어

프로그램과 library를 링킹할 수 있게 하는 라이브러리라고 할수 있다. $$$

 

 

 

=

 

=> 한 프로그램의 최종 실행 파일을 만들기 위해서 각 파일들을 컴파일 하고, 생성된 object file을 linking하게 된다. 

이 결과를 P라고 하면 여기서의 Stub은 추후에 라이브러리를 어떻게 로드하고 Linking하는지에 대한 정보를 담고 있다.

그 후에  Shared library을 의미하는 Dynamic Linker를 통해 P*에서는 Stub을 실제 라이브러리의 주소로 대체하게 된다.

 

 

#Summary

 

1. MMU (Register(relocated register), TLB)

=> Logical address를 실제 physical address로 바꿔준다. 이때 TLB라는 캐시가 가상 메모리를 물리 메모리로 바꾸는 속도를 높여주는 버퍼이다.

 

2. Address Binding

: Compile time binding, load time binding: Physical address와 virtual address가 같다. 요즘은 잘 사용하지 않음.

: 주로 Execute time binding을 사용한다. Logical address와 virutal address가 다르므로, 반드시 Memory translation table이나 MMU를 필요로 한다.

 

3. Dynamic Loading

: 로딩을 최대한 뒤로 미뤄서 execute time에 필요한 루틴만 메모리로 로딩하여 실행하게 된다.

 

4. Dynamic Linking

: Linking을 최대한 Execute 뒤로 미뤄서 실행 전까지는 Linking이 되지 않고, 처음 실행 될 때 최초로 라이브러리가 메모리에 로딩되고, 이 라이브러리를 사용하는 프로세스들은 stub을 참조해서 라이브러리에 접근하게 된다.

stub 포인트는 원래 어떻게 라이브러리에 접근하고 로딩하는지에 대한 정보가 담겨있고, Dynamic Linker를 통해서 

라이브러리의 주소로 대체되게 된다.