---

Background

✔️ Base, limit Register

• 각각의 프로세스는 독립된 메모리 공간을 가져야 하고, 다른 프로그램의 메모리에 접근하는 것을 막아야 한다
• 기준,한계 레지스터를 사용하여 합법적인 메모리 주소 범위를 결정하고 메모리 접근을 보호할 수 있다

기준, 상한 레지스터는 특권 명령을 가진 운영체제에 의해서만 로드(load) 될 수 있다.

커널 모드에서 수행되는 운영체제는 운영체제 메모리 영역과 사용자 메모리 영역의 접근에 어떠한 제약을 받지 않는다.

• 사용자 프로그램을 사용자 메모리 영역에 적재
• 오류가 발생한 경우에 프로그램을 덤프
• 시스템콜의 매개변수를 변경
• 사용자 메모리로부터의 입출력과 다른 많은 서비스들을 제공할 수 있다.

✔️ Address Binding

• 프로그랭은 이진 실행 파일 형태로 디스크에 저장되어 있다.
• 프로그램이 실행되기 위해서는 메인 메모리에 적재되어 프로세스가 되어야 한다

✔️ Logical Address space

유저 프로그램에 의해 생성된 논리적인 주소(CPU가 생성하는 주소) 집합

✔️ Physical Address space

논리주소에 대응되는 물리 주소 집합

✔️ MMU

• Memory Management Unit
• Logical addreess를 Physical Address로 변환하는 하드웨어
• 사용자 프로그램은 실제적인 물리주소를 결코 알 수 없다.

✔️ Dynamic Loading

• 다이나믹 로딩은 프로그램이 실행되는 도중에 필요한 모듈(라이브러리 또는 실행 파일의 일부분)을 런타임(runtime)에 메모리로 로드한다
  • 프로그램의 시작 시점에서 모든 코드를 미리 로드하는 것이 아니라, 프로그램 실행 중에 필요한 모듈을 추가로 메모리에 로드한다.
  • 실행 중인 프로세스에 추가적인 코드나 모듈을 런타임에 동적으로 로드하여 해당 프로세스의 주소 공간에 추가한다.
  • 이렇게 로드된 코드는 실행 중인 프로세스 내에서 호출되어 사용된다.
• 즉, 루틴은 실제 호출되기 전까지 메모리에 로딩되지 않고 재배치 가능한 상태로 디스크에서 대기하다가 호출될 때 메모리에 로딩된다

Relocatable Linking Loader

필요한 루틴을 업로드하고, 프로그램 주소 테이블(logical address)을 업데이트한다

Dynamic Loading 장점

• 메모리를 절약하고, 프로그램의 시작 속도를 향상시킬 수 있다.

✔️ DDLs(Dynamically Linked Libraries)

Staic linking

시스템 라이브러리가 로더에 의해서 다른 모듈들과 바이너리 프로그램으로 함께 결합된다

Dynamic linking

• 프로그램이 실행될 때 프로그램이 사용하는 라이브러리나 외부 모듈들이 실행 파일과 별도로 유지되며, 실행 시점에 필요한 라이브러리를 메모리로 동적으로 로드한다
  • 실행 파일이 시작될 때, 다이나믹 링킹을 지원하는 운영체제는 필요한 라이브러리를 메모리에 동적으로 로드하여 해당 프로세스의 주소 공간에 연결한다.
  • 이렇게 로드된 라이브러리의 코드는 프로세스 내에서 호출되어 사용된다.

Dynamic linking 장점

• 여러 프로세스 간에 공유되는 라이브러리를 사용하여 실행 파일의 크기를 줄이고, 메모리 절약을 가능하게 한다.
• 이로 인해 실행 파일의 크기를 줄이고 여러 프로그램들이 같은 라이브러리를 공유할 수 있다.

Dynamic Loading vs Dynamic linking

• 다이나믹 로딩은 실행 중에 필요한 모듈을 동적으로 메모리에 로드하는 기술이며
• 다이나믹 링킹은 실행 파일과 라이브러리를 분리하여 실행 시점에 필요한 라이브러리를 메모리에 로드하는 기술이다.
  • 다이나믹 링킹은 일반적으로 운영체제의 도움이 필요하다
  • 메모리에 있는 프로세스들이 각가의 공간은 자기만 엑세스할 수 있도록 보호된ㄷ

✔️ Shared Library

• DDL은 Shared 라이브러리라고도 알려져 있다
• 메인 메모리에 라이브러리가 적재되어 있으면 다수의 유저 프로세스 사이에서 공유 가능하다

---

Contiguous Memory Allocation

✔️ 개념

메모리에 프로세스를 한 섹션으로 연속적으로 할당

✔️ Memory Protection

✔️ Memory Allocation

가변 길이로 메모리를 할당하면 hole(가용한 메모리 블록)이 생성된다.

First-fit

첫번째로 적재 가능한 hole에 프로세스를 적재

Best-fit

적재 가능한 hole 중 가장 작은 hole에 프로세스를 적재

Worst-fit

