Memory

paging이란 뭔가요?

paging은 외부 단편화 문제를 해결하기 위해 나온 개념으로 논리적 주소를 일정한 크기로 나누어 메모리와 매핑하는 방식입니다. 이 방식을 통해 외부 단편화가 해결 되었으나 한 페이지내 사용하지 않는 공간 문제인 내부 단편화가 일어날 수 있어 페이지 크기를 적절하게 정하는 것이 중요합니다

 

segmentation에 대해서 설명해 주세요

세그멘테이션은 논리적 주소 공간을 논리적 단위인 코드, 데이터, 스택으로 나누어 물리적주소와 매핑하는 방법입니다.

 

[꼬꼬무1] segmentation의 메모리 단편화(Memory fragmentation) 문제에 대해 설명해 주세요

segmentation같은 경우 논리적 단위로 구분하여 필요한 만큼만 할당하기 때문에 내부 단편화는 발생하지 않습니다. 그러나 남은 공간의 총합은 충분하나 공간이 분산되어 있어 더이상 올리지 못하는 외부 단편화가 발생할 수 있습니다.

[꼬꼬무2] paging과 segmentation의 차이는 뭔가요?

테이블 내에서 세그먼트, 페이지단위로 접근 권한을 부여할 수 있는데, 페이지 같은 경우는 일정 크기로 분할하기 때문에 code, stack, data영역이 섞여 접근 권한 부여가 까다롭지만 세그먼트는 논리적 단위로 나누어져 페이지에 비해 접근 권한 설정이 편리합니다. 그러나 segmentation같은 경우 외부 단편화가 일어나기 때문에 주로 paging기법을 많이 사용하는 것으로 알고 있습니다.

[꼬꼬무3] paged segmentation의 기법에 대해 설명하시오

paged segmentation이란 segmentation을 기본으로 하되, 이를 다시 동일한 크기의 page로 나누어 물리 메모리에 할당하는 메모리 관리 기법입니다. 즉, 프로그램을 의미 단위의 segment로 나누고 개별 segment의 크기를 page의 배수가 되도록 하는 방법입니다.

이를 통해 segmentation 기법에서 발생하는 외부 단편화 문제를 해결하고, 동시에 segment단위로 접근 권한 보호가 이루어지도록 해서 paging 기법의 단점을 해결합니다.

 

• 32비트에서, 페이지의 크기가 1kb 이라면 페이지 테이블의 최대 크기는 몇 개일까요?

총 페이지 개수 = 가상 주소 공간 크기 / 페이지 크기
= (2^32 바이트) / (1KB)

32비트 주소체계를 사용하는 컴퓨터가 있다고 할 때, 주소 공간의 크기는 2의 32승이다.
페이지 하나의 크기가 4KB라면 이는 약 2^12이다.
페이지 테이블에 2^20개(2^32/2^12)의 정보가 저장되어야 하고, 항목 당 4바이트가 사용된다면 각 프로세스는 2의 22승, 즉 4MB의 페이지 테이블 공간을 물리메모리에 필요로 하게 된다.

가상 메모리에 대해서 설명해 주세요 ⭐

가상 메모리의 개념이 나오기 이전에는 실행되는 코드의 전부가 물리메모리에 존재 해야했고, 메모리 용량보다 큰 프로그램을 실행 시킬 수 없었습니다. 또한 가끔만 사용되는 코드가 불필요하게 메모리를 차지하는 문제가 있었고 이를 해결하기 위해 가상 메모리가 나오게 되었습니다

 

가상메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이며, 프로그램이 물리 메모리보다 커도 된다는 장점이 있습니다.

[꼬꼬무1] 요구페이징 (demand paging)이란 무엇인가요?

프로그램 실행 시작 시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 필요한 것들만 적재하는 전략을 요구 페이징이라 합니다.

 

[꼬꼬무2] 페이지 교체 알고리즘(replacement algorithm)을 아는대로 말씀해주세요

필요로 하는 페이지가 주기억장치에 존재하지 않을 시, 어떤 페이지를 선택하여 교체할 것인지 정하는 것을 페이지 교체라합니다.

[꼬꼬무3] LRU알고리즘과 LFU알고리즘을 비교 설명해 주세요

LRU는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘으로 대체적으로 FIFO 알고리즘보다 우수하고, OPT알고리즘보다는 그렇지 못한 모습을 보입니다. 

LFU는 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘으로 참조 횟수가 기준이기 때문에 가장 최근에 불려온게 교체될 수 있어 잘 사용하지 않는 알고리즘입니다.

 

• 가상 메모리가 가능한 이유가 무엇일까요?

실제 프로세스가 동작할 때, 프로세스의 메모리 전체를 다 보는것이 아니라 일부만 보기 때문입니다.

• Page Fault가 발생했을 때, 어떻게 처리하는지 설명해 주세요.

1. page table을 통해 필요한 page가 없다면(invalid) page fault

