1. Background

• CPU는 Program Counter(레지스터)가 지시하는 대로 메모리로부터 다음 수행할 명령어를 가져오기 때문에 프로그램은 저장장치에서 메모리 혹은 레지스터로 적재되어야 실행될 수 있다.
• 메모리에 대한 고려사항은 레지스터와 메모리의 접근 속도 차이이다. 레지스터는 CPU의 한 클록사이클로 접근 가능하고, 메모리는 여러 클록 사이클이 필요해 속도 차이로 인해 CPU가 필요한 데이터가 없어서 중단되는 Stall 현상이 일어날 수 있다 → 사이에 캐시를 두어 해결
• 메모리에 대한 또 다른 고려사항은 올바른 동작을 보장하기 위해서 사용자 프로그램으로부터 운영체제 영역을 보호 해야 한다. 이러한 방식은 base(메모리가 프로세스상에 적재될 가장 낮은 주소)와 limit(논리 주소의 범위) 레지스터에 주소를 할당하여 각각의 프로세스가 독립된 메모리 공간을 가지도록 해야한다. 이러한 레지스터 값의 변경은 Kernel mode에서 이루어진다.

A. Address Binding

• CPU가 생성하는 주소는 Logical address or Virtual address, 메모리가 취급하는 주소는 Physical address이다.
• 대부분의 시스템은 사용자 프로세스가 메모리 내 어느 부분으로도 올라올 수 있도록 지원하고 다음과 같은 방식을 보인다.
  • 소스코드에서 주소는 symbol 형태로 표현 된다.
  • 컴파일 과정중 주소는 Relocatable addresses로 바인딩된다.
  • 실행 시간에 Relocatable addresses는 실제 메모리에 적재되는 absolute addresses로 바인딩 된다.
• 바인딩이 이루어지는 시점에 따른 구분
  • 컴파일 시간 바인딩: 컴파일 시점에 프로세스가 메모리 내에 적재될 물리주소 공간을 알면 절대 코드를 생성할 수 있다. → 논리주소=물리주소
  • 적재 시간 바인딩: 컴파일 시점에 절대 주소를 모른다면, 일단 컴파일러는 일단 Relocatable code로 만들어야 한다. 그리고 물리 주소 공간과의 바인딩은 메모리 적재 시점에 이루어진다. → 논리주소=물리주소
  • 실행 시간 바인딩: 프로세스 실행 중간에 메모리 내에서 주소가 변경 될 때 바인딩은 실행 시간마다 이루어진다. → 논리주소 ≠ 물리주소
• 프로그래머는 프로그램이 실행될 때 어디에 적재될 지 모른다는 것을 알아야 한다.

B. Memory Management unit

• MMU는 run-time에 Virtual addresses를 Physical addresses에 mapping한다.( Contiguous Memory Allocation, Paging, Segmentation)
• MMU는 base register를 relocation register라고 부르며 이 레지스터에 들어있는 값을 통해 메모리상 프로세스의 주소를 바꾼다.

C. Dynamic Loading

• Static Loading은 실행될 때 모든 프로그램과 데이터가 적재된다.
• Dynamic Loading은 함수가 실행되기 전까지 메모리에 적재되지 않는다. 이 방식은 메모리 공간을 효율적으로 사용할 수 있으며, 아주 간혹 발생하면서도 많은 양의 코드를 필요로 하는 경우 특히 유용하다.
• Dynamid Loaing은 운영체제에 의해 지원되는 것이 아니라, 프로그램 디자인 시 구현되는 것이다.

D. Dynamic Linking

• Dynamic Linking은 link과정이 실행 시기로 미뤄지는 것이다.
• 주로 시스템 라이브러리에 Dynamic Linking이 사용되며, 만약 Static Link로 라이브러리를 연결 했다면 시스템 라이브러리를 부르는 프로그램들은 이진 프로그램 이미지에 사용될 라이브러리를 모두 가지고 있어야하는 낭비가 생긴다.
• Dynamic Linking에서는 라이브러리를 부르는 곳마다 stub(라이브러리를 어떻게 찾을 것인지에 대한 코드)이 생긴다. stub이 실행되면 필요한 라이브러리가 메모리에 적재되어있는지 확인하고 없으면 디스크에서 로드 해온다.
• 그리고 자신을 메모리에 적재된 라이브러리의 주소로 대체하게 된다. 이러한 구조를 사용하면 printf() 같은 라이브러리를 쓰는 프로세스가 10개가 있어도 메모리상에 이 라이브러리 코드는 한개만 있으면 된다.
• 동적 적재는 동적 연결과는 달리 운영체제의 도움이 필요하다.