적재 가능한 hole 중 가장 큰 hole에 프로세스를 적재

✔️ Fragmentation

✅ 외부 단편화

• 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면 작은 hole이 많이 생긴다
• 작은 hole들을 모두 합치면 충분한 공간이 되지만 여러 곳에 분산되어 있을 때 발생한다

[솔루션 1] Compaction

• 메모리의 모든 내용을 한군데로 몰고 모든 자유 공간을 다른 한 군데로 몰아서 큰 블록을 만들어서 외부 단편화를 해결할 수 있다

  • 압축은 프로세스들의 재배치가 실행 시간에 동적으로 이루어지는 경우에만 가능하다

  • 주소가 동적으로 재배치 가능하다면, 재배치 작업은 프로그램과 데이터를 새로운 위치로 옮기고 새 위치를 반영하기 위하여 기준 레지스터만 변경하면 완료된다

• 비용이 많이 드는 작업이다

[솔루션 2] 페이징, 세그먼테이션

✅ 내부 단편화

메모리를 파티션으로 쪼개었을 때, 메모리 크기가 파티션의 정수배가 아닐때, 파티션 안에서 발생하는 단편화

---

Segmentation

✔️ Segmentation

• 세그먼테이션은 프로세스의 논리주소를 서로 다른 크기의 논리적 블록으로 분할하여 메모리에 비연속적으로 할당하는 기술

• ex) C 컴파일러는 다음과 같은 세그먼트들을 만들것이다

  1. 코드
  2. 전역 변수
  3. 메모리 할당을 위한 힙
  4. 각각의 스레드를 위한 스택
  5. 표준 C 라이브러리

• 컴파일 타임에 링크되는 라이브러리는 별도의 세그먼트에 할당되어야 한다. 로더는 이런 세그먼트를 받아서 세그먼트마다 번호를 매긴다.

단점

• 가변 크기의 페이지를 사용하기 때문에 여전히 외부 단편화 문제는 발생한다

• 단편화 문제 발생

  • 스왑 아웃 될 때 다양한 크기의 세그먼트를 보조 저장장치에서 미리 확보해야하기 때문에
  • 보조 저장장치는 접근 속도가 느리기 때문에 Compaction이 불가능하다

✔️ Segment Table

---

Paging

✔️ Page

• frame = 물리 메모리를 고정된 블록 사이즈로 분할한 것
• page = 논리 메모리를 프레임과 같은 크기로 분할한 것

• CPU에 의해 생성되는 모든 주소는 page number(p), page offset(d) 두개로 분리된다
• page number는 페이지 테이블에서 인덱스로 사용된다

✅ 페이지 크기

• 프레임 사이즈와 같이 하드웨어에 의해 정의된다
• 대개, 페이지 크기는 2의 지수승이고 4KB에서 1GB 사이이다

논리 주소 공간 = 2^m, 페이지 크기 = 2^n 일 때,
Page number 개수는 2^(m-n)가 생기고, Page Offset 수는 2^n 생긴다.

TODO

✅ 페이지 장점

• 페이지를 적용함으로써 연속적인 메모리 할당에서 발생했던 아래 2가지 문제(외부 단편화,Compaction)를 해결할 수 있다.
• 논리 주소 공간과 물리 주소 공간을 분리한다(물리 메모리에 연속적으로 페이지를 적재할 필요가 없기 때문에)

✔️ 운영체제 지원

✅ 논리 주소 → 물리 주소

• 사용자 프로세스는 자신의 메모리가 아닌 다른 메모리에는 접근조차 할수가 없다

• 페이지 테이블을 통하지 않고서 다른 공간을 접근할 길이 없고, 페이지 테이블은 그 프로세스가 소유한 페이지들만 가리키기 때문이다

✅ 프레임 테이블 관리

• 프레임 테이블을 통해 물리 메모리의 프레임이 어디에 할당되어 있는지, 어느 프레임이 사용 가능한지, 프레임을 관리한다.

✔️ 하드웨어 지원

프로세스 크기가 커짐에 따라, 페이지 테이블 크기도 커진다. 페이지 테이블을 레지스터를 사용해서 페이지 테이블을 저장하기에는 페이지 테이블 크기가 너무 크다. 페이지 페이지 테이블 정보를 관리하는 일이 문제가 된다.

✅ PTBR(Page-table base register)

메인 메모리에 적재되어 있는 페이지 테이블을 가리키는 레지스터

장점

문맥교환이 빠르다

단점

페이지 테이블이 메모리에 있기 때문에 2번의 메모리 엑세스가 필요하다

1. Page Table 엔트리를 위한 메모리 엑세스
2. Frame Address를 위한 메모리 엑세스

✅ TLB(Translation Look-aside Buffer)

• 빠른 검색 캐시 메모리 하드웨어이며, 엔트리는 키와 값으로 구성된다
  • 현대 하드웨어에서의 TLB 검색은 명령어 파이프라인의 일부로 동작하기 때문에 성능에 추가적인 손해를 끼치지 않는다
  • 파이프라인 단계 동안 검색을 하기 위해서는 TLB의 크기는 작게 유지할 수 밖에 없으며 통상 32~1024개의 항목으로 유지한다
