Memory

ian·2023년 1월 20일

Memory

virtual memory = physical memory + swap area

Logical address vs Physical address

A logical address is generated by CPU while a program is running.
This address is used as a reference by the CPU to access the actual physical memory location.

A physical address identifies the physical location of a specific data element in memory.

The user program generates the logical address and believes that the program is running in this logical address space, but the program needs physical memory for its execution, therefore, the logical address must be mapped to the physical address by the MMU before the addresses are used

Demand paging

demand paging (as opposed to anticipatory paging) is a method of virtual memory management. In a system that uses demand paging, the operating system copies a disk page into physical memory only if an attempt is made to access it and that page is not already in memory
(Need replacement algorithms)

Effective Access Time

Demanding Paging은 페이지 테이블에 해당 페이지가 없으면 backing store에서 메모리로 가져오는 과정이 있다. 따라서, 페이지 테이블에 해당 페이지가 있을 때와 없을 때 시간 차이가 발생한다.
이러한 시간 차이를 고려하여 평균적으로 어느 정도 소요되는지 계산하는 것을 유효 접근 시간이라 한다.

Swapping & Demanding Paging

공통점은 둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행한다.
차이점은 Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동한다.

MMU

논리 주소를 물리주소로 변환해 준다.
메모리 보호(base, limit), 캐시 관리 등 CPU가 메모리에 접근하는 것을 총 관리해주는 하드웨어임

각 프로그램마다 중복되는 논리주소를 가짐
Base Register + 가상주소 = 물리주소
메모리에서 프로세스가 가진 정보를 정확하게 가져옴
Limit register로 프로세스가 요청하는 논리주소가 올바른지 확인

TLB

가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시

cpu가 정보를 요청해야할 때 메모리에 두번씩 접근
TLB 사용.
TLB부터 확인. 매칭되는 주소 확인
한번 참조했던 곳을 다시 참조할 가능성이 많음. TLB 성공률 높아짐

지역성
기억 장치 내의 정보를 균일하게 액세스 하는 것이 아니라 한 순간에 특정부분을 집중적으로 참조하는 특성

TLB와 메모리에 없는 페이지를 요구, page fault.
MMU가 프로세스 일시 정지, OS가 check, swapping
중간에 cpu가 다른 프로세스에 넘어갈 수 있음 (context switching)

캐싱 라인
빈번하게 사용되는 데이터들을 캐시에 저장했더라도, 내가 필요한 데이터를 캐시에서 찾을 때 모든 데이터를 순회하는 것은 시간 낭비다.

즉, 캐시에 목적 데이터가 저장되어있을 때 바로 접근하여 출력할 수 있어야 캐시 활용이 의미있어짐

따라서 캐시에 데이터를 저장할 시, 자료구조를 활용해 묶어서 저장하는데 이를 캐싱 라인이라고 부른다.

즉, 캐시에 저장하는 데이터에 데이터의 메모리 주소를 함께 저장하면서 빠르게 원하는 정보를 찾을 수 있음 (set이나 map 등을 활용)

memory management

연속 메모리 할당: 각 프로그램이 주기억장치 내에 인접되어 연속되게 하나의 블록을 차지하도록 배치되는 방법
비연속 메모리 할당: 하나의 프로그램이 페이지나 세그먼트 단위로 나뉘어 분산 배치되는 방법

메모리 공간을 최대한 공간을 활용하기 위해
메모리를 일정하게 frame으로 잘라둔다.
프로그램을 frame과 동일한 크기로 자름 => page
현대 메모리 관리는 페이징 기법을 사용

Fragmentation

1) External Fragmentation
2) Intenal Fragmentation

pages vs segments

Frame allocation

Paging – Computer memory is divided into small partitions that are all the same size and referred to as, page frames. Then when a process is loaded it gets divided into pages which are the same size as those previous frames. The process pages are then loaded into the frames.

Segmentation – Computer memory is allocated in various sizes (segments) depending on the need for address space by the process. These segments may be individually protected or shared between processes. Commonly you will see what are called “Segmentation Faults” in programs, this is because the data that’s is about to be read or written is outside the permitted address space of that process.

