[운영체제] 메모리 관리, 페이징기법, 세그멘테이션, 가상메모리

[메모리 관리]

*Logical address vs Physical address

• Physical address : 물리 메모리에 실제 올라가는 위치
• Logical address : 각 프로세스마다 독립적으로 가지는 주소공간
• -> CPU가 보는 주소는 logical address

-> 프로그램을 실제 메모리에 올리기 위해 Logical address를 Physical address로 바꿔주는 과정이 필요한데 이를 Address binding이라고 한다.

*Address binding

어떤 프로그램이 메모리의 어느 위치에, 즉 어떤 물리적 주소에 load 될지를 결정하는 과정이다.

• Compile Time binding

이미 컴파일 때 물리적 메모리 주소로 변환되므로 컴파일에 존재하는 주소를 그대로 사용한다. 이 방식은 여러 프로그램을 실행하면 이 주소가 겹칠 수도 있다 등의 문제가 있어서 옛날에 프로그램을 하나씩만 올릴 때에 사용하던 방식이다.

• Load Time binding

프로그램을 로드할때 물리적 주소가 정해지는 방식이다. 로드할 때 물리적 주소를 확인하고 비어있는 곳에 할당되는 방식이다. 이로 인해 논리주소와 물리주소가 다르다. 프로세스 내에 메모리를 참조하는 명령어들이 많은데 이들의 주소를 다 바꿔줘야하기 때문에 로딩할때 시간이 매우 오래걸릴 수 있다.

-> 위 두 방식은 현재 잘 안쓰이는 방식이다.

• Execution Time(Run Time) binding

프로그램이 실행할때 물리적 주소가 정해지며 실행을 시작한 이후에도 프로그램이 위치한 물리적 주소가 변경될 수 있는 바인딩 방식이다. 논리주소에서 할당하고자 하는 물리 주소의 값 만 더해서 할당하면 된다. 이때 더하는 연산이 발생하는데 이를 도와주는 하드웨어가 MMU다.

*MMU

Logical address를 Physical address로 매핑해주는 하드웨어를 말하며 재배치 레지스터를 가지고 있어 만약에 346번지에 들어가야하는 코드가 있는데 현재 메모리에는 빈공간으로 14000번지가 있다고 한다면 재배치 레지스터가 14000이라는 값을 더해주어 코드가 14346번지엣 실행하게 해준다.

*단편화(Fragmentation)

프로세스들이 메모리에 적재되고 제거되는 일이 반복되면 프로세스들이 차지하는 메모리 틈 사이에 사용하지 못할만큼의 작은 공간들이 발생하는 현상을 말한다. 단편화에는 외부 단편화와 내부 단편화로 나뉜다.

*외부 단편화

프로세스가 할당되고 해제되고 하는 과정에서 프로세스가 들어가지 못하는 공간들이 생긴다. 이런것들을 외부 단편화라고 한다. 이를 해결하기 위해 페이징기법이 등장했다

*페이징 기법

연속적이지 않은 할당 방식을 말한다. 메모리는 프레임(Frame), 프로세스는 페이지(Page)라 불리는 고정 크기의 블록으로 분리한다. 한 프로세스가 사용하는 공간은 여러 page로 나뉘어 관리되고, 각각의 page는 순서와 관계없이 메모리의 frame에 매핑되어 저장된다.

이렇게 되면 프로세스가 순서대로 메모리에 저장되지 않기 때문에 page가 어느 frame에 들어가 있는지 알아야 한다. 이에 대한 정보가 page table이라는 테이블에 저장되어 있고, 이를 사용하여 논리적 주소를 물리적 주소로 변환한다.

*paging의 단점

•  내부 단편화가 생긴다.

메모리를 프레임으로 쪼개고 해당 프레임안에 쪼금 남는 영역을 내부 단편화 라고 한다.

-> 페이징이 프로세스를 프레임크기와 맞춰 쪼개는건데 10씩 쪼개다가 전체 크기가 92라서 2만큼의 크기가 남아있을때 이를 하나의 프레임에 넣으면 8이라는 공간이 생김 -> 내부 단편화가 생김

• page table을 저장하기 위한 메모리가 추가로 소모된다.

page table이 메모리에 상주하기 때문에 메모리에 할당하기 위해 2번의 메모리 접근이 필요하게 되어 속도가 느리다. (page table에 접근 -> 실제 연산)

이러한 문제점을 해결하기 위해 페이지 테이블도 캐시로 만들어 해결했다. 페이지 테이블을 별도의 칩으로 만들어서 CPU와 메모리 사이에 위치시키는 것이다. 이러한 테이블을 TLB(Translation Look-aside Buffer)라고 부른다.

*TLB

캐시의 역할을 하며, 실제 전체 페이지 테이블은 메모리에 있고 일부를 TLB에 가져와서 사용한다.

-> TLB에 있는 경우 TLB hit, 없는 경우 TLB miss

