[OS] Memory

Background

• 메인 메모리와 프로세서 자체에 내장되어 있는 레지스터들은 cpu가 직접 접근할 수 있는 유일한 general-purpose storage 이다.
• 레지스터들은 cpu clock의 1 cycle 내에 접근 가능하다.
• cache는 cpu와 메인 메모리 사이에 추가한다.
• cache는 빠르게 접근하기 위해 cpu 안에 있으며, 메모리 접근 속도를 향상시킨다.

base and limit registers

• 각 프로세스가 구분된 메모리 공간을 가질 수 있도록 보장해야 한다.
• 프로세스 당 메모리 공간을 갖게되면 프로세스끼리 보호해줄 수 있으며, 동시성을 위해 여러 프로세스를 동시에 메모리에 올리기 위해선 가장 기초적인 과정이다.
• 프로세스가 접근 가능한 합법 주소 범위르 결정하고 프로세스가 해당 범위만 접근하도록 보장한다.
• base register : 최소 합법 물리 메모리 주소
• limit register : 범위의 크기
  

hardware address protection

• cpu 하드웨어가 사용자 모드에서 레지스터로 생성한 모든 주소를 비교해주는 것으로 메모리 공간 보호를 해줄 수 있다.
• 사용자 모드에서 운영체제 메모리나 다른 사용자의 메모리에 접근하면, 운영체제에 trap을 보내게 되며 이를 치명적인 오류로 간주한다.
• 사용자의 프로그램이 운영체제나 다른 사용자의 코드나 자료구조를 수정하는 것을 방지 해준다.

address binding

• 프로그램이 메인 메모리에 올라오게 되면, 프로세스 되어야 한다.

• 디스크에서 메인 메모리로 들어오기를 기다리고 있는 프로세스들의 집합은 input queue를 구성한다.

• 프로세스 실행 중에 메모리로부터 명령어 및 자료에 접근한다.

• 나중에 종료되면 메모리는 다른 프로세스가 사용해야하니 뺏긴다.

• 대부분의 시스템은 사용자의 프로세스가 물리 메모리 아무데나 있게해준다.
  -> 컴퓨터 주소 공간이 00000에서 실행해도 사용자 프로세스의 주소 공간에 00000에서 시작하는 것은 아니다.

• 대부분의 경우 사용자 프로그램은 여러 단계를 거치고 나서 실행된다.

• 컴파일러는 보통 기호적인 주소를 위치를 바꿀 수 있는 주소로 바인딩 한다.

• 링커나 로더가 이후에 이 위치를 바꿀 수 있는 주소를 절대주소로 바인딩 해준다.

• 각 바인딩은 한 주소 공간으로부터 다른 주소 공간으로 매핑이다.

• 메모리 주소 공간에서 명렁어와 데이터의 binding은 그 binding이 이루어지는 시점에 따라 다음과 같이 구분된다.

1. Compile time : 컴파일 시 프로세스가 메모리 어디에 있을지를 결정할 수 있다면 절대코드(absolute code)가 생성된다.
   -> 컴파일러가 프로세스가 메모리 어느 위치에 들어갈 지 미리 알고 있다.
   -> 한 번 정해진 위치를 계속 쓴다.
   -> 나중에 시작위치가 바뀐다면 코드를 재컴파일해야한다.
2. Load time : 컴파일 시 프로세스가 메모리 어디에 위치할 지 모른다면 컴파일러는 반드시 재배치 가능한 코드(relocatable code)를 생성해야한다.
   -> 최종 바인딩은 로드 시까지 지연된다.
   -> 시작 주소가 바뀌면 오로지 사용자 코드에 바뀐 값만 합쳐 다시 로드하면 된다.
3. Execution time(runtime) : 프로세스가 수행이 시작된 이후에 프로세스가 실행될 때 메모리 주소를 바꾸는 방법이다.
   -> runtime 때 물리적 주소가 결정되고 실행 도중에 주소가 바뀔 수 있다.
   -> cpu가 주소를 참조할 때 마다 address mapping table을 이용해 binding을 점검한다.
   -> 특정 하드웨어에서만 가능하다.
   -> 대부분 운영체제가 이 방법을 사용한다.
   

