[OS] Memory Management - Fixed Partitions, Variable Partitions, Overlays, Swapping, Virtual Address

1. 메모리 관리

운영체제가 어떤 방식으로 피지컬한 메모리를 관리할까?

메모리 관리의 목적은 다음과 같다.

• 프로그래머에게 abstract view를 보여주는게 중요하다.
  • 프로그래머는 A.exe가 메모리의 어디에 위치하는지는 전혀 신경쓰지 않고 배열을 선언하는 등 편하게 사용한다. 그 이유는 운영체제가 피지컬한 메모리를 가상의 공간으로 잘 보여주기 때문이다.
• 메모리는 부족한 자원인데, 이를 잘 나눠줘야 한다.
  • 여러 프로세스들이 메모리를 두고 경쟁하는 과정에서, 성능은 최대화시키면서 오버헤드는 최대한 줄여 잘 나눠줘야 한다.
• 프로세스간 isolation을 제공해야 한다.
  • 프로세스마다 가상의 메모리를 각각 가지고 있고 서로의 메모리는 볼 수 없어야 한다.

왜 메모리 관리가 어려울까?

싱글 프로세스라면 OS 등의 메모리만 할당하고 나머지는 하나의 프로세스에게 다 주면 된다.

멀티 프로그래밍에서 문제가 생긴다.

• Need multiple processes in memory at once
  • 피지컬한 메모리를 어디부터 어디까지 어떤 프로세스에게 할당하는지가 문제가 된다.
  • CPU와 I/O가 섞여서 사용되면서 어려움이 생긴다.
  • 프로세스마다 요구하는 메모리도 다르다. a.exe는 100메가가 필요하지만 b.exe는 100기가를 요구할 수 있고,
    이 또한 동적으로 사이즈가 바뀐다.
  • 프로세스는 연속적인 메모리 공간을 원한다. 가상의 어드레스 스페이스에서 공간이 연속적인것처럼 말이다.
• 요구사항
  • Protection
    스택은 얼마나 쓸 수 있어야한다던지, 코드의 영역은 어디부터 어디까지인지 등 프로세스가 사용할 수 있는 address를 제한해야 한다.
  • Fast translation
    가상 주소를 물리 주소로 변환하는 일은 굉장히 많다. 그 과정이 빨라야 한다. 이를 memory lookup이라 한다.
  • Fast context switch
    컨텍스트 스위치가 일어나면서 발생하는 메모리 하드웨어 업데이트가 빨라야 한다.

어플리케이션이 사용하는 virtual address를 커널에 의한 physical address로 바뀌는 일이 많다.

---

2. Fixed Partitions

Fixed Partitions 방법은 어플리케이션이 가상 주소에 접근하면 OS는 CPU 내부에 있는 Base register를 더해서 피지컬한 address로 바꾸는 방식이다.

Base register에는 해당 프로세스가 사용하는 메모리의 시작 주소가 저장되어 있다. 당연하게도 a.exe와 b.exe가 사용하는 memory address는 다르고, base register을 통해 translation하게 된다.

 

정리하자면 Fixed Partitions는 피지컬한 메모리를 고정된 파티션으로 분할하는 방식이다.

• 각각의 파티션은 모두 같은 크기이고, 고정되어 있다.
• 파티션의 수는 멀티프로그래밍으로 실행시킬 수 있는 프로세스의 수가 된다.
• 하드웨어는 base 레지스터만 잘 관리하면 된다.
  • Physical address = virtual address + base register
  • OS가 다른 process로 context switch를 할 때 Base register load만 하면 된다.

Fixed Partitions의 장점

• 구현하기 쉽고, context switch가 빠르다.

Fixed Partitions의 문제점

• 내부 단편화(Internal fragmentation)에 의해서 메모리가 낭비된다.
  • 해당 프로세스가 사용하지 않는 파티션은, 다른 프로세스도 사용할 수 없어서 낭비가 발생하는 것이다.
• 파티션의 사이즈를 결정하는 방법이 문제가 될 수 있다. 한 사이즈는 적합하지 않을 가능성이 높다.
  • 더 작은 공간으로 많은 파티션을 할당하면 동시에 실행할 수 있는 프로세스가 늘어난다.
  • 반대로 파티션 사이즈가 커진다면 더 적은 양의 프로세스만 실행할 수 있지만 context switch가 덜 일어난다.

💡 아래 소개하는 각 방식의 특징, 문제점과 특히 fixed의 경우 어떻게 사이즈를 정해야하는지가 중요하다.

Fixed Partitions의 개선 방안