2. Swapping

• 프로세스가 실행되기 위해서는 메모리에 있어야 하지만 프로세스는 실행중에 임시로 예비 저장장치에 스왑되었다가 실행을 계속하기 위해 다시 메모리로 되돌아 올 수 있다.
• 시스템은 ready queue에서 CPU Scheduler에 의해 선택된 프로세스를 실행하여 Dispatcher를 호출한다.
• Dispatcher는 실행될 프로세스가 메모리에 있는지 확인하고 없을 경우 디스크에서 불러와야한다. 근데 만약 메모리에 공간이 없다면 현재 메모리에 있는 프로세스를 swap-out하고 원하는 프로세스를 불러 들여야한다.

3. Contiguos Memory Allocation

• 메모리는 일반적으로 운영체제가 적재된 부분과 User 프로세스가 적재된 부분들로 나누어진다.
• Interrupt vector는 주로 낮은 메모리 주소에 위치하기 때문에 OS또한 낮은 메모리 주소에 적재된다.
• Contiguous Memory Allocation 시스템에서 각 프로세스는 다음 프로세스를 포함하는 영역과 연속된 하나의 메모리 영역을 차지한다.

A. Protection

• CPU스케줄러가 다음 프로세스를 고를 때 Dispatcher는 Context-switching을 하며 프로세스가 적재될 base register와 limit register에 정확한 값을 적재하고 이 register들은 Kernel Mode에서 적재되므로 다른 사용자 프로세스로부터 보호가 가능하다.
• MMU가 base register와 limit register의 값을 변경하면서 Logical addresses들은 Dynamic하다.

B. Memory Allocation(Multi-partition allocation)

• 각 분할은 한 프로세스를 가지고 이 분할의 수로 멀티프로그래밍의 정도를 알 수 있다.
• 가변 분할 기법에서 운영체제는 메모리의 사용부분을 확인하는 테이블을 유지한다.
• 초기에 메모리는 한 개의 큰 사용가능한 블록으로 간주되고 이러한 메모리의 연속적인 공간을 Hole이라고 부른다. hole은 여러개 일수도 있다.
• 프로세스는 자신이 들어갈 수 있는 충분한 크기의 hole을 할당받고 반납한다.
• 운영체제는 입력 큐에있는 프로세스들을 일정한 순서로 배치할 수도있지만 공간이 부족하면 입력 큐로 돌아가 다른 프로세스를 알아볼 수도 있다.

• 이러한 기법은 동적 메모리 할당 문제(여러개의 자유블록(hole)중에 어떤 부분을 할당해야하나?)를 발생시킨다.
  • First-fit: 검색해서 처음으로 나온 프로세스를 할당할 수 있는 hole을 할당
  • Best-fit: 프로세스를 할당할 수 있는 hole(Big enough)중 가장 작은 hole을 할당
  • Worst-fit: 프로세스를 할당할 수 있는 가장 큰 hole을 할당

C. Fragment

• 외부 단편화: 남는 자유 공간들을 모두 합치면 충분한 공간이 되지만, 그것들이 너무 작은 조각들로 여러 곳에 분산되어 있을 경우 발생한다. → 프로세스를 메모리의 한쪽으로 밀집시키는 압축 기법을 통해 해결할 수 있으나 메모리상 프로세스의 주소가 정적으로 결정되는 경우 이 기법은 사용할 수 없다.
• 내부 단편화: 할당된 공간이 요구받은 공간보다 클 경우 이들 두 크기의 남는 부분이 내부 단편화문제이다.

D. Segmentation