페이지의 단점은 내부 단편화 문제의 비중이 늘어난다.
세그먼트의 단점은 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 작은 조각의 자유 공간들이 많아지면서 외부 단편화 문제가 발생

Memory Pool(메모리 풀)

고정된 크기의 블록을 할당하여 메모리 동적 할당을 가능하게 해 준다. memory pool이라고 불리는 동일한 사이즈의 메모리 블록들을 미리 할당해 놓고 프로세스들이 필요할 때마다 사용하고 반납하는 기법이다. (미리 할당하기 때문에 메모리 누수가 있다)

미리 공간을 할당해놓고 사용한 다음 반납하기 때문이 이로 인한 외부 단편화는 발생하지 않는다. 또한 필요한 크기만큼 할당을 하기 때문에 내부 단편화도 존재하지 않는다.

메모리의 할당, 해제가 빈번할 때 메모리 풀 방식이 효과적이다.

page table

page기법
순서보장이 안됨. 복잡해진 페이지 계산
별도의 페이지 테이블 이용

Structure of the Page Table

1)Hierarchical Paging

2)Hashed Page Table

3)Inverted Page Table

shared page

공유 페이지는 여러 프로세스에 의해 공유되는 페이지이므로 물리적 메모리에 하나만 적재되어 메모리를 좀 더 효율적으로 사용

page fualt

page table 확인 후 메모리 상 없다면 OS에서 page fault interrupt를 발생 시키며 이후 저장 매체에서 필요 페이지를 찾아 메모리에 적재시키고 페이지 테이블에 등록
페이지 폴트 인터럽트 발생 시, IDT(Interrupt Descriptor Table)에 가서 해당 인터럽트 번호에 매칭된 OS 내부에 있는 system call 함수를 호출한다. 커널 모드에서 시스템 콜 함수를 실행 후, 커널모드에서 사용자 모드로 전환 후, CPU에게 프로세스의 다음 코드를 실행하도록 한다.

page replacement

Swapping 시 물리메모리에 가득 차있다면 기존 메모리에서 Swap으로 보내야함. Page replacement. 운영체제 결정

Demanding Paging은 요구되는 페이지만 backing store에서 가져온다. 하지만 프로그램들이 계속 실행함에 따라, 요구 페이지도 계속 늘어나게 된다. 그러다보면, 언젠가는 메모리가 가득 차게 될 것이다.
여기서, 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면, 이미 메모리에 적재되어 있는 backing store로 보내고 — 이를 page-out이라고 한다.
한 편으로, 이미 backing store로 page-out이 된 페이지를 victim page이라고 한다.

page replacement algorithm

마지막으로 참조된 시점이 가장 오래된 페이지 (LRU) 를 찾아내는게 적합해보이지만 OS는 이미 물리메모리에 있었으면서, page fault를 회피한 page 정보는 모름, OS가 page fault를 관리한 것만 알
음.

FIFO Algorithm

초기화 코드에 사용

LRU Algorithm

최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나옴

가장 오래 사용되지 않은 페이지를 교체하는 알고리즘이다. 최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다.

LRU의 단점1: 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야 한다. 즉 계수기나 스택과 같은 별도의 하드웨어가 필요하며, 시간적인 큰 오버헤드가 발생한다.
LRU의 단점2: 동일한 패턴이 반복되는 경우 성능이 저하된다. 예를 들어, N개 페이지의 LRU 풀에 대해서 N+1개 페이지의 배열이 반복적으로 참조된다면 매 loop마다 Page Fault가 발생한다.

Clock Algorithm
LRU를 근사화시킨 방식으로, 각 페이지가 최근에 참조되었는지 여부를 활용한다. 1bit짜리 reference bit에 사용했는지 여부를 기록한다. 시간을 일정한 time interval로 나누고, 그 범위 안에서 사용 여부를 비교하는 방식이다.

clock hand가 임의의 페이지를 가리키고 있으며 이 clock hand를 움직여 교체할 페이지를 결정한다. 가리키는 페이지의 reference bit가 1이명 0으로 바꾸고 다음 페이지로 넘어간다. 이 과정을 반복하다가 0인 페이지를 만나면 페이지 교체가 일어난다.