• TLB가 가득차면 기존 항목 중 교체될 항목을 선택해야 하는데, LRU, 라운드로빈, 무작위 등 다양한 알고리즘이 선택된다
  • 몇몇 특정 항목(중요 커널 코드와 같은)들은 TLB에 고정시킬 수 있다

• TLB를 페이지 테이블과 함께 사용할 수 있다.

  • 페이지 테이블의 일부분만을 저장한다.
  • key는 페이지 번호, value는 프레임 번호

• TLB hit

  • 페이지 넘버가 TLB에 있을때

• TLB miss

  • 페이지 넘버가 TLB에 없을때는 메모리 참조가 발생한다
  • 참조는 CPU 종류에 따라 하드웨어에서 자동으로 이루어지거나 운영체제에게 인터럽트를 걸어 수행된다

TLB 범위

ASID(Address-space identifiers)

• ASID 항목은 TLB 항목이 어느 프로세스에게 속한 것인지 알려준
  다.
• 가상 주소를 변환할 때 현재 수행 중인 프로세스의 ASID와 TLB 항목의 ASID가 동일하지 않으면, TLB 미스로 처리한다.
  • ASID 지원이 있으면 한 TLB 안에 여러 프로세스들의 정보를 함께 보관할 수 있다.
  • AISD 지원이 없으면 새로운 페이지 테이블이 선택될 때마다(ex: 새 프로세스가 문맥 교환을 해서 실행을 재개하는 경우) 실행 프로세스의 주소 변환이 잘못되지 않도록 TLB는 전부 플러시 된다.

✔️ Memory Protection

• 페이지에 붙어있는 추가적인 비트(valid-invalid bit)에 의해 수행된다
  • bit 🟰 valid : 프로세스의 논리 주소 공간에 위치한 페이지
  • bit 🟰 invalid : 프로세스의 주소 공간에 위치하지 않은 페이지
• invalid bit로 설정된 페이지에 접근하면 트랩 발생한다

✔️ Shared Pages

• 공유 페이지를 사용하여 공통의 코드를 공유할 수 있다.
  • libc와 같은 standard c 라이브러리에서 각각의 프로세스는 libc 복사본을 자신의 주소 공간에 추가하는 대신 코드가 reentrant code라면 공유될 수 있다.
• 코드를 공유하므로써 프레임을 절약할 수 있다.

Reentrant code

실행 도중에 절대 변경되지 않는 non-selif-modifying 코드

✔️ Page table Structure

주소 공간이 너무 커지면 페이지 테이블 자체가 커지는 문제가 발생한다. 모든 페이지 테이블을 메인 메모리에 연속적으로 할당한다면 단편화 문제가 발생할 수 있다.

✅ Hierarchial Page table

• 페이지 테이블을 여러개의 테이블로 분리하여 계층화한다
  • ex) 32-bit 시스템, 페이지 변위 = 12-bit를 2단계 페이징
    • p1=10, p2=10, d=12

✅ Hashed Page table

• 32비트보다 큰 주소 공간을 처리할 때 hashed table을 사용할 수 있다.

✅ Inverted Page table

• 페이지 테이블 대신에 inverted 페이지 테이블을 사용한다
• 메모리 프레임마다 엔트리를 가지고 엔트리는 아래 요소로 구성된다
  • 프레임에 올라와 있는 페이지 주소
  • 페이지를 소유하고 있는 프로세스의 ID
• 시스템에서 하나의 페이지 테이블만 존재하고, 테이블 내 각 항목은 메모리 한 프레임을 가리킨다

TODO

---

Swapping

• 프로세스가 실행되기 위해서는 메모리에 있어야 하지만, 프로세스는 실행 중에 임시로 예비 저장장치로 스왑되었다가 실행을 계속하기 위해서 다시 메모리로 되돌아 올 수 있다.
• 프로세스가 스왑될려면, 그 프로세스는 완전히 휴지 상태여야 한다

✔️ Standard Swapping

• 프로세스 전체를 메인 메모리와 예비 저장 장치 사이에서 이동시킨다

• 디스패처는 레디 큐에 있는 다음 프로세스가 메모리에 올라와 있는지 확인한다

  • 올라와 있지 않다면 디스크에서 불러들인다
  • 이 프로세스를 위한 공간이 없다면 공간을 만들기 위해 현재 메모리에 올라와 있는 프로세스를 내보내고, 불러들인다.

• 이러한 스와핑 시스템의 경우 문맥교환 시간이 오래 걸린다

✔️ Page Swapping

• 현대 운영체제는 문맥교환 오버헤드 때문에 기본 스와핑을 사용하지 않는다
• 프로세스의 페이지는 전체 프로세스를 대신에 페이지 단위로 스와핑될 수 있다.
  • page out = 페이지가 메모리로부터 예비장치로 이동
  • page in = 페이지가 예비장치로부터 메모리로 이동