• Segmentation은 메모리를 사용자 관점에서 볼 수 있게 도와준다.
• 각 Segment는 논리적인 단위로 이루어져있으며, 예를 들자면 main, funciton, method,variable … 등등이 있다.
• 각 Segmentation은 이름과 offset을 가지며, 프로그래머는 프로그램 작성시 모든 주소를 Segment 이름과 offset 두 부분으로 나누어 명기한다.
• 시스템은 Segmentation 구현을 쉽게 하기 위해 Segment 이름 대신에 번호를 매긴다.
• 프로그래머가 작성한 프로그램에서 segmentation이름과 offset은 Segment table(PCB에 저장된다.)의 도움을 받아 Logical(Virtual) Memory 에서 Physical Memory로 mapping된다. Segment table은 base(시작주소)와 limit(길이)로 이루어진다.

cpu는 논리주소를 작성하면 Segment table과 offset의 합을 통해 접근하려는 실제 메모리 주소를 얻는다.

4. Paging

• Segmentation 기법에서 발생하는 외부단편화 문제와 단편화에 따른 압축을 해야하는 문제는 paging을 통해 해결할 수 있다.

A. Basic Method

• Physical Memory는 frame이라는 같은 크기의 블록으로 나누어지고, Logical Memory도 page라고 불리는 같은 크기의 블록으로 나누어진다. 그리고 page의 크기와 frame의 크기는 같다.
• 프로세스 실행시 프로세스의 page는 Physical memory의 frame으로 적재된다.
• page table은 각 page가 Physical Memory에 대응되는 frame에 대한 정보를 가지고 있다.
• CPU에 의해 생성되는 논리주소는 page number와 page offset으로 구성되며, 논리주소의 크기가 2^m일때(m개의 비트로 이루어질때) 상위 m-n비트는 page number를 나타내고 하위 n비트는 page offset으로 구성된다.

• paging 방식은 외부단편화가 일어나지는 않지만 page나 frame을 일정한 크기로 자르기 때문에 frame내부 공간이 낭비되는 내부 단편화 문제가 발생한다.
• 이런 측면에서 보면 page크기가 작은 것이 바람직 하지만, 이에 반비례하여 페이지 테이블의 크기가 커진다.

B. Implement of Page Table & TLB

• 대부분의 컴퓨터는 Page Table을 메인 메모리에 저장하고 PTBR(Page Table Base Register)로 하여금 페이지 테이블을 가리키는 방식을 이용한다.
• 프로세스의 PCB는 프로세스의 여러 레지스터 값들을 저장하고 PTBR에 대한 레지스터 또한 가진다. 그래서 프로세스 교체시 다른 Page Table을 사용해야 할때 PCB에 저장된 PTBR 레지스터를 이용하면 된다.
• 이 방식의 문제점은 페이지 테이블을 위해 한 번, 그 메모리 자체를 위해 한번 이렇게 두번이나 메모리에 접근해야 한다는 것이다. 이 방식에 대한 해결은 TLB를 이용하여 어느정도 해결할 수 있다.
• TLB(Translation Look-aside Buffer)은 매우 빠른 연관 메모리(주소가 아닌 내용으로 찾음)로 키와 값으로 구성된다. 키에는 Page Number, 값에는 Page Number에 해당하는 프레임 번호를 알려준다. 추가로 TLB는 각 항목에 ASIDs(address-space identifier)을 가지는데 ASID는 그 TLB의 항목이 어느 프로세스에 속해 있는 것인지를 알려준다.
• 프로세스마다 Page Number와 Frame Number를 가지므
• TLB hit: TLB에 요청한 Page Number에 대응되는 Frame Number가 있는 경우
• TLB miss: TLB에 요청한 Page Number에 대응되는 Frame Number가 없는 경우, 이 경우 페이지 테이블을 접근하기 위한 메모리 참조가 일어나고 해당 Page Number와 Frame Number을 TLB에 추가 저장한다. 또한 ASID가 현재 프로세스와 일치하지 않는 것또한 miss이다.

C. Protection

• Page table의 각 entry에는 vaild/invaild bit가 하나 더 있다. 이 비트가 vaild인 경우 그 엔트리에 있는 page가 프로세스의 합법적인 페이지이고 invaild인 경우 그 page가 프로세스의 논리 주소 공간에 속하지 않는다는 것을 의미한다. page와 frame을 사상 하려고 할때, invaild/vaild 비트가 무효라면 트랩되어 사상이 멈춘다.
• Paging기법에서 발생하는 내부 단편화의 문제로 단편화된 공간을 넘어간 참조는 부적절하다는 것을 알기 위해 설정한다.