가상메모리

https://inf.run/bXfg

그림으로 쉽게 배우는 운영체제 - 인프런 | 강의

본 포스팅은 위 링크의 강의를 요약/정리한 것으로, 지식의 공유보다는 개인적으로 공부하고 복습하기 위해 작성한 글입니다.

 

 

가상메모리

 

가상메모리란?

🔗당장 실행해야 하는 부분만 메모리에 넣고 나머지는 보조기억장치(스왑 영역)에 넣어 동작하도록 하는 것이다. 이렇게 함으로써 메모리보다 큰 프로세스나 운영체제를 실행할 수 있다.

🔗프로세스는 메모리 관리자를 통해 메모리에 접근하기 때문에 물리 메모리에 직접 접근할 일이 없다. 메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결해 준다.

🔗가상 메모리의 크기는 이론적으로 무한대이지만 실제로는 물리 메모리의 크기와 CPU의 bit 수로 결정된다.

• 만약 32bit CPU라면 표현할 수 있는 주소값이 2의 32승으로, 대략 4gb 이기 때문에 가상 메모리의 크기도 4gb이다.

🔗메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소로 물리 주소를 변환하는데, 이를 동적 주소 변환이라고 한다. 동적 주소 변환을 거치면 프로세스가 사용자 데이터를 물리 메모리에 배치할 수 있다.

🔗가상 메모리 시스템에서는 운영체제 영역(물리 주소 0x0 번지)을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에 할당한다.

🔗가상 메모리 시스템에는 가변 분할 방식을 이용한 세그멘테이션과 고정 분할 방식을 이용한 페이징이 있다. 세그멘테이션에서는 외부 단편화가 발생하고 페이징에서는 내부 단편화가 발생한다.

🔗따라서 이를 보완한 세그멘테이션-페이징 혼용 기법을 사용한다.

🔗가상 주소는 메모리나 스왑영역에 위치하며 메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리한다.

---

세그멘테이션(배치정책)

 

🔗세그멘테이션에서 프로그램은 함수나 모듈 등으로 세그먼트를 구성한다. 프로그램(사용자) 관점에서 메모리는 메인 코드가 있는 세그먼트, 전역 데이터가 있는 세그먼트, 힙 영역이 있는 세그먼트, 스택 영역이 있는 세그먼트가 있다.(+라이브러리)

• 세그먼트: 가상 기억 장치에 있어서 가상 어드레스(virtual address) 구조를 실현하기 위해 운영 체제에 의해서 어떤 바이트 수 단위로 분할되는 가상 기억 영역
• 각 세그먼트는 서로 인접하지 않아도 되지만 프로세스 관점에서는 인접한 것으로 본다.

 

🔗사용자와 프로세스, CPU가 사용하는 주소는 논리 주소이며, 메모리 관리자를 거쳐서 물리 주소로 변환된다.

🔗메모리 관리자는 세그먼트 테이블을 이용해 물리 메모리 주소를 계산한다

• 세그먼트 테이블: 세그먼트 번호와 시작 주소, 세그먼트의 크기를 담은 테이블. 
• 세그먼트 테이블의 시작 주소는 메모리 관리자 내의 'Segment table base register'에 저장돼 있다.

🔗과정은 다음과 같다.

• CPU에서 논리 주소를 전달하면 메모리 관리자는 해당 논리 주소가 몇 번 세그먼트인지 알아낸다.
• 세그먼트 테이블 베이스 레지스터를 이용해 물리 메모리 내의 세그멘테이션 테이블을 찾고, 세그먼트 번호 인덱스로 Base address와 Bound address(세그먼트의 크기를 나타냄)를 찾는다.
• 메모리 관리자가 전달받은 논리 주소와 바운드 어드레스의 크기를 비교한다
• 만약 논리 주소가 Bound address보다 작다면 논리 주소와 Base address를 더해 물리 주소를 구하고, 반대의 경우라면 메모리를 침범했다고 보고 에러를 발생시킨다.