logical vs physical address space

• logical address : cpu에서 생성한 주소, 가상 주소 virtual address라 부른다.
• physical address : 메모리 레지스터에서 저장하는 주소
• 컴파일 시나 로드 시에 생성한 논리 주소는 물리 주소와 동일하지만, 실행 시에 생성한 논리주소는 물리 주소와 다르다. 이 경우 논리 주소를 가상 주소라고 부른다. 근데 사실상 논리구조와 가상주소를 동일하게 부른다

memory-management unit(MMU)

• MMU라는 하드웨어 장치를 사용해서 논리적 주소를 물리적 구조로 바꿔준다.

• 프로세스가 cpu에서 수행되면서 생성해내는 모든 주소 값에 대해서 base register의 값을 더해줘 물리적 주소를 생성하는 방식이다.

• base register는 하나이므로 프로세스끼리 공유한다.
  -> Base register(Relocation register)는 접근할 수 있는 물리적 주소의 최솟값을 나타낸다.

• 사용자 프로그램은 실제 물리 구조에 접근하지 않는다.

• 오로지 메모리 주소로서 사용될 때 (간접 로드 혹은 저장)만 base register에 의해 재배치 된다.

• 메모리 공간을 더 잘 쓸 수 있다.

swapping

• 프로세스 명령어나 데이터는 반드시 메모리에 있어야 실행이 가능하다.
  .근데 프로세스나 프로세스의 일부분을 잠깐 메모리 밖의 보조 스토리지 (backing store)로 스왑(swap)을 해줬다가, 실행을 계속하려할때 다시 올려줄 수 있다.
• 스와핑을 통해 프로세스의 전체 물리 주소 공간이 시스템의 실제 물리 메모리를 초과할 수 있어 시스템의 다중 프로그래밍의 차수를 높여준다.
  

context switch time including swapping

• 만약 사용자 프로세스의 크기가 100MB이고, backing store는 50MB/s의 전송률을 가진 디스크라고 하면, backing store로부터 100MB 프로세스를 전송하는 데 걸리는 시간은 100MB/(50MB/s) = 2s이다.
• Swap in과 Swap out을 해야 하므로 총 걸리는 시간은 2s X 2 = 4s이다.
• 정확하게 얼마만큼의 메모리가 올라오는지 알 수 있으면 그 시간을 줄일 수 있다.
  -> 프로세스 전체를 올리는게 아니라 필요한 부분만 올린다.

Contiguous Allocation (연속 메모리 할당)

• 운영체제와 여러 사용자 프로세스들은 반드시 주기억장치에 기억되어 있어야 한다.
• 가장 효율적으로 할당해야할ㄴ다.
• 초기 방법 중 하나인 연속 메모리 할당만 설명한다.
• 메모리는 보통 os영역이랑 user 프로세스 영역 둘로 나뉜다.

Hardware Support for Relocation and Limit

• 프로세스가 자기 메모리가 아닌 곳으로 접근 못하게 막는다.
• relocation register가 한다.
• 각 가장주소는 반드시 limit register 범위 내에 존재해야한다.
• MMU가 가장주소에 relocation register를 더해줘서 동적으로 매핑한다.
• 매핑된 주소는 메모리에 보내진다.
  

Multiple-partition allocation

• 메모리를 할당하는 가장 간단한 방법은 프로세스를 메모리에 딱 넣을 수 있는 만큼의 크기로 분할하여 넣는 것이다.
• 이런 가변분할(variable partition)에서는 운영체제가 메모리 중 어느 부분이 현재 사용 중인지를 기록해야한다.
• 처음에는 전부 사용 가능한 상태일 것이고, 하나의 거대한 메모리 덩어리, 어떻게 보면 하나의 거대한 구멍 (hole) 이라 할 수 있다.
• 프로세스가 시스템에 들어오면, os가 프로세스 별로 메모리가 얼마나 필요한지를 확인하고 메모리 할당을 결정한다. 할당이 되면 메모리에 프로세스를 올려서 cpu를 얻기 위해 다른 프로세스와 경쟁하게 만들어 준다.
• 프로세스 종료되면 메모리를 반환할 것이고 os는 이걸 다른 프로세스에게 할당해주면 된다.
• 필요한 만큼 잘라주기 때문에 내부 단편화가 없다.
  

