LECTURE is here

KOCW 온라인에서 제공되는 이화여대 반효경 교수님의 OS 강의에 대한 정리 요약

• 노션에 기록했듯 CSAPP과 함께 천천히 병행
• 연관 게시글은 강의 진행 순서대로 정렬되어 있지 않고, 내 필요에 따라 강의의 주제를 선택해 듣는다.
• 온라인 상의 타인들이 올려놓은 연관 자료 역시 함께 참고한다.

사용자 프로세스를 물리 메모리에 통째로 올려 놓는 방식에서는 주소 바인딩이 비교적 간단하다. 베이스 레지스터에 각 프로세스에 대한 시작 주소 위치를 담고 있고, 각 프로세스의 주소 체계를 물리 주소 체계로 바꾸는 것이 단지 논리 주소의 0번지가 물리 메모리의 몇 번지에 올라가는지에 대한 시작 주소만 알면 물리 주소를 굼벙변환할 수 있는 게 되니 말이다.

그러나 대게 실제로는 위와 같게 관리되지 않다.

페이징 기법은 프로그램을 구성하는 주소 공간이 동일한 크기의 페이지로 각각 잘려 각각의 페이지가 물리 메모리의 필요한 위치 어디든 올라갈 수 있는 기법이다. 각각의 페이지 별로 주소 변환을 해줘야 한다.

📍 Paging

물리적 메모리를 페이지와 같은 동일한 크기의 프레임으로 미리 나누어 두는 기법이다. 페이지 테이블(PT)은 각각의 논리적인 페이지가 물리 메모리의 어디에 올라가 있는가, 주소 변환을 하는 역할이다. 물리 메모리에서 페이지가 들어갈 수 있는 위치를 페이지 프레임이라 명명한다.

페이지 테이블은 프로세스 당 존재한다. 페이지 테이블은 물리적 메모리인 Main Memory에 상주한다.

페이지 테이블은 논리 주소 개수만큼 페이지 테이블 엔트리(PTE)를 가진다. (여기서 엔트리란, 자료구조 테이블(배열)과 병행되어 자주 등장하는 용어다.) (배열이 프렉티컬하게는 테이블이란 이름으로 많이 불린다.) 이는 페이지의 개수만큼 페이지 엔트리에는 각각의 페이지가 몇 번 프레임에 올라가있는지에 대한 인덱싱 정보이다. 배열이라함은 순차 검색이 필요 없이, 몇 번 인덱스인지에 대하여 바로 접근이 가능하여 효율적이다.그림 속 CPU 옆에 위치한 항목들이 binding을 설명한다. 한 페이지에 대한 정보는 그 p에 페이지 테이블의 논리적 시작 주소가 담겨있고, d은 그 시작 주소에서부터 몇 인덱스 떨어져 있는지 즉 시작 주소로부터의 offset 값이 담겨있다(여기서, offset 값은 내부적 위치이므로 그 값에는 변화가 없다). 고로 PTE를 거치면, f에 페이지 프레임 번호가, d는 변환된 물리적 주소가 담기게 된다.

각 프로세스의 주소 공간 전체를 물리적 메모리에 한꺼번에 올릴 필요가 없고, 일부는 backing storage, 일부는 물리적 메모리에 혼재하는 것이 가능하다.

메모리에 올리는 단위가 동일한 크기의 페이지 단위이므로 외부 조각이 발생하지 않고, 동적 메모리 할당 문제도 고려할 필요가 없다. 다만 프로그램의 크기가 항상 페이지 크기의 배수가 된다는 보장이 없으므로 프로세스의 주소 공간 중 제일 마지막에 위치한 페이지에서는 내부 조각이 발생할 수 있다.

현재 CPU에서 실행 중인 프로세스의 페이지 테이블에 접근하기 위해 운영체제는 2개의 레지스터를 사용한다.
- 페이지 테이블 기준 레지스터(page-table base register)
메모리 내에서 페이지 테이블의 시작 위치를 가리킴
- 페이지 테이블 길이 레지스터(page-table length register)
페이지 테이블의 크기를 보관함

