메모리에 대해 설명해주세요.
메모리란 주소를 통해 접근하는 장치입니다. 이 메모리 주소는 두가지로 나눌 수 있는데 논리적 주소, 물리적 주소입니다. 논리적 주소(=가상 주소)는 프로세스마다 독립적으로 가지는 주소 공간으로, CPU가 보는 주소입니다. 해당 주소는 각 프로세스마다 0번지부터 시작하게 됩니다. 반면 물리적 주소는 메모리에 실제 올라가는 위치입니다.
사용자가 코드를 작성하고 컴파일, 실행을 하게 된다면, 변수로 선언되어 있던 데이터는 컴파일 과정에서 변수로 선언되어있던 데이터들이 논리적 주소로 변환이 됩니다. 이후에 실제 파일을 실행을 하게 되면서 해당 논리적 주소의 데이터들이 물리적 주소로 변환되어 접근 할 수 있습니다.
MMU에 대해 설명해주세요.
이렇게 논리적 주소를 물리적 주소로 변환시켜주는 하드웨어를 MMU(Memory-Management Unit)라고 하는데, 이는 relocation register(=base register, 접근할 수 있는 물리적 메모리 주소의 최소값)와 limit register(논리적 주소의 범위)로 이루어져 있습니다.
그렇기 때문에 유저 프로그램은 논리적 주소만을 다루게 되고, 실제 물리적 주소를 볼 수 없으며, 알 필요 또한 없습니다.
스와핑에 대해 설명해주세요.
프로세스를 일시적으로 메모리에서 backing store(=디스크)로 쫓아내는 것을 말합니다. 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스를 선정합니다.
swap time은 대부분 trnasfer time으로, swap되는 양에 비례합니다.
메모리 과할당에 대해 설명해주세요.
실제 메모리의 사이즈보다 더 큰 사이즈의 메모리를 프로세스를 할당한 상황으로, 이러한 상황이 사용자에게 들킬 수 있는 경우는 세가지가 있다.
- 프로세스 실행 중 페이지 폴트가 발생
- 페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
- 모든 메모리가 사용중이라 빈 프레임이 존재 X
- 프로세스 하나를 swap out하고, 이 공간을 빈 프레임으로 활용
Page Replacement에서 오버헤드를 줄이는 방법은 뭐가 있을까요?
첫 번째로, 적절한 페이지 교체 알고리즘을 사용하는 것입니다.
두 번째는, 각 페이지 테이블의 엔트리에 변경 여부를 저장하는 비트를 둠으로써 교체될 페이지 내용이 디스크와 달라졌는지를 판단하는 것입니다. 만약 변경 되지 않았다면 디스크에 페이지 내용을 기록할 필요가 없기 때문에, 오버헤드를 줄일 수 있습니다.
캐시 메모리에 대해 설명해주세요.
한정된 빠른 공간에 요청된 데이터를 저장해 두었다가, 후속 요청시 캐시로부터 직접 서비스하는 방식으로, 많은 개발 분야(디스크에 swap area, 캐시 메모리, 버퍼 캐싱, 웹 캐싱)에 사용됩니다.
페이징과 세그멘테이션에 대해 설명해주세요.
프로세스를 메모리에 할당할때, 연속적으로 할당하는 방법과 불연속적으로 할당하는 방법이 존재합니다. 페이징과 세그멘테이션은 이 중 불연속적으로 할당하는 방법으로, 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있는 방식입니다.
연속적 할당 방법에 대해 설명해주세요.
메모리는 일반적으로 두 영역으로 나뉘어 사용하게 됩니다. 첫번째는 OS 상주 영역으로, interrupt vector와 함께 낮은 주소 영역을 사용합니다. 두번째는 사용자 프로세스 영역으로, 높은 주소 영역을 사용합니다.
사용자 프로세스 영역의 할당 방법은 두 가지가 있는데, 연속적인 할당 방법, 불연속적인 할당 방법입니다.
연속적 할당
각각의 프로세스가 쪼개지지 않고, 연속적인 공간에 적재되는 방법입니다.
고정분할 방식(Fixed partition)
물리적인 메모리를 여러개의 partition으로 미리 나누어 놓는 것으로, 파티션에 비해 프로세스의 크기가 작으면서 여백이 발생하게 됩니다. → 내부 단편화, 외부 단편화 발생할 수 있습니다.
가변분할 방식(Variable partition)
메모리를 미리 나누지 않고, 프로세스의 크기를 고려해서 할당하는 것으로,
프로세스가 종료되고, 다른 프로세스가 실행되는 과정을 통해 프로세스 사이에 여백이 발생할 수 있습니다 → 외부 단편화 발생
Hole
가용 메모리 공간을 말하는 것으로, 다양한 크기의 Hole들이 메모리에 흩어져 있게 됩니다. 프로세스가 도착하면 이중 수용 가능한 Hole에 프로세스를 할당하는 과정이 필요한데, 이중 가장 적절한 Hole을 찾기 위해 여러 방식이 존재합니다.
First-fit
해당 프로세스가 들어가는, 최초의 hole에 할당하는 방식입니다.
Best-fit
Size가 n 이상인 가장 작은 hole을 찾아 할당, Hole의 리스트가 크기순으로 정렬되어있지 않은 경우, 모든 hole을 탐색해야합니다. 많은 수의 아주 작은 hole들이 생성됩니다.
Worst-fit
가장 큰 hole에 할당하는 방법으로, 이 역시 모든 hole의 리스트를 탐색해야 합니다.
→ First-fit과 Best-fit이 속도와 공간 이용률 측면에서 효과적입니다.
compaction
외부 조각 문제를 해결하는 방법 중 하나로, 사용 중인 메모리 영역을 한군데로 몰고, hole을 한군데로 몰아 큰 block으로 만드는 방법입니다.
세그멘테이션과 페이징의 차이점은 무엇인가요?
페이징은 프로세스를 나누는 단위를 균등하게 자르는 것이고, 세그멘테이션은 의미 단위의 여러 개의 세그먼트로 자르게 됩니다. 일반적으로는 code, data, stack 부분이 하나씩 세그먼트로 정의되지만, 프로그램 전체를 하나의 세그먼트로 정의하거나, 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의할 수도 있습니다.
페이지와 세그멘테이션에서 실제 주소를 어떻게 가져올 수 있는지 설명해주세요.
페이지
논리적 주소 단위인 페이지를, 실제 물리적 주소 단위인 프레임으로 변환하는 과정이 필요한데, 이는 페이지 테이블을 통해 가능합니다.
CPU에서 나오는 모든 주소는 페이지 번호와 페이지 오프셋으로 이루어지는데, 페이지 번호는 페이지 테이블을 접근할 때 사용되며, 페이지 테이블은 메인 메모리에 존재하고, 각 페이지 주소와 프레임 주소를 매핑하는 테이블입니다.
페이지 테이블을 통해 p번째 페이지를 저장하는 프레임(f)을 알아내고, 해당하는 프레임(f)에 오프셋(d)을 더함으로써 실제 물리 메모리 주소에 접근할 수 있습니다.
세그멘테이션
세그먼트를 물리적 주소로 변경하기 위해서는 세그먼트 테이블이 필요합니다. CPU에 나오는 주소는 세그먼트 번호와 오프셋으로 이루어지는데, 세그먼트 테이블의 각 엔트리는 limit과 base로 이루어져 있습니다.
base는 해당 세그먼트의 물리적 주소 시작 위치, limit은 해당 세그먼트의 길이를 뜻합니다.
오프셋과 limit을 비교해 만약 오프셋이 limit보다 크다면, addressing error를 반환하고, 작다면 base에 오프셋을 더한 주소를 통해 물리적 주소로 접근하게 됩니다.
페이징과 세그멘테이션 기법의 장단점을 말해주세요.
세그멘테이션 대표적으로 세 개의 장점을 가지고 있습니다. 첫 번째로, 일반적으로 페이징 기법보다 공간적으로 유리합니다. 일반적으로 페이지의 개수가 세그먼트의 개수보다 훨씬 많기 때문에, 페이지 테이블로 인한 메모리 낭비가 심합니다.
또한 각 세그먼트 별로 protection bit를 갖게 됩니다. 이는 valid bit와 read/write/execution bit로 이루어져 있는데, 이를 통해 유효한 세그먼트인지와 권한을 확인할 수 있습니다.
마지막으로 세그먼트는 의미 단위로 이루어져 있기 때문에, 자주 쓰이는 세그먼트(특히 code)들을 공유함으로써 재사용하기 쉽습니다.
그렇지만 단점으로는, 각 세그먼트들의 길이가 동일하지 않기 때문에, 가변 분할 방식에서 나타나는 문제점들, 즉 외부 단편화가 발생하게 됩니다.
Paged Segmentation은 무엇인가요?
페이징과 세그멘테이션을 혼합한 방법으로, 각 세그먼트에 페이지 테이블이 존재하는 방식입니다. 즉, 하나의 세그먼트가 균등한 크기의 페이지로 다시 나뉜 것으로, 이를 통해 기존 세그먼트 기법에서 발생하는 외부 단편화 문제가 발생하지 않게 됩니다.
페이지와 프레임의 차이에 대해 설명해주세요.
물리 메모리는 프레임이라 불리는 균등한 크기의 block으로 나누어지고, 논리 메모리는 페이지라 불리는 균등한 크기의 block으로 나누어집니다.
페이지 크기에 따른 trade-off는 뭐가 있을까요?
페이지의 크기가 크다면, 페이지 테이블의 갯수가 적기 때문에 메모리가 절약됩니다. 그렇지만 내부 단편화가 심해짐으로써 공간적으로 낭비가 발생할 수 있습니다.
페이지의 크기가 작다면, 내부 단편화는 줄어들겠지만 페이지 개수가 많아짐으로써 페이지 테이블로 인한 메모리 낭비가 심해집니다.
페이지 테이블의 여러 구조에 대해 설명해주세요.
https://dkswnkk.tistory.com/465
계층적 페이지 테이블(Hierarchical Page Table)
컴퓨터의 주소 공간이 커지게 되면서, 페이지 테이블의 크기도 커지게됩니다. 이에 거대한 페이지 테이블을 메인 메모리에 연속적으로 할당을 하는 것이 무리가 있게 됩니다. 때문에 계층적으로 페이지 테이블을 나누어서 사용하는 방법이 나오게 되었습니다.
대표적인 방법 중 2단계 페이지 테이블 기법이 있는데, 페이지 테이블 자체를 다시 페이지화 함으로써 접근 시간을 줄일 수 있습니다.
해시 페이지 테이블(Hash Page Table)
만약 주소 공간이 32비트가 아닌 64비트라면, 가상 주소를 해시로 사용하는 해시 페이지 테이블을 사용하게 됩니다. 왜냐하면, 64비트의 체계에서 유의미하게 불연속적 할당이 이루어지도록 페이지 테이블의 계층을 나누고자 한다면, 7계층까지 나누어야 하기 때문입니다.
- 가상 주소 공간으로부터 페이지 번호가 오면 그것을 해싱한다.
- 그 값으로 부터 해시 페이지 테이블에서 연결 리스트를 따라가며 첫 번째 원소와 가상 페이지 번호를 비교한다.
- 일치한다면, 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻는다.
역 페이지 테이블(Inverted Page Table)
보통 프로세스는 각자 하나씩 페이지 테이블을 가지고, 또 페이지 테이블은 프로세스가 사용하는 페이지마다 하나의 항목을 가집니다. 때문에 각 프로세스마다 페이지 테이블의 엔트리가 수백만개가 되면서, 메모리 낭비가 심해집니다.
때문에 역테이블은 물리적인 메모리의 프레임에 해당하는 엔트리가 페이지 테이블에 한 항목씩 존재하게 함으로써 물리적 주소로 논리적 주소를 유추하기 쉽게 만들었습니다. (물리적 메모리에 f번째 프레임 항목에 해당하는 것이 페이지 테이블 f번째 항목), 또한 각 항목은 그 프레임에 해당하는 페이지 주소, 페이지를 소유할 수 있는 프로세스 ID를 표시하도록 하였습니다.
이러한 방식의 장점은, 시스템에 단 하나의 페이지 테이블만 존재하면 되기 때문에, 공간적으로 절약이 될 수 있다는 것입니다. 그렇지만 논리적 주소를 통해 물리적 주소를 변환하고자 한다면, 페이지 테이블 전체를 위에서부터 탐색해야하기 때문에 시간적으로 trade-off가 발생하게 됩니다.
어떻게 개선할 수 있을까요?
associative register를 이용하면 병렬적으로 동시에 탐색이 가능하기 때문에, 탐색에 있어 시간적 비용을 줄일 수 있습니다.
TLB에 대해 설명해주세요.
모든 메모리 접근 연산에는 페이지 테이블 접근, 실제 데이터 접근, 총 두 번의 메모리 엑세스가 필요하게 됩니다. 이때 속도 향상을 하기 위해, translation look-aside buffer, TLB라고 불리는 고속의 하드웨어 캐시를 사용할 수 있습니다. TLB는 associative register를 통해 구현이 가능한데, 이는 병렬 탐색이 가능하기 때문에 속도상의 이점을 가지고 있습니다.
페이지 테이블 중 일부가 TLB에 보관되어 있고, 만약 해당 페이지가 TLB에 있는 경우 곧바로 프레임 넘버를 얻지만 그렇지 않은 경우 메인 메모리에 있는 페이지 테이블로부터 프레임을 얻습니다.
어떤 주소공간이 있을 때, 이 공간이 수정 가능한지 확인할 수 있는 방법이 있나요?
페이지 테이블, 세그먼트 테이블의 각 엔트리에 protection bit를 둠으로써 read/write/read-only 등의 권한을 확인할 수 있습니다.
또한 valid bit를 통해 해당 주소의 frame에 프로세스를 구성하는 유효한 내용이 있는지의 여부를 확인할 수 있습니다.
32비트의 논리 주소 체계를 가지고 있을 때 페이지의 크기가 4kb라면 페이지 테이블의 항목은 최대 몇 개일까요?
4kb = 2^12bit이고, 32bit는 2^32bit를 나타내니, 페이지 테이블에 들어갈 수 있는 페이지는 2^20 개입니다.
그렇다면 페이지 테이블의 각 항목이 4B라면, 프로세스당 페이지 테이블의 크기는 얼마일까요?
2^20은 1MB인데, 각 항목이 4B의 크기를 갖는다면 프로세스당 페이지 테이블 크기는 4MB를 가지게 됩니다.
논리 주소는 어떤식으로 나뉘어질까요?
논리 주소는 page number와 page offset으로 이루어져 있는데, page number는 20비트, page offset은 12비트의 크기를 가질 것 같습니다.
페이지 교체 알고리즘에 대해 설명해주세요.
Page Fault로 인해 해당하는 페이지를 물리 메모리로 올릴 때, 만약 메모리에 빈 공간이 없다면, 어떤 프레임을 빼앗아 올지 결정해야합니다. 이러한 프레임을 victim이라 합니다.
이 때 어떤 프레임을 내보낼지 정하는 것이 중요한데, 이유는 그것에 따라 page fault가 일어나는 횟수가 차이나기 때문입니다.
page fault는 일반적인 메모리 접근보다 수십~수백만배의 성능 차이를 가지고 있기 때문에, 최대한 적게 일어나는 것이 중요합니다.
대표적인 알고리즘은 OPT, FIFO, LRU, LFU 가 있습니다.
가상 메모리란 무엇인가요?
프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하도록 하는 기법을 가상메모리라고 합니다.
가상 메모리는 왜 필요한가요?
기존의 메모리 관리 기법들은(페이징, 세그멘테이션) 현재 실행되고 있는 코드들은 반드시 물리 메모리에 존재해야 한다는 조건이 있었습니다.
그렇지만 프로그램에 잘 발생하지 않는 오류 상황을 처리하는 코드, 거의 사용되지 않는 옵션이나 기능들을 메모리에 항상 올라와 있어야 하는 것은 아닙니다.
만약 이러한 부분들을 메모리에 올려두지 않고 프로그램을 실행할 수 있다면, 프로그램이 물리 메모리 크기에 의해 제약받지 않게 되고, 더 많은 프로그램을 수행할 수 있고, 프로그램을 메모리에 올리는 시간이 줄어들어서 빨리 실행될 수 있다는 장점이 존재하게 됩니다.
요구 페이징(Demand Paging)에 대해 설명해주세요.
요청이 있으면 메모리에 페이지를 올린다. 라는 뜻으로
초기에 필요한 것들만 메모리에 로드하는 전략입니다. Demand Paging을 사용하는 가상 메모리에서는 페이지들이 실행 과정에서 필요로 할 때 load됩니다.
이러한 방법을 사용함으로써 얻는 이점은, I/O 양의 감소, Memory 사용량 감소, 빠른 응답 시간, 더 많은 사용자를 수용할 수 있다는 점이 있습니다.
요구 페이징 기법에서는 valid/invalid 비트를 사용하게 되는데, 만약 invalid 하다면, 이는 페이지가 물리적 메모리에 없고 backing store, 즉 디스크에 있는 경우이거나, 아예 사용이 되지 않는 주소 영역(페이지)일 경우가 있습니다. 때문에 주소 변환을 통해서 물리적인 프레임 번호를 얻을 수 있는 경우에만 valid라고 볼 수 있습니다.
만약 주소 변환을 위해 해당하는 페이지 테이블 엔트리에 접근했을 때, invalid하다면 page fault가 일어나게 되고, 디스크에 존재하는 페이지가 물리적 메모리로 올라오게 됩니다.
프로세스 실행 도중 Page Fault가 발생 했을 때의 처리 루틴에 대해 설명해주세요.
- invalid page에 접근하게 되면 MMU가 trap: page fault를 발생시킵니다. 프로세스는 실행이 중지됩니다.
- 운영체제는 커널 모드로 들어가게 되고, page fault 핸들러가 실행됩니다.
- 해당 프로세스에서 사용되지 않는 주소, 보호되어 있는 페이지일 경우 abort가 진행됩니다.
- 물리 메모리에서 비어있는 프레임을 찾습니다. (없으면 replace 과정을 통해 뺏어옵니다.)
- 페이지를 disk에서 memory로 읽어옵니다.
- disk I/O가 끝난 후, 페이지 테이블 중 해당하는 엔트리에 프레임 넘버를 기록하고, invalid bit를 valid로 수정합니다.
- ready queue에 해당 프로세스를 넣습니다.
- 프로세스가 cpu를 점유하고, 중단되었던 작업을 재개합니다.
Optimal(Belady’s optimal, MIN, OPT)
어떤 페이지가 호출될 지 미리 알고 있다는 가정 아래 설계된 알고리즘이기 때문에, 구현이 불가능합니다. 가장 먼 미래에 참조되는 페이지를 replace합니다.
어떤 알고리즘을 쓰더라도 이 알고리즘보다 적은 page fault를 발생시킬 수 없습니다.
FIFO(First In First Out)
메모리에 가장 먼저 올라와 있던 페이지를 교체하는 방식입니다. 가장 구현이 간단합니다.
FIFO의 경우, 물리 메모리의 크기가 클 수록 Page Fault가 적게 날까요?
아닙니다. 메모리의 프레임이 더 클 수록 page fault가 증가하는 현상이 발생하는데, 이러한 현상을 Belady’s anomaly, Belady의 모순이라 불립니다.
LRU(Least Recently Used)
가장 오래 전에 참조된 페이지를 교체하는 방식입니다. 이는 실제로 페이지 교체 알고리즘으로 자주 사용됩니다.
LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?
시간 지역성을 이용한 것으로, 최근에 호출된 것이 이후에 다시 호출될 가능성이 높은 특성을 이용한 것입니다.
LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?
스택, 카운터 등으로도 구현할 수 있지만, 가장 최적으로 구현할 수 있는 것은 linked list라고 생각합니다.
참조한 페이지들을 참조된 순서대로 linked list를 통해 관리할 수 있습니다. 기존에 있던 페이지가 다시 참조 된다면, 해당 노드를 가장 마지막으로 옮김으로써 참조 순서를 업데이트 할 수 있고, 만약 Replace가 필요하다면, 첫번째 노드를 쫓아냄으로써 구현할 수 있습니다.
시간 복잡도는 어떻게 될까요?
O(1)의 시간 복잡도를 가집니다.
LFU(Least Frequently Used)
참조 횟수가 가장 적은 페이지를 교체하는 방식으로, 가장 적은 참조 횟수를 가진 페이지가 여러 개 있다면, 임의로 선정하거나, 가장 오래 전에 참조된 페이지를 교체하도록 구현할 수 있습니다.
LFU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?
각 페이지마다 참조된 횟수를 가지고 있는 heap을 통해 구현할 수 있습니다. LRU와 같이 linked list로 관리한다면, 한 페이지가 참조될 때마다, 업데이트된 참조 횟수에 맞는 위치를 찾아가기 위해 O(n)의 시간 복잡도를 가지게 됩니다. 때문에 이를 줄이기 위해 각 페이지의 참조 횟수를 기반으로 한 heap을 통해 구현할 수 있습니다.
시간 복잡도는 어떻게 될까요?
O(logn)의 시간 복잡도를 가집니다.
LRU와 LFU의 장단점을 비교해주세요.
LFU의 경우, LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 정확히 반영할 수 있습니다.
그렇지만 참조 시점의 최근성을 반영하지 못하고, LRU보다 구현이 복잡하다는 단점을 가지고 있습니다.