2. 운영체제에 page fault trap을 발생시킨다.

3. 필요한 page를 backing store에서 찾고 물리 메모리에서 빈 frame을 찾는다. 빈 frame이 없다면 교체 알고리즘으로 page in, page out을 수행해야 한다. 이때 프로세스는 waiting state가 된다.

4. 그리고 물리 메모리에 올리면, page table을 update 한다. 즉, valid bit를 수정한다

5. page fault를 발생시킨 코드를 다시 시작한다.

• 페이지 크기에 대한 Trade-Off를 설명해 주세요.

페이지 크기가 줄어들 경우 내부 단편화 문제가 덜 발생하나 페이지 갯수가 많아져 page table이 커진다. 따라서 PCB가 커져 context switch 비용이 커진다.

• 페이지 크기가 커지면, 페이지 폴트가 더 많이 발생한다고 할 수 있나요?

페이지 크기가 커지면 한 번에 더 많은 데이터를 처리할 수 있어 페이지 폴트가 발생할 가능성이 줄어들지만, 페이지 내 쓸모 없는 데이터의 증가로 인해 페이지 폴트 발생 시의 부담이 증가할 수 있습니다.

• LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?

과거의 정보를 토대로 미래를 예측하는 특성이 있는 알고리즘입니다.

• LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?

Reference bit를 이용하여 LRU 유사 알고리즘을 구현할 수 있다.

 

1. Additional-reference-bits algorithm

페이지별로 reference bit를 8개 사용하여 최신 기준으로 가장 오래동안 참조되지 않은 페이지를 고른다.

2. Second chance algorithm

말 그대로 두번의 기회를 주는 알고리즘으로 reference bit가 1이면 0으로 바꾸면서 기회를 한번 더 주고 reference bit가 0인 page를 교체하는 알고리즘이다.

 

정리

address translation - 가상 주소를 물리 주소로 mapping 하는 과정
protection - 다른 프로세스가 내 메모리 영역을 침범하지 못하도록 보호하는 방법
MMU - CPU코어 안에 탑재되어 가상 주소를 물리 주소로 변환해주는 하드웨어
issue - 해당 메모리 관리 기법 사용 시 발생할 수 있는 문제

Address translation

1.

프로세스의 시작 주소를 저장하는 relocation register에서 시작 주소를 꺼낸후 offset값 346을 더해 mapping

2.

page table내에서 page number에 해당하는 frame number를 찾고 offset(d)를 더하고 mapping

3.

segment table에서 해당하는 base주소를 찾고 offset(d)을 더 해준 뒤 mapping

Protection

4.

limit register에서 프로세스 크기를 가져온 후, offset값이 이보다 더 크면 illegal하다고 알림

5.

페이지 테이블 엔트리는 유효/무효(valid, invalid) 비트라는 하나의 비트가 더 있다. 이 비트가 유효로 설정되면 페이지가 물리 주소에 있음을 나타내고, 무효라면 해당 페이지는 물리 주소 공간에 속하지 않음을 나타낸다.
예를 들어 14비트 주소 공간을 갖는 시스템이 있다. 해당 시스템은 0~10468의 주소만을 사용할 수 있다. 페이지 크기가 2KB일때 아래와 같은 상황이 된다.

이때 0,1,2,3,4,5의 주소는 페이지 테이블에 정상적으로 맵핑이 된다. 하지만 페이지 6,7에서 주소를 맵핑하려 시도하면, 비트가 무효로 설정된 것을 발견하여 트랩을 발생시킨다.

 

6.

segment table안에 permsission관련 bit가 존재하여 segment별로 read, write, execute권한을 체크할 수 있습니다.

 

MMU

7.

offset에 프로세스 시작주소를 더해주면 되는 단순한 구조

8.

MMU는 먼저 TLB를 조회하여 찾고자 하는 가상 주소가 있는지 확인합니다. TLB에 매핑 정보가 없는 경우, MMU는 페이지 테이블을 참조하여 매핑 정보를 가져와 TLB에 저장하고 주소 변환을 합니다. 이렇게 TLB를 통해 매핑 정보를 가져오면 메모리를 통하지 않고 캐시를 통해 매핑 정보를 가져올 수 있기 때문에 변환 속도를 향상시킬 수 있습니다.

9.

가상 주소를 세그먼트 번호와 offset으로 분리한 후, segment table을 통해 매핑 정보를 찾고 offset을 더해줍니다.

 

Issue

10.

프로세스를 연속적인 주소에 할당하기 때문에 빈 공간의 합은 충분한데 공간이 전부 분리 되어 있어 메모리를 할당하지 못하는 외부 단편화 문제가 발생합니다.

11.

프로세스가 필요한 양보다 페이지 크기를 더 많이 할당하여 페이지 내부에서 공간이 낭비되는 내부 단편화 문제가 발생합니다.

12.

논리적 단위인 segment로 할당하기 때문에 외부 단편화 문제가 발생합니다.