페이징 기법에서 모든 메모리 접근 연산은 총 2번씩 필요하다. (주소 변환을 위해 페이지 테이블에 접근 + 변환된 주소에서 실제 데이터에 접근)

이러한 오버헤드를 줄이고 메모리의 접근 속도를 향상하기 위해 고속의 주소 변환용 하드웨어를 사용하는데, 이 associative register 역할을 하는 것이 TLB(Translation Lock-aside Buffer)라는 것이다.

TLB (Translation Lock-aside Buffer)

메인 메모리와 CPU 사이에 존재하는 주소 변환 별도의 계층이다. 빈번히 참조되는 페이지에 대한 주소 변환 정보만 담게 되는 일종의 캐시같은 존재이며, 페이지 테이블에 대한 일부 데이터를 caching하는 것이다.TLB는 주소 변환 전에 먼저 검색하여 데이터를 체크하고, 존재한다면 바로 주소변환이 발생한다.

TLB는 정보 전체를 담고 있는 것이 아니라 빈번이 참고되는 일부 데이터만을 담고 있기 때문에 물리적/논리적 페이지의 쌍을 가지고 있다.

요청된 페이지 번호가 TLB에 존재한다면 곧바로 대응하는 물리적 메모리의 프레임 번호를 얻을 수 있지만, TLB에 존재하지 않는 경우에는 메인 메모리에 있는 페이지 테이블로부터 프레임 번호를 알아내야 한다.

페이지 테이블에는 페이지 번호가 주어지면 해당 페이지에 대응하는 프레임 번호를 얻을 수 있지만, TLB에는 페이지 번호와 프레임 번호 쌍을 가지고 있으므로 특정 페이지 번호가 있는지 TLB 전체를 병행 검색(parallel search)이 가능하도록 구현해야 한다. (이때 TLB 풀 스캔 시간이 오래 걸리므로 병렬적으로 탐색이 가능한 연관 레지스터를 사용한다.)

TLB는 context switch시, 이전 프로세스의 주소 변환 정보를 담고 있는 내용이 전부 지워진다.

Two-Level Page Table

아까 말했듯이 페이지 테이블의 용량이 크지만, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하고, 고로 로지컬 메모리 크기만큼의 규격 크기로 만들어져야하는 페이지 테이블은 그 안에서 실사용되지 않는 공간에 대해 극심한 낭비이다. 바로 이 공간 활용면의 이슈를 해결하기 위해 고안된 것이 2LPT이다. (속도면의 이슈는 해결되는 바가 없다.)

• page table 자체를 page로 구성.
  
• 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음).
• 사용하지 않는 공간을 빼고 페이징 테이블(배열)을 만들수는 없다. 인덱스를 통해 접근하기 떄문이다.
• 물리 메모리보다 가상 메모리가 더 크더라도 실행에 문제는 없다.

32 bit addesss 사용시 ==> 4GB의 주소 공간

Page Size가 4K시 1M개의 page table entry가 필요
각 page entry가 4B시 프로세스당 4M의 page table 필요(그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하기 때문에 낭비가 심함)

그렇다면 virtual memory크기가 최대 얼마까지 가능한가? -> 메모리를 표시하는 주소 체계를 몇 비트 주소 체계를 사용하냐에 따라 다름 -> 메모리는 byte 단위.

1bit -> 2가지 표현 , 2bit -> 4가지.. 32bit -> 232
210 = K, 220 = M, 230 = G
안쪽 페이지의 크기는 페이지 크기와 같다(4KB). 테이블 자체가 페이지화 되어서 페이지 어딘가에 들어간다. -> 엔트리 하나는 4B, 엔트리 개수는 1K개

Multilevel Paging and Performance

Address space가 더 커지면 다단계 페이지 테이블이 필요해진다. (페이지 테이블이 여러 개 있을 수도 있지만 그만큼 여러 단계를 거쳐야 하고, 주소 변환을 위해 각 단계에 접근하기 때문에 오버헤드가 너무 크다.)각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근이 필요하다.