🔗세그멘테이션의 장점

• 메모리를 가변적으로 분할할 수 있고 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있기 때문에 공유 및 각 영역에 대한 메모리 접근 보호가 편리하다.

🔗세그멘테이션의 단점

• 가변 분할 방식의 단점인 외부 단편화가 발생한다.

---

페이징(배치정책)

 

페이징이란?

🔗메모리 관리 기법 중 하나로, 논리 주소 공간(가상 메모리)을 모두 같은 크기의 블록으로 편성하여 운용한다. 이때 일정한 크기의 블록을 페이지(page)라고 한다.

🔗페이징은 메모리를 일정한 크기의 페이지로 나누기 때문에 관리가 쉬우며 외부 단편화 현상이 일어나지 않는다.

🔗물리 주소 공간도 페이지의 크기와 동일한 값으로 나누는데, 이를 프레임이라고 부른다.

🔗페이징의 주소 변환

• 세그멘테이션과 마찬가지로 메모리 관리자는 테이블을 갖고 있다. 이때의 테이블을 페이지 테이블이라 한다.
• CPU에서 논리 주소를 전달하면 메모리 관리자는 해당 논리 주소가 몇 번 페이지에 해당하는지, 오프셋은 얼마인지 알아낸다.
  • 오프셋: 하나의 시작 주소로부터 얼마만큼 떨어져 있는지 나타내는 값