Dynamic Storage-Allocation Problem (동적 저장 공간 할당 문제)

• 동적 저장 공간 할당 문제란, 주어진 hole 목록에서 크기 n만큼의 메모리를 요구하는 요청을 들어주는 방법을 찾는 문제이다.

first-fit : 공간이 충분한 처음 hole에 할당한다.
공간 활용률이 떨어진다.

best-fit : 공간이 충분한 hole 중에 남는 공간이 가장 적은 딱 맞는 곳에 할당한다.
적합한 곳을 찾으므로 탐색시간이 오래 걸린다 -> 오버헤드
크기가 큰 파티션은 유지가능한데, 작은 크기의 파티션은 너무 많이 발생한다.

worst-fit : 공간이 충분한 hole 중 크기가 가장 큰 hole에 할당한다.
모든 파티션을 살펴보므로 탐색시간이 오래 걸린다 -> 오버헤드
작은 크기의 파티션 발생을 줄일 수 있는데 큰 크기의 파티션 확보는 어렵다.

• 그래도 worst-fit보단 first-fit, best-fit이 낫다!

Fragmentation

• external fragmentation (외부 단편화) : 전체 메모리 공간이 요청을 충족하기 위해 존재하지만 연속적이지 않다. 필요한 사이즈로 메모리 할당시 발생앞에 3가지 애들은 외부 단편화가 방생한다.
  -> 압축(compaction)으로 해결할 수 있다.
  --> 이 방법은 메모리의 모든 내용을 한 군데로 몰고, 모든 free space들을 다른 한 군데로 몰아서 큰 block을 만드는 방법이다.
  --> 주소를 재매핑하는게 동적으로 가능할 때, 실행시간이 끝났을 때 가능하다.
  -> 페이징(paing)으로도 해결가능하다.
  --> 가상 주소 공간이 비연속적일 수 있게 해서 물리 메모리에 공간이 있는 곳마다 할당하는 것이다.

컴퓨터 시스템에서 가장 일반적인 메모리 관리 기법이다.

• internal fragmentation (내부 단편화) : 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있는데, 이 두 공간의 크기 차이를 말한다.

Logical View of Segmentation

• 서로 비슷한 역할을 하는 것끼리 모아 놓고 떨어뜨려보자

Segmentation Architecture

• 세그멘테이션은 프로그래머가 인지하는 메모리의 모습을 실제 physical 메모리의 모습으로 변환해주는 기법을 제공한다.
  

• 위와 같이 프로그래머가 생각하는 모양을 그대로 지원하는 메모리 관리 기법이다.

• 프로그래머가 생각하는 논리구조 공간은 세그먼트들의 집합으로 이뤄진다.

• segment table의 각 항목은 segment의 base와 limit를 가진다.
  -> base : segment의 시작 주소를 나타낸다.
  -> limit : segment의 길이를 명시한다.

• Segment Table Base Register (STBR) : 메모리에서 segment table의 위치를 나타낸다.

• Segment Rable Length Register (STLR) : 사용중인 프로그램의 segment 수의 길이값을 나타낸다.
  -> 즉 segment num s < STLR 이다.
  

• 몇번째인지를 segment 테이블에서 본다.

Paging

• 프로세스 물리 주소 공간이 연속적이지 않아도 된다.
• 페이징을 사용하면 외부 파편화를 해결할 수 있다. 압축도 필요 없다.
• 페이징은 swap-out 되는 다양한 크기의 세그먼트를 backing storage에 저장해야 하는 문제도 해결한다.

기본방법