TLB를 통해 메모리 접근 시간을 줄일 수 있다.

4단계 페이지 테이블을 사용하는 경우,

• 메모리 접근 시간이 100ns, TLB(주소 변환을 용이하게 해주는 캐시 메모리) 접근 시간이 20ns
• ex. TLB hit ratio가 98%인 경우: effective memory access time = 0.98 * 120 + 0.02 * 520 = 128 nanosecond
• 결과적으로 주소 변환을 위해 28ns만 소요됨! (메모리 접근 시간이 100ns이기 때문에)

page table의 각 entry마다 아래의 bit를 둔다.

1. Valid(v) / Invalid(i) Bit

사실 엔트리마다 부가적인 비트가 더 저장되어 있다. 그 중 하나가 Valid(v) / Invalid(i) Bit 이다.
📌 valid 표시의 경우 : 해당 주소의 frame에 유효한 내용 (접근 허용)
📌 invalid의 경우 : 해당 주소의 frame에 유효한 내용 부재 (접근 불허)
.... 1. 프로세스가 그 주소 부분을 사용하지 않는 경우
.... 2. 해당 페이지가 메모리에 올라와 있지 않고, swap area에 있는 경우 등

위 그림에서 가장 왼쪽 테이블이 Logical memory이다. Logical Memory의 개수 만큼 가운데에 있는 페이지 테이블에 엔트리가 존재한다고 일전에 언급했다. 논리적인 메모리가 최종적으로 물리적인 페이지 어디에 적재되어 있는지에 대해서도 페이지 테이블에 저장해두는데, 주소 변환 정보만 들어있는 것이 아니라 vaild-invaild bit이 같이 들어있다.

Logical memory의 최대 개수만큼 페이지 테이블 엔트리가 존재하기 때문에, 현재 사용하고 있지 않는 영역이더라도 엔트리가 존재하게 된다. 사진 속 6,7 페이지가 없지만 페이지 테이블은 존재하는 것도 이와 같다.

이로 인해 우린 vaild-invaild bit를 통해 이미 물리적으로 적재된 페이지인지 판별 가능하게 된다. 항상 메모리에 올라와있지 않거나, 물리적으로 적재되어 있지 않은 경우 invaild bit를 표기하여 파악하는 것이다.

2. Protection Bit

page에 대한 접근 권한 (read/write/read-only)을 나타내는 연산이다. 메모리 영역 중 코드와 같은 영역이 이에 해당하겠다.

Inverted Page Table

여태 소개된 개념에서 역발상한 순서로 가며, sysstem-wide한 페이지 테이블이다. 기존의 비효율을 개선하기 위해 고안되었으며, 프로세스 개수만큼이 아니라 물리적인 메모리의 프레임 개수만큼 존재한다. page frame 하나 당 page table에 하나의 entry를 둔 것.

각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용을 표시한다. (process-id, process의 logical address)

실제 물리적 메모리의 프레임 개수만큼 페이지 테이블에 엔트리가 존재.
페이지 테이블의 첫 번째 엔트리에는 물리적 메모리의 첫 번째 프레임에 들어가는 논리적 메모리의 첫 번째 프레임의 주소가 있고,
페이지 테이블의 두 번째 엔트리에는 물리적 메모리의 두 번째 프레임에 들어가는 논리적 메모리의 두 번째 프레임의 주소가 있음.
페이지 주소 변환이란, 논리적 메모리의 주소를 참조해서 물리적 메모리를 찾아가는 과정이지만, Inverted Page Table은 반대.
논리적 페이지의 페이지 번호 p가 물리적 메모리의 몇 번째 프레임에 위치했는지 찾기 위해서는, 페이지 테이블을 모두 뒤져서 p가 자리한 엔트리를 찾은 뒤 물리적 메모리의 어디에 위치해있는지 알 수 있음.
목적에는 부합하지 않으나 그럼에도 이걸 사용하는 건 페이지 테이블이 메모리에서 차지하는 공간을 줄이기 위한 것. 하지만 시간적인 오버헤드 존재. 뿐만 아니라 p가 어느 프로세스의 p인지 파악하기 위해 프로세스를 구분하는 pid 역시 저장해야 함.