• 파티션의 크기가 같을 필요가 없다.
• 다른 사이즈의 파티션으로 쪼개서 할당하는 방법이 좋다. 메모리를 많이 사용하면 더 큰 사이즈의 파티션을 주는 것이다.
• 이 방식은 일단 프로세스가 메모리를 얼마나 쓸지 예측하기 힘들다. 예측이 가능하다고 가정하면, 내부 단편화가 적은 메모리를 찾아서 할당해야 한다. 전체 메모리를 스캔해야 한다는 것이다. 물론 무조건 스캔하는 것은 아니고 다른 방법도 존재한다.
  • First fit allocation : 비어있는 파티션 중 맞는 프로세스가 쓸 메모리보다 같거나 큰 크기의 가장 먼저 스캔되는 파티션에 할당한다. 스캔이 필요하다.
  • Best fit allocation : 비어있는 파티션에 맞는 가장 큰 job을 선택한다. 좀 더 많은 스캔이 필요하고, 오버헤드가 많이 든다.
• IBM OS/MFT : Tasks를 고정된 수로 멀티프로그래밍 하는 시스템이다.

---

3. Variable Partition

프로세스별로 필요한 만큼 파티션을 할당한다. 프로세스마다 파티션의 크기가 다르게 설정되므로 프로세스 a에서 접근하려는 address가 프로세스 a의 파티션 범위 내인지 판단하기 위해 limit register, base register를 사용해야 한다.

 

피지컬한 메모리를 variable-sized 파티션으로 분할한다.

• IBM OS/MVT가 여기에 속한다.
• base register와 limit register 하드웨어만 잘 관리하면 된다.
  • Physical address = virtual address + base register
  • limit register는 각 파티션의 크기를 저장하고 있다.
  • base register는 각 파티션의 시작 주소를 가리킨다.
  • base register는 다른 프로세스로 컨텍스트 스위치가 일어나면 OS에 의해 load된다.
  • 컨텍스트 스위치가 일어났을 때 register 값만 잘 세팅하면 되므로 저렴하다.
• limit register는 protection의 역할이다.
  • If(physical address > base + limit), 해당 프로세스의 바운더리를 넘어가는 것이므로 protection fault를 발생시키게 된다.
• fixed에 비해 어떤 프로세스가 쓰는 메모리를 알 수 있다면 더 합리적이다.
• 메모리를 어떻게 할당하는지에 대해 세 가지 방법이 있다. 기본적으로 프로세스가 얼마나 메모리를 사용할지 알아야 하고, 그만큼 들어갈 수 있는 공간을 찾아야 한다. 메모리를 스캔해야한다는 뜻이고, 그만큼 오버헤드가 발생한다.
  1. First fit : 가장 먼저 찾아진 곳에 할당한다.
  2. Best fit : 프로세스가 들어갈 수 있는 곳 중 가장 작은 곳에 할당한다.
  3. Worst fit : 가장 큰 곳에 할당한다.

Variable Partitions 장점

• 내부 단편화가 존재하지 않는다.
  • 프로세스에게 충분히 큰 공간을 할당하기에 내부 단편화로 인한 메모리는 낭비는 발생하지 않는다.

Variable Partitions 단점

• 외부 단편화(external fragmentation)
  • jobs를 할당하고 해제하다 보면, 메모리 사이에 빈 공간들이 조각 조각 생기게 된다. 이런 문제를 외부 단편화라고 한다.
  • 빈 공간을 다 합치면 job을 충분히 할당할 수 있는데 다 조각나있어서 메모리가 낭비되는 문제이다.
• Compaction : 파티션의 빈 공간이 사라지게끔 파티션을 밀어내서 하나의 공간으로 만들어내는 방식이다.
  • 이 방식은 메모리를 밀어내야 하므로, 밀어내려는 메모리를 전부 복사했다가 붙여넣기하는 과정을 거쳐야 한다. 즉, CPU와 시간이 낭비된다.
• paging and segmentation

---

3. Overlays

과거에 two-pass assembler 방식일 때 사용했다. 메모리가 매우 작을 때 pass1 부분을 실행하다가 pass1이 끝나면 pass1은 전혀 사용하지 않으므로 pass1을 메모리에서 없애고 pass2를 메모리에 올려서 실행하는 방식이다.

• instruction, data 같은 부분을 메모리에 잠시 올려뒀다가 필요 없어지면 다시 내리는 방식이다.
• 보통 유저 프로그램에 의해 구현되었다. 메모리의 배치까지 전부 유저가 구현했다.

장점

• 프로세스가 할당된 메모리보다 큰 경우에 필요하다.
• 운영체제로부터 특별한 지원이 필요하지 않다는 장점이 있다.

단점