-> TLB에 유요한 페이지가 있을 때와 없을 때의 속도 차이가 발생

그런데 만약 물리 메모리보다 더 큰 프로세스를 수행하게 된다면 어떻게 될까?

-> 100mb메모리에 200mb프로세스를 실행한다면..? (실제로 게임의 용량은 매우매우 큼..)

프로세스가 아무리 크다해도 지금 내가 하려는 동작에 필요한 부분은 한정되어 있을 것이다. 이렇듯 필요한 부분만 메모리에 적재하는 방법으로 해결할 수 있다. 이처럼 현재 필요한 페이지만 메모리에 올리는 것을 Demanding Paging(요구 페이징) 이라고 한다.

*Demanding Paging

위 이미지는 요구 페이징의 모습이다. 각 프로세스(P1,P2)는 필요한 페이지만 올려진 모습이다. 기존 page Table과 다른점은 옆에 Vaild bit라는것이 생겼다는 점이다. 이는 해당 페이지가 실제로 메모리에 올려져 있는지 아닌지를 확인하기 위한 값이다.

-> 1이면 물리메모리에 할당되어 있고 0이면 할당되어있지 않고 이런방식..

이렇게 필요한 페이지만 올리게 될 경우 CPU가 아직 메모리에 올리지 않는 페이지에 접근하려고 할 수 도 있다. 이럴때 CPU는 인터럽트를 발생해 해당 페이지를 메모리에 올리는 작업을 한다. 이처럼 CPU가 접근하려는 페이지가 메모리에 없는 경우를 Page Fault(페이지 부재)라고 한다.

*Swapping vs Demanding Paging

둘다 메모리와 backing store(hdd,sdd같은 애들) 사이를 오가면서 수행하지만 swapping은 프로세스 단위로 이동하고 demanding paging은 페이지 단위로 이동하는 차이점이 있다.

만약에 이러한 방법들을 통해 backing store에서 계속해서 페이지를 가져오는데 프로그램이 실행됨에 따라 요구하는 페이지가 늘어나서 결국 메모리가 가득차게 된다면 어떻게 해야할까? 이미 메모리에 있는 페이지 중 하나를 다시 backing store로 보내고 (page-out), 새로운 페이지를 메모리에 올려야한다(page-in). 이를 페이지 교체라고 한다. 여기서 page-out된 페이지를 victim page라고 한다.

*victim page(희생양 페이지)

희생양 페이지를 고르는 건 어떤 기준으로 골라야할까? 이미 작업이 된(수정이 된)페이지는 backing store로 가면 그 과정에서 수정이 필요하다. 그렇기 때문에 수정되지 않는 페이지를 page-out하는게 좋다. 이를 기록하기 위해 modified bit라는 값을 하나 추가하여 이 값을 통해 수정 여부를 판별할 수 있다.

여기서 또 고민해볼 수 있는게 하나 더 생긴다. 만약 수정되지 않은 파일이 여러개라면? 이때는 무슨 기준으로 선택해야하는가.. 단순히 랜덤으로 선택될 수 도 있고 FIFO의 방법을 채택할 수도 있고 그외에도 Optimal 알고리즘, LRU(Least-Recently-Used) 알고리즘등을 활용할 수 있다

*페이지 교체 알고리즘

페이지 교체 알고리즘을 공부하기 전에 Page reference string에 대한 사전지식이 필요하다.

만약에 페이지의 단위이가 100Byte라고 가정해보자. 그럼 100~199번지까지는 같은 페이지에 한꺼번에 가져오기 때문에 같은 100번대에 있는 값은 메모리폴트가 일어나지 않는다.

따라서 페이지 번호가 1(101) 1(186) 1(123) 4 6 1 1 6 6 일때 페이지 참조 열은 1 4 6 1 6이 된다.

FIFO : 메모리에 올라온 지 가장 오래된 페이지를 교체하는 알고리즘이다. FIFO 알고리즘의 경우 프레임 수가 적을수록 페이지 결함이 더 많이 일어난다. 왜냐하면 계속 교체를 해줘야하기 때문이다.

FIFO방식은 초기화 코드에 대해서 적절한 방법이라고 할 수 있다. 초기화 코드는 처음에 프로세스가 실행될 때 최초 초기화를 시키는 역할만 수행하기 때문에 메인 메모리에서 내려도 괜찮다.

OPT(Optimal) : 앞으로 가장 사용하지 않을 페이지를 교체하는 알고리즘이다. 용어만 봤을땐 굉장히 이상적이다. 실제로 FIFO보다는 메모리폴트가 적게 발생한다. 문제는 앞으로 사용하지 않을 페이지라는 것이 보장되어 있지 않는다. 그래서 실질적으로 수행하기에는 큰 어려움이 있다.

LRU(Least-Recently-Used) : 최근에 사용하지 않은 페이지를 가장 먼저 내려 보내는 알고리즘이다. 최근에 사용되지 않았다면 나중에도 사용되지 않을 것이라는 아이디어로부터 온 것이다. OPT는 미래에 대한 예측이지만 LRU는 과거를 보고 판단하므로 실질적으로 사용 가능한 알고리즘이다.