• 그 후 메모리 관리자 내에 Page Table Base Rdgister(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고, 페이지 번호에 대항하는 인덱스를 찾아 프레임 번호를 알아낸다. 마지막으로 프레임 번호를 시작 위치로 설정하고 오프셋을 구해 더해주면 물리 주소로의 변환이 끝난다.
  • 페이지 번호: 논리 주소 / 페이지의 크기
  • 오프셋 구하는 공식: 논리 주소 % 페이지의 크기

🔗페이지 테이블에 Invaild라고 표시돼 있으면 스왑영역에 저장돼 있다는 의미이다.

🔗세그멘테이션과 마찬가지로 Page Table Base Rdgister는 운영체제가 컨텍스트 스위칭을 할 때마다 해당 프로세스의 것으로 업데이트 해준다.

🔗메모리 관리자 내의 페이지 테이블은 1차원 배열로 구성돼 있으며 페이지 번호가 곧 배열의 인덱스이다. 해당 인덱스로 가면 프레임 값을 얻을 수 있다.

🔗세그멘테이션과 페이징의 차이

• 세그멘테이션은 프로세스마다 크기가 달라서 바운드 어드레스를 가지지만 페이징에서는 필요없다.
• 페이징은 외부 단편화는 발생하지 않지만 내부 단편화는 발생한다. 그러나 세그멘테이션에서 발생하는 외부 단편화에 비하면 낭비되는 공간이 적으며, 외부 단편화를 해결하는 게 더 어렵다.
• 세그멘테이션은 세그먼트마다 크기를 다르게 나눌 수 있으니 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다. 반면 페이징에서는 나누는 크기가 동일하기 때문에 특정 영역만 떼어내서 공유하거나 권한을 부여할 수 없다.

🔗페이징에서는 페이지 테이블의 크기를 신경 써야 한다. 각 프로세스마다 페이지 테이블을 갖고 있으므로 프로세스가 많아질수록 페이지 테이블이 많아진다. 페이지 테이블이 많아질수록 실제로 사용할 수 있는 메모리 영역은 줄어든다. 또한 메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장돼 있기 때문에 페이지 테이블의 크기가 너무 크면 사용자 영역이 부족해진다.

---

페이지드 세그멘테이션(배치정책)

 

메모리 접근 권한

🔗메모리의 특정 번지에 부여된 권한으로, 읽기, 쓰기, 실행 세 가지가 있다.

🔗프로세스는 각 영역마다 접근 권한이 있다.

• 코드 영역은 수정되면 안 되기 때문에 읽기와 실행 권한만 있다.
• 데이터 영역은 읽기 권한이 있으며 쓰기 권한은 있을 수도 있고 없을 수도 있다.
• 스택과 힙 영역은 읽기와 쓰기 권한이 있다.

🔗가상 주소에서 물리 주소로 변환될 때마다 메모리 접근 권한을 검사하며, 만약 권한을 위반한다면 에러를 발생시키고 프로세스를 종료한다.

페이지드 세그멘테이션

🔗세그멘테이션과 페이징을 혼합해 장점을 취한 방식이다.

🔗페이지드 세그멘테이션 기법에서는 세그먼트 테이블에 권한 비트를 추가한다. base address는 페이지 번호로 바뀌고 bound address는 해당 세그먼트의 페이지 개수로 바뀐다. 각각의 역할은 이름만 달라졌을 뿐 본질적으로는 같다.

🔗주소 변환 과정은 다음과 같다.

• 변환하려는 가상 주소의 세그먼트가 몇 번인지 알아낸다.
• 세그먼트 테이블을 참조해서 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다.
  • 접근 권한을 위반했으면 프로세스를 종료하고 위반하지 않았으면 페이지 번호와 페이지 개수를 가져온다.
• 페이지 테이블에 접근해서 페이지 번호에 해당하는 프레임 번호를 가져온다.
• 물리 메모리 내의 해당 프레임 위치에 페이지 개수를 더해 물리 주소를 구한다.
• 만약 물리 메모리에 해당 프레임이 없다면 스왑 영역에서 물리 메모리로 가져온다.

🔗페이지드 세그멘테이션의 다넞ㅁ은 물리 주소에 접근하려면 메모리에 두 번 접근해야 한다는 것이다.(세그멘테이션 테이블을 참조할 때, 페이지 테이블을 참조할 때)

🔗이런 단점 때문에 현대 운영체제는 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용한다.

---

디맨드 페이징(가져오기 정책)

 

지역성의 원리

🔗CPU가 자주 참조하는 주소가 특정 지역에 몰리는 현상을 말한다.(90대 10의 법칙: 프로그램이 실행되는 시간의 90퍼센트가 10퍼센트의 코드에 머무는 것.)

🔗지역성 이론은 두 가지로 나뉜다.

• 공간의 지역성: 현재 위치와 가까운 데이터에 접근할 확률이 높다.
• 시간의 지역성: 최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높다.

디맨드 페이징

🔗지역성 원리를 이용해 조만간 쓰일 데이터만 메모리에 올리고 나머지는 스왑 영역으로 보내 성능을 높이는 정책. 스왑 영역은 보조저장장치에 있기 때문에 속도가 느리며, 성능 향상을 위해 스왑 영역으로 데이터를 보내는 걸 최소화해야 한다.

• 스왑 영역에서 물리 메모리로 데이터를 가져오는 것을 스왑 인이라고 하고 반대의 경우를 스왑 아웃이라고 한다.

🔗가상 주소가 주어지면 메모리 관리자는 페이지 테이블을 참조해서 물리 메모리가 있는 프레임을 알아내거나 스왑 영역의 위치를 알아내야 한다.

• 이는 페이지 테이블의 여러 가지 비트를 이용해서 알아낼 수 있다.

🔗페이지 테이블을 이루는 한 행을 페이지 테이블 엔트리라고 부른다. 페이지 테이블 엔트리는 접근비트, 변경비트, 유효비트, 읽기/쓰기/실행비트, 프레임 등으로 구성되어 있다.

• 접근 비트: 페이지가 메모리에 올라온 후 데이터의 접근이 있었는지 알려준다.
• 변경 비트: 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려준다.
• 유효 비트: 페이지가 물리 메모리에 있는지 알려준다.
• 읽기/쓰기/실행 비트: 권한 비트로, 해당 메모리에 접근 권한이 있는지 검사한다.

🔗프로세스가 가상 메모리에 접근 요청을 할 때 일어나는 일

• 메모리 관리자가 페이지 테이블을 보고 물리 메모리에서 프레임을 찾는다. 만약 물리 메모리에 없다면 page fault라는 인터럽트를 발생시킨다.
• page fault가 발생하면 보조 저장 장치의 스왑 영역에 접근하게 되고 해당 프로세스는 대기 상태가 된다.
• 그 후 스왑 영역에 있는 데이터가 메모리로 올라가면 대기 상태의 프로세스가 다시 실행된다.

🔗가상 메모리 주소가 참조되는 경우는 세 가지로 나눌 수 있다.

• 데이터가 물리 메모리에 있는 경우
• 물리 메모리에 여유 공간이 있으면서 데이터가 스왑 영역에 있는 경우
• 물리 메모리에 여유 공간이 없으면서 데이터가 스왑 영역에 있는 경우
  • 이 경우 현재 물리 메모리에서 필요 없다고 판단되는 영역을 스왑 영역으로 옮긴다. 그 후 페이지 테이블에서 옮긴 영역의 항목을 수정한다. 이후 처음 옮기려고 했던 데이터를 물리 영역으로 옮기고, 페이지 테이블에서 해당 데이터와 관련된 항목을 수정한다.

---

페이지 교체 정책

 

페이지 교체 정책

🔗메모리가 꽉 찼을 때 어떤 페이지를 스왑 영역으로 보낼지 결정하는 정책이다.

🔗페이지 교체 정책은 여려 가지가 있다.

• 무작위 선택: 지역성을 고려하지 않기 때문에 자주 사용되는 페이지가 선택될 때가 있다. 따라서 성능이 안 좋으며 거의 쓰이지 않는다.
• 메모리에 들어온 지 가장 오래된 페이지를 선택(FIFO): 마찬가지로 자주 쓰이는 페이지가 메모리에 먼저 들어왔다는 이유로 교체될 수 있다. 그러나 구현이 간단하고 성능도 나쁘지 않아서 변형해서 많이 쓴다.
  • 이 방법의 가장 큰 단점은 빌레이디의 역설 현상(page fault를 줄이기 위해 메모리를 늘리고 프레임의 수를 늘렸는데 오히려 페이지 폴트가 더 많이 발생하는 현상)이 일어난다는 것이다.
• 향후 가장 오랫동안 쓰이지 않을 페이지를 선택하는 방법(Optimum): 구현이 불가능한 이론적인 선택 방법이다. 따라서 다른 알고리즘과 성능 비교를 할 때 참조용으로 쓰인다.
• 최근에 가장 적게 사용된 페이지를 선택하는 방법(Least recently used, Lru): 최근 사용된 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 최근에 가장 적게 사용한 페이지가 앞으로도 적게 사용될 거라는 점(시간의 지역성)을 이용한 방법이다. Optimum 알고리즘의 성능에 근접한 성능을 보인다. 다만 프로그램이 지역성을 보이지 않을 때 성능이 떨어진다.
  
  • Lru의 단점: 시간을 기록하려면 페이지 테이블 엔트리에 시간을 기록하는 bit를 추가해야 하는데, 여기에는 bit가 많이 필요하다. 따라서 성능이 낭비될 수 있으며 또한 시간이 많이 지날 경우 오버플로우가 발생하게 된다.(오버플로우로 값이 초기화되면서 시간을 올바르게 표현할 수 없게 됨.)
  • 이런 점 때문에 실제로 Lru를 구현할 때는 접근 비트를 이용해서 Lru와 유사한 알고리즘을 구상했는데, 바로 클락 알고리즘(Clock algorithm)이다.

🔗클락 알고리즘은 일정 시간마다 모든 페이지의 접근 비트를 0으로 초기화해 그 일정 시간 동안 페이지가 참조되었는지 확인하는 알고리즘이다. 방식은 다음과 같다.

• 접근 비트의 초기값은 0이며 만약 페이지가 참조되었다면 1로 설정한다.
• Clock 알고리즘에서 각 페이지는 클락 핸드라고 불리는 포인터에 의해 원형으로 연결된다.
• page fault가 발생해서 페이지를 스왑 영역으로 보내야 하면 클락 핸드는 현재 참조하는 페이지의 접근 비트를 확인한다.
• 만약 접근 비트가 1이라면 해당 접근 비트를 0으로 바꾸고 다음 페이지를 확인한다.
• 이렇게 반복하다가 접근 비트가 0인 페이지를 발견하면 해당 페이지를 스왑 영역으로 보낸다.

🔗클락 알고리즘을 수정해 변경 비트까지 확인하는 알고리즘이 있는데, 이를 향상된 클락 알고리즘(Enhanced clock algorithm)이라고 한다. 향상된 클락 알고리즘에서는 접근 비트와 변경 비트를 이용해 스왑 영역으로 보낼 페이지의 우선 순위를 매긴다. 가장 순위가 높은 것은 접근 비트와 변경 비트 모두 0인 페이지고, 그 다음은 접근 비트가 0, 변경 비트가 1인 페이지, 그 다음은 접근 비트가 1, 변경 비트가 0인 페이지, 마지막은 둘 다 1인 페이지이다.

🔗Lru 대신 FIFO를 사용하는 경우

• Lru에서는 접근 비트를 이용하는데, 만약 접근 비트를 쓸 수 없는 하드웨어라면 FIFO를 사용할 수밖에 없다. 따라서 이를 대비해 FIFO의 성능을 높이는 알고리즘도 고안되었다. 바로 2차 기회 페이지 교체 알고리즘이다. 이는 FIFO 방식에서 자주 사용되는 페이지에 한 번 더 기회를 주는 것으로, FIFO 방식과 돌일하게 동작하지만 만약 Page fault 없이 페이지에 접근하는 데 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장하는 방식이다. 성능은 Lru보다는 안 좋고 FIFO보다는 좋다.

---

스레싱과 워킹셋

 

스레싱

🔗CPU 사용률을 높이기 위해 메모리에 올리는 프로세스의 수를 늘를수록 스왑영역에 저장되는 프레임이 많아진다. 그러면 CPU가 스왑 작업에 더 많은 시간을 사용하게 되고 CPU의 사용률은 떨어진다. CPU의 사용률이 떨어지면 CPU 스케줄러는 더 많은 프로세스를 메모리에 올리고, 이를 반복하다 보면 CPU 사용률은 0에 수렴하게 된다. CPU 사용률을 높이려 했지만 오히려 CPU 사용률이 떨어진 것이다. 이러한 현상을 스레싱이라고 한다.

🔗스레싱의 근본적인 원인은 물리 메모리의 크기 부족이다. 이를 하드웨어적으로 해결하려면 메모리 크기를 늘리면 된다.

🔗소프트위어적으로 해결하는 방법도 있다. 바로 page fault가 발생할 경우 더 많은 페이지를 할당하는 것이다. 반대로 page fault가 너무 적게 발생하면 메모리가 낭비되는 것이라 판단하고 페이지를 회수한다. 이렇게 하면 프로세스가 실행되는 동안 해당 프로세스에 적합한 페이지 수를 할당하게 된다.

• 적정 페이지 수를 정했다면 어떤 페이지를 유지할지 선택해야 한다. 프로세스는 일정 시간 동안 특정 페이지를 집중적으로 참조하는 경향이 있으므로(지역성 원리) 집중 참조 페이지들을을 하나로 묶어서 메모리에 올린다. 이를 워킹셋이라고 한다. 워킹셋은 컨텍스트 스위칭을 할 때 쓰인다.