1. CPU가 logical address를 줌
2. 1번에서 받은 주소를 가지고 page entry를 뒤져서 p가 위치하는 물리적 메모리의 frame 위치를 파악
3. p가 여러 개 존재할 수 있기 때문에 현재 CPU를 점유하고 있는 프로세스의 PID를 동시에 줘서 그 PID를 가진 P가 물리적 메모리의 어떤 위치에 존재하는지 찾음.
4. 찾아진 위치가 page table에서 몇 번째 떨어진 위치인지(여기서는 f만큼 떨어진 엔트리) 파악해서 물리적 메모리에 가서 f번째 떨어진 엔트리를 찾음으로써 주소 변환을 완료.

단점 : 테이블 전체를 탐색해야 함 (시간적인 오버헤드 존재)
해결 방법 : associative register 사용 (expensive) -> 별도의 하드웨어를 사용하여 시간적인 오버헤드를 줄이는 방법

Shared Page

다른 프로세스들과 공유할 수 있는 페이지를 말한다. 같은 파일을 여러 개 연다고 생각해보면, 각 해당 파일들에 대한 메모리에서 code 부분은 모두 똑같을 것이다. 이 공통의 부분은 shared code라고 볼 수 있다.

Shared code (Re-entrant Code, 재진입 가능 코드, Pure code)

이렇게 share가 가능한 코드들에 대해서는 반복되는 동일 코드를 한 카피만 메모리에 올려 여러 프로세스와 매핑한다. 이렇게 효율적으로 메모리 공간을 활용하는 것이다. 각각의 프로세스마다 다른 데이터 코드만 메모리에 별도로 올려서 사용한다.

read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림(코드 공유). (e.g. text editors, compilers, window systems)

shared code는 두 가지 조건이 있다. Read-only로만 세팅해야 하며, 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다.

📍 Segmentation

여태 우리는 페이징 기법을 배우며, 하드웨어가 동일한 크기(page)로 프로세스를 구성하는 주소 공간을 분할하여 사용하는 모습을 보았다.

세그먼테이션 기법은 프로세스를 구성하는 주소 공간을 의미단위(ex.code,data,stack...)으로 나누는 것이다.

작게는 프로그램을 구성하는 하나 하나를 세그먼트로 정의, 크게는 프로그램 전체를 하나의 세그먼트로 정의가 가능하다.

세그먼트는 다음과 같은 논리적인 유닛이라 할 수 있다.

main()
function
global variables
stack
symbol table
arrays
...

보통 code, data, stack 기준으로 나누며, 작게 함수 단위로도 나눌 수 있다.논리적 주소는 <세그먼트 번호(s), 오프셋(d)>으로 나뉘어 사용된다.

• 세그먼트 번호는 해당 논리적 주소가 프로세스 주소 공간 내에서 몇 번째 세그먼트에 속하는 지를 나타낸다.
• 오프셋은 그 세그먼트 내에서 얼마만큼 떨어져 있는 지에 대한 정보를 나타낸다.

즉 base의 주소값으로 가서 (offset)얼만큼 떨어져 있는가를 더해준다.

세그먼트 테이블을 사용한다. 세그먼테이션 테이블의 각 엔트리는 기준점(base)과 한계점(limit)이라는 정보값을 가지고 있다.

• 기준점은 물리적 메모리에서 그 세그먼트의 시작 위치를 나타낸다.
• 한계점은 그 세그먼트의 길이를 나타낸다.

두 개의 레지스터가 지원되는데, 세그먼트 테이블 기준 레지스터(STBR)와 세그먼트 테이블 길이 레지스터(STLR)을 사용한다.

• 세그먼트 테이블 기준 레지스터는 현재 CPU에서 실행 중인 프로세스의 세그먼트 테이블이 메모리의 어느 위치에 있는지 그 시작 주소를 담고 있다.
• 세그먼트 테이블 길이 레지스터는 그 프로세스의 주소 공간이 총 몇 개의 세그먼트로 구성되는지, 즉 세그먼트의 개수를 나타낸다.