clock hand가 빠르게 돌고 있다면 OS가 과부하 상태일 수 있다. 만약 모든 페이지가 사용 중이라면 clock hand가 전체 페이지를 순회하게 되며, 알고리즘 성능이 FIFO와 동일한 수준으로 떨어지게 된다.

global vs local

global : 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
local : 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식

thrashing

메모리에 프로세스들이 많아지면 프로세스당 frame이 줄어들고
page가 적어지면 page fault가 늘어남.
모든 프로세스들이 page replacement에 빠짐,
CPU가 유휴상태에 빠지고 프로세스들이 계속 메모리에 올라옴
Thrasing.

working set vs page fault-freq.

working set
특정 시간동안 참조되는 page의 수를 확인해서 그 page 수만큼 확보되면 그 순간 페이지들을 메모리에 올림. working-set 단위로 page replacement

page fault freq
상하한을 둬 지급하는 frame의 수를 늘리고 줄임

메모리 고갈 => Thrasing
CPU 사용률 체크 이유 => 사용률이 급격하게 떨어지는 구간 확인 가능, Thrasing 유무 확인

DIRTY BIT
즉 실제메모리가 꽉 찬 경우, 이때는 어쩔수없이 다른 프로그램을 죽여서 새 공간(Victim frame)을 마련해야 한다. 현재 메모리에 상주하고 있는 임의의 페이지를 Disk로 swap out시키고 Disk의 새 페이지를 실제 메모리로 swap in시키게 되는데, 이 경우 두번의 disk writing이 필요하다. (swap in, out) 이것은 상당히 비효율적이다. 이 효율성 문제를 해결하기 위해서 dirty bit (혹은 modify bit)이라는 것이 등장하게 된다. 각각의 page는 dirty bit이라는 정보를 가지게 된다. physical memory상의 page가 어떤 방법에 의해서든지 조금이라도 변경이 되었다면 page의 dirty bit이 켜진다(on). 그렇지 않을 경우에는 dirty bit은 off인 상태다. dirty bit이 on이라는 의미는 physical memory상의 page가 swap out되려면 반드시 다시 쓰여져야 한다. (왜냐하면 내용이 변경되었기 때문에) 즉, dirty bit이 on이면 이 페이지를 victim frame으로 해서는 안된다는 말이다. 근데 dirty bit이 off라면, 그 페이지는 physical memory로 swap in 된 후에 한번도 내용이 변경이 안되었다. 그러면 이 페이지를 victim frame으로 잡은 다음, 이 페이지를 그냥 지워도 된다. disk(가상 메모리)에 원래 내용이 그대로 있으니까 상관없다.

참조
https://jhnyang.tistory.com/133
https://eng.libretexts.org/Courses/Delta_College/Operating_System%3A_The_Basics/07%3A_Memory/7.5%3A_Logical_vs_Physical_Address
https://www.tutorialspoint.com/operating_system/os_virtual_memory.htm
https://eunjinii.tistory.com/142
https://velog.io/@lcy960729/페이징-Paging-보호-Protection
https://dongdd.tistory.com/66
https://neos518.tistory.com/125
https://binaryterms.com/structure-of-page-table.html
https://m.blog.naver.com/sqlmvp/140191559473
https://wansook0316.github.io/cs/os/2020/04/06/운영체제-정리-18-프레임-할당.html
https://vansoft1215.tistory.com/211
https://velog.io/@coral2cola/Memory-Virtualization-Swapping
https://m.blog.naver.com/human_kim/25470505
https://daco2020.tistory.com/174
https://www.javatpoint.com/memory-management-operating-system
https://er.yuvayana.org/memory-management-techniques-in-operating-system/
https://www.geeksforgeeks.org/difference-between-internal-and-external-fragmentation/
https://afteracademy.com/blog/what-are-paging-and-segmentation/
https://sites.google.com/site/hwangslabo/just-understanding/segmentwapage-uichai