대부분의 컴퓨터는 LRU방식으로 페이지 교체를 하게 된다

프로세스는 원활하게 수행하기 위해서는 일정수준 이상의 페이지 프레임을 할당받아야한다. 그런데 운영체제 입장에서 CPU 이용률을 계속 보면서 이용률이 너무 낮아지면 새로운 프로세스를 더 추가해서 멀티 프로그래밍의 정도를 높인다. 이렇게 되다보면 프로세스별 할당된 프레임수가 적어지고 페이지 폴트도 크게 상승해 CPU이용률이 급격히 떨어질 수 있다 이와 같은 현상을 쓰레싱이라고 한다.

이를 방지하기 위해 각 프로세스가 필요로 하는 최소한의 프레임 갯수를 보장해주거나 페이지빈도 알고리즘과 같은 알고리즘을 활용할 수 있다

페이지빈도 알고리즘 : 페이지 부재율 주기적으로 조사 -> 부재율이 미리 정해놓은 상한값을 넘게되면 프레임 추가로 할당 -> 추가로 할당할수 있는 프레임이 없다면 일부 프로세스를 swap-out

반면, 부재율이 하한값이하로 떨어지면 너무 많은 프레임이 할당되었다고 판단 -> 프레임 수 감소

멀티 쓰레드 환경에서 문제가 되는 것은 공용 공간의 데이터에 접근할 때 발생한다. lock 역시 공용 공간의 데이터에 한 쓰레드만 접근하기 위해 사용하는 것이다. 기껏 멀티쓰레드환경을 택해놓고 한 쓰레드만 작업하게 만들어 둔것이다. 그래서 heap영역과 데이터 영역처럼 전역 공간이지만 스택처럼 각 쓰레드별로 할당할 수 있는 저장 공간인 Thread Local Storage를 사용한다.

개념은 간단한데….이걸 언제 쓰는거지

-> 서로 다른 스레드끼리 공유해야할 자원이 있을때, 해당 자원에 lock없이 접근하고 싶아면 TLS를 이용해 각 스레드마다 자원을 따로 만들어 각자 리소스를 쓰게 할 수 있다.

-> 만약 엄청 많은 일감(?), 작업등이 큐에 쌓여있다고 하면 큐에서 하나씩 꺼내서 처리하는게 아니라 한 100개씩 뭉퉁구리로 꺼내서 TLS에서 넣어둔다음에 TLS에서 사용하는건 굳이 lock을 걸지 않고 사용할 수 있다..

-> 공용 공간에 접근하는 횟수도 줄일 수 있음 -> 대신 공용공간에 접근할때는 lock걸어서 안정성 보장을 하자

[세그멘테이션]

페이징은 프로세스를 물리적인 단위인 페이지 단위로 잘라서 메모리에 적재하는 방법이라면 논리적인 단위인 세그멘트로 자르는 방법을 세그멘테이션이라고 한다. 프로세스 하나를 동작하기 위해서는 기본적으로 코드, 데이터, 스택등의 세그먼트를 가지고 있다. 더 들어가보면 코드에서도 main함수가 있을 수 있고, 다른함수, 더 들어가 배열단위로도 나뉜다. 그래서 페이지와 달리 세그멘트들의 크기는 일반적으로 같지 않다.

*세그멘테이션의 장점을 알아보자

페이징은 프로세스를 같은 단위로 자르게 되므로 중요하지 않은 부분이 같은 페이지 안으로 잘라질 수 있다. 예를 들어 코드 영역같은 경우 논리적인 단위로 나누는 세그멘테이션과 달리 페이징은 같은 크기 단위로 자르기 때문에 애매하게 잘려질 확률이 있다. 하지만 세그멘테이션 방법으로 자르게 되면 코드 영역은 코드영역, 중요한 세그멘트, 중요하지 않은 세그멘트를 논리적인 내용 측면에서 자를 수 있는 장점이 존재한다.

*세그멘테이션은 왜 지금 많이 사용하지 않는가?

세그멘테이션은 치명적인 단점이 존재한다. 세그멘트의 크기가 고정적이지 않고 가변적이라 동적 메모리 할당을 해야하는데 이때 외부단편화가 생길 수 있다. 현재는 페이징기법을 많이 사용한다.

-> 외부 단편화는 꽤 치명적이다. 메모리 낭비를 매우 크게 발생시킨다.

 

• https://neos518.tistory.com/128
• https://comdolidol-i.tistory.com/243
• https://bellog.tistory.com/161
• https://wansook0316.github.io/cs/os/2020/04/06/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%A0%95%EB%A6%AC-16-%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC.html
• https://dar0m.tistory.com/270
• https://doh-an.tistory.com/28
• http://itnovice1.blogspot.com/2019/08/thrashing.html