논리적 주소를 물리적 주소로 변환하기 전 세그먼트 테이블은 두 가지 사항을 확인한다.
✅ 요청된 세그먼트 번호(s)가 STLR에 저장된 값보다 작은 값인가?
-----그 크기보다 크면, 존재하지 않는 세그먼트에 대한 접근 시도이므로 trap 발생!
✅ 논리적 주소의 오프셋 값(d)이 그 세그먼트의 길이(limit)보다 작은 값인가?
-----그 길이보다 길다면, 세그먼트 길이를 넘어서는 오프셋 위치이므로 trap 발생!
세그먼트는 의미 단위로 나누다 보니, 똑같은 크기로 다뤄지는 페이징과 다른 장단점이 있다.

장점

• 페이징보다 protection 하기 쉽다. 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적이다.

단점

• 페이징과 다르게 크기가 균일하지 않다. base뿐 아니라 길이(length register)가 얼마인지 엔트리에 같이 담고 있다. 그렇게 크키가 다르므로 external fragementation 발생, 가변분할과 같이 동일한 문제점들이 발생한다. (일반적으로 테이블에 대한 메모리 낭비가 심한 쪽은 페이징 (4KB))

Sharing of Segments

같은 역할을 하기 때문에 공유를 하는 것
세그먼트 번호가 같고, 물리적인 세그먼트 위치가 같아야 함.
주소 변환 시 같은 주소로 변환됨. (<->private segment의 경우 다른 위치에 적재되어 있음.)

📍 Segmentation with Paging

현실적으로 현재 사용되고 있는 MMU(하드웨어) 중 순수하게 Segmentation 기법을 쓰는 경우는 없다. Paging 역시 마찬가지. 두 기법의 단점을 개선한 Segmentation with paging 기법이 아주 널리 쓰이고 있다.

특히, 서버 및 클라우드 환경에서는 대규모 메모리와 다중 프로세스/쓰레드를 처리해야 하는 경우가 많기 때문에 이 기법이 흔히 사용된다. 또한, 최신 운영체제에서는 가상화 기술과 같은 기술을 이용해 여러 가상 머신을 호스팅하거나, 컨테이너와 같은 가벼운 가상화 기술을 사용하기도 합니다. 이러한 경우에도 segmentation with paging 기법이 사용될 수 있다.

segment 하나가 여러 개의 page로 구성. 때문에 메모리에 올라갈 때 page 단위로 잘려서 올라감.

segment table entry가 물리적 메모리에서 segment가 어디서 시작하는지 나타내는 base address가 아니라 segment를 구성하는 page의 위치를 나타내는 page table의 base address를 가지고 있음. 이를 통해 segment의 크기가 각각 달라 hole이 발생하는 문제를 해결.

어떤 segment를 read-only로 설정할 것인지 등등의 의미단위 작업은 segment table에서 미리 설정.
➡️ logical address에서 s를 통해 setment table 내의 몇 번째 segment entry를 나타내는지 확인.
➡️ 그렇게 알게 된 segment table의 s에서 segment 내부의 page의 시작 위치인 page-table base를 확인.

한편, 물리적 메모리에서 해당 segment가 어디에서 시작하는지 나타내는 offset값 d와 s를 비교하여 error를 검출.

3번에서 이상이 없다면 offset값 d를 나눠서 page의 page-table에서 몇 번째 page entry인지 나타내는 p값과 page의 어디에서 시작되는지 나타내는 offset 값 d'를 확인.

1~4번에서 얻은 값을 통해 최종적으로 논리적 주소를 물리적 메모리 주소로 변환.

이 모든 작업은 MMU라는 하드웨어와 CPU가 해줘야 하는 일.
여기서 운영체제가 하는 일은 없음! 운영체제는 IO Device에 접근할 때. 하지만 메모리 접근 시에는 하드웨어가 작업!