• 페이징 구현의 기본은 물리 메모리를 고정된 크기의 블록 즉, frame 프레임으로 나누고, 가상 메모리를 이와 동일한 크기의 블록 즉, page 페이지로 나누는 것이다.
• 프로세스를 실행하려면 프로세스의 페이지를 프로세스가 있는 곳에서 사용가능한 메모리 프레임에 적재한다.
  보조 기억 장치는 메모리 프레임과 동일한 고정된 크기의 블록 혹은 여러 프레임의 군집으로 나뉘어 진다.
• cpu가 생성한 모든 주소는 page number(p)와 페이지 오프셋(d)로 나뉜다.
• 페이지 수는 페이지 테이블에 대응하는 색인으로 사용한다.
• 페이지 테이블은 물리 메모리의 각 프레임의 베이스 주소를 갖고 있으며, 오프셋은 참조하는 프레임에서의 위치를 의미한다.
• 프레임 베이스 주소와 페이지 오프셋을 합쳐셔 물리 메모리 주소를 알 수 있다.
  

• MMU가 cpu가 생성한 가상 주소를 물리 주소로 변환할 때 다음 단계를 거친다.

1. 페이지수 p를 구해서 페이지 테이블의 색인으로 삼는다.
2. 페이지 테이블에서 이 색인에 대응하는 프레임 수 f를 구한다.
3. 가상 주소의 페이지 수 p를 프레임 수 f로 교체한다.

• 오프셋 d 자체는 바뀔 일이 없으므로 교체해줄 필요가 없다. 프레임 수와 오프셋 두 개가 물리 주소를 구성한다.
  

• n = 2, m =4. 즉, 페이지 크기가 4, 물리적 메모리가 32byte

• 페이징을 하면 외부 파편화가 없어진다 -> 빈 프레임이 결국 필요한 프로세스에게 할당이 되니깐 하지만 내부 파편화는 발생한다.이때 프레임은 유닛 단위를 할당이 된다.

• page size - 2048 bytes, process size = 72766 bytes

• 둘이 나누면 35page + 1086 bytes

• 35개는 내부 파편화 없이 꽉꽉 채우고 1개의 페이지에 대해서는 내부 파편화가 생긴다.

• worst case sms 1fram - 1byte

• 평균적으로 1/2 frame size

• 페이지 하나의 크기를 얼마나 잘 조절하는가에 따라 해시 테이블의 크기도 달라지고 우리가 그것을 인덱싱 할 때 시간도 달라지고 레지스터의 크기도 달라진다.
  -> 해시의 크기를 마냥 줄이는건 좋지 않다 -> 줄이면 줄일수록 내부 파편화는 줄일 수 있지만 페이지테이블 자체에 들어가는 overhead가 늘어날 수 있다.
  

• 페이지가 4개가 필요함 -> 어찌 됐든 mapping만 하면 된다.

• mapping 시키고 남는건 15이다.

Implementation of Page Table

• 페이지 테이블의 크기가 큰 경우네는 main memory에 저장한다.

• 페이지 테이블 기준 레지스터(PTBR)가 페이지 테이블을 가리키게 한다.
  -> 이 방식은 context switch 시간을 줄일 수 있지만, 메모리접근 시간을 늘릴 수 있다.

• 이에 TLB(Translation Look-aside Buffers)로 불리는 특수한 소형 cache가 사용된다.

• TLB는 보통 64개에서 1024개의 엔트리를 가질 수 있음

• 만약 페이지수가 TLB에 없다면 (TLB miss) 페이지 테이블까지 가야한다. 프레임 수를 얻은 후에는 이걸로 메모리에 접근한다. -> 나중에 좀 더 빨리 찾을 수 있게 해준다.
  

• TLB를 먼저 본다 있으면 good -> physical memory에 접근

• 없으면 (TLB miss) page table에 접근

Effective Access Time

• TLB를 보는 것
  

Shared Pages

• 페이징의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 점이다. (multi-tasking에서 중요)
• 재진입 가능 코드는 수행하는 동안 절대 변하지 않고, 두 개나 그 이상의 processor 들이 동시에 같은 코드를 수행할 수 있다.