• 프로그래머가 overlay structure의 디자인을 생각해서 코드를 짜야하므로 복잡하다는 문제가 있다.

---

4. Swapping

지금 사용되는 swapping과는 다른 개념이다. 과거에 사용되었던 기법이고, 싱글 시스템처럼 한 프로세스가 메모리를 통째로 다 쓰는 방법이다. precoess1이 메모리 전체를 다 쓰다가 컨텍스트 스위치가 일어나면 process2를 메모리에 다 불러와서 쓰게 된다. 마치 컨텍스트 스위치처럼 디스크에서 프로세스를 다 불러오는 방식이다.

• 잠시 메모리의 내용을 다 들어내서 backing store에 집어 넣는다.
• 그 프로세스가 다시 필요하게 되면, 디스크에서 읽어서 다시 메모리에 집어 넣는 작업, Bringing back을 수행하게 된다.

문제점

• swap하기 위해 I/O 장치로 transfer 하는 작업이 굉장히 오래 걸린다.
• I/O의 작업을 기다리고 있는데, swapping이 일어나는 경우도 문제가 된다.
  • 이런 상황에서는 swapping 하지 않는다, context switch 하지 않는다는 방식으로 해결할 수 있지만 좋은 방법은 아니다.
• context switch에 굉장히 오랜 시간이 걸린다.
• 요즘에 사용되는 swapping은 demand paging이라고 하며, 여기서 설명하는 swapping과는 다른 개념이다.

---

5. Virtual Memory

이 코드처럼 가상의 어드레스를 출력하면 똑같은 주소가 나온다.

이런식으로 번호마다 받는 사람이 다른 ARS를 생각해보자.

사람들이 전부 5번만 누르면 5번 텔러만 바쁘게 될 것이다.

그런데 중간에 누군가가 다른 텔러로 돌려준다면?

굉장히 좋아진다.

유저는 유저가 원하는 메모리에 엑세스만 할 수 있으면 되고, 피지컬한 메모리는 몰라도 된다. 이 과정을 OS가 효율적으로 해준다.

Virtual Memory

• Virtual Memory에서는 OS가 어플리케이션에게 굉장히 크고 연속된 가상의 어드레스를 사용한다. 32bit 머신에서는 4GB이고 64bit 머신에서는 훨씬 더 크다.
• CPU와 OS가 런타임에 가상의 어드레스 주소를 translation 해준다.
• 가상의 주소를 4GB 쓴다고 해서 피지컬한 메모리 주소에 4GB를 통째로 박아서 사용하는 것은 아니다. 동적으로 할당되고 해제된다.
• 각 프로세스가 사용하는 virtual address는 private해야 한다. 실제로 피지컬한 메모리에 어디에 어떻게 배치될지는 어플리케이션이 모르기에 서로 보호가 된다.

Virtual Address

• virtual address(logical address)는 각 프로세스에게 private한 주소를 주기 위해서이다.
• OS만 가상 주소와 피지컬한 주소의 매핑 관계를 알 수 있고 완전 별개의 주소이다.
• OS는 피지컬한 메모리에서 data의 location을 결정한다.

메모리가 엑세스되는 과정

• CPU가 명령어를 실행하면서 가상 주소를 사용한다.
• OS가 가상 주소를 피지컬한 주소로 변환한다.
• 다른 프로세스가 같은 가상 주소에 접근해도 다른 피지컬한 주소로 접근되게끔 OS가 그렇게 관리한다.

Virtual Address의 장단점과 구현

장점

• 피지컬한 메모리와 가상 주소를 분리시킬 수 있다.
  • 피지컬한 메인 메모리를 굉장히 크고 연속적인 가상의 메모리 어드레스 스페이스로 absract하게 보여줄 수 있다.
  • 따라서 프로그래머는 피지컬한 메모리의 배치를 신경쓰지 않고 좀 더 편하게 프로그래밍 할 수 있다.
• 프로그램이 VAS(가상의 어드레스 스페이스)를 사용할 수 있는데, VAS는 피지컬한 메모리보다 더 크다!
  • 스와핑(메모리가 부족해지면 일부 페이지를 내리는 메커니즘)을 통해 가능하다.
• 더 많은 프로그램을 동시에 실행시킬 수 있다.
• page swapping을 통해 조각조각 옮길 수 있어서 I/O가 덜 필요해진다.
• 프로세스가 공유되는 파일이나 어드레스 스페이스를 통해 쉽게 공유할 수 있다.
• 프로세스의 생성과 protection이 쉬워진다.

단점

• 성능!
  • 계속 translation을 해야하므로 성능이 떨어지고 메모리도 사용해야 한다.

구현

• 페이징
• Segmentation