728x90
24.09.10 CSAPP
CSAPP
9. 가상메모리
- 한 시스템의 프로세스들은 CPU와 메인메모리를 다른 프로세스들과 공유한다.
- 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리 VM이라고 알려진 메인메모리의 추상화를 제공한다. 가상메모리는 각 프로세스에 하나의 크고 통합된 사적 주소공간을 제공한다. 이것은 하드웨어 예외, 하드웨어 주소번역, 메인메모리, 디스크파일, 커널 소프트웨어들 사이의 상호작용이다. 가상메모리는 한 개의 깔끔한 매커니즘을 사용해 세 주요 기능을 제공한다.
- 메인메모리를 디스크에 저장 된 주소공간에 대한 캐시로 취급해서 메인메모리내 활성화 영역만 유지하고, 데이터를 디스크와 메모리간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.
- 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
- 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.
가상메모리를 프로그래머가 이해해야 하는 이유
- 가상메모리가 중심이다. 가상메모리는 모든 컴퓨터 수준에 스며들어 있으며, 하드웨어 예외, 어셈블러, 링커, 로더, 공유객체 파일, 프로세스를 설계하는데 중요한 역할을 한다. 가상메모리를 이해하면 어떻게 시스템이 일반적으로 동작하는지 이해하는데 도움이 된다.
- 가상메모리는 강력하다. 가상메모리는 응용에 메모리 블록을 생성하고 없애고, 메모리 블록을 디스크 파일로 매핑하고, 메모리를 다른 프로세스들과 공유할 수 있는 강력한 기능을 준다. 가상메모리를 이해하면 가상메모리의 강력한 성능을 여러분의 응용 프로그램에 적용하는데 도움이 될 것이다.
- 가상메모리는 위험하다. 응용 프로그램은 이들이 변수를 참조하고, 포인터를 역참조하고, malloc같은 동적할당 패키지로 호출할 때 마다 가상메모리와 상호작용한다. 만일 가상메모리가 잘못 사용되면, 응용 프로그램은 당혹스럽고 퍼져나가는 메모리 관련 버그로 부터 괴로움을 당할 수 있다. 가상메모리와 이를 관리하는 malloc같은 할당 패키지를 이해하면 이러한 에러를 피하는데 도움이 된다.
9.1 물리 및 가상주소의 방식
- 컴퓨터 시스템의 메인메모리는 m개의 연속적인 바이트 크기 셀의 배열로 구성된다. 각 바이트 고유의 물리적인 주소를(PA) 가진다. 첫 번째 바이트 주소는 0, 다음 바이트 주소1, 다음 바이트는 2 이런식으로 진행된다.
- 이와 같은 주소가 주어졌을 때, CPU가 메모리에 접근하는 가장 자연스러운 방식은 물리주소를 사용하는 것이다. 이러한 접근법을 물리주소 방식이라고 부른다. CPU가 로드 인스트럭션을 실행할 때 유효 물리주소를 생성하고, 이것을 메모리 버스를 거쳐서 메인메모리에 전달한다. 메인 메모리는 물리주소에서 시작하는 바이트 워드를 선입하고 이것을 CPU에 돌려주고, 다시 이것을 레지스터에 저장한다.
- 초기 PC들은 물리주소 방식을 사용 하였으며 디지털 신호처리 프로세서, 임베디드 마이크로 컨트롤러, Cray 슈퍼 컴퓨터 같은 시스템은 이 방식을 계속해서 사용하고 있다. 그렇지만 현대의 프로세스들은 가상주소 방식이라는 주소 형태를 사용한다.
- CPU는 가상주소 지정으로 가상주소(VA)를 생성해서 메인 메모리에 접근하며, 이것은 메모리로 보내지기 전에 적절한 물리주소로 변환된다. 가상주소를 물리주소로 변환하는 작업은 주소번역이라고 알려져있다. 예외 처리처럼 주소번역은 CPU하드웨어와 운영체제간에 긴밀한 협력을 필요로 한다. CPU칩 내에 메모리 관리 유닛(MMU)이라고 부르는 전용 하드웨어는 메인메모리에 저장된 참조 테이블을 사용해서 실행중에 가상주소를 번역하며, 이 테이블의 내용은 운영체제가 관리한다.
9.2 주소공간
- 주소공간은 비음수 정수 구조의 정렬된 집합이다.
- { 0, 1, 2, … }
- 만일 주소공간의 정수가 연속적이라면, 이 공간은 선형 주소공간이라고 한다. 우리는 논의를 간단히 하기 위해서 언제나 선형 주소공간을 가정하겠다. 가상메모리를 갖는 시스템에서 CPU는 가상주소 공간이라고 불리는 N=2^N 주소의 주소공간에서 가상의 주소를 생성한다.
- { 0, 1, 2, …, N-1}
- 주소공간의 크기는 가장 큰 주소를 표시하는데 필요한 비트수로 나타낸다. 예를 들어 N=2^N을 주소로 갖는 가상주소 공간은 N-비트 주소공간 이라고 부른다. 현대 시스템은 전형적으로 32비트 또는 64비트 가상 주소공간을 지원한다.
- 또한 컴퓨터 시스템은 이 시스템내의 M바이트의 물리메모리로 대응되는 물리 주소공간을 갖는다.
- { 0, 1, 2, … , M-1 }
- M은 2의 제곱일 필요는 없지만, 논의를 단순하게 하기 위해서 M = 2^M이라고 가정할 것이다.
- 주소공간의 개념은 중요한데, 그것은 이 개념이 데이터 객체와 그들의 특성(주소들)들 간에 명확한 구별을 해주기 때문이다. 이 구별을 인지하면 일반화 할 수 있으며, 각 데이터 객체가 다중 독립주소를 가질 수 있도록 하고, 이 각각의 주소는 서로 다른 주소공간에서 선택되었다. 이것은 가상메모리의 기본 아이디어다. 메인메모리의 각 바이트는 가상주소공간으로 부터 선택된 가상주소를 가진다.
9.3 캐싱도구로서의 VM
- 결과적으로, 가상메모리는 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다. 각 바이트는 특정한 가상주소를 가지며, 배열의 인덱스로 작용한다. 디스크 안의 배열 정보는 메인메모리에 캐시된다. 메모리 계층구조 안에 있는 캐시는 블록단위로 분할이 되며, 디스크와 메인메모리 사이에 징검다리 역할을 한다. VMsystem은 가상메모리를 규정된 사이즈 블록 단위로 분할하여 관리한다. 분할된 블록들은 가상페이지라 부른다. 각 가상페이지는 P=2P 바이트의 크기를 갖는다. 이와 비슷하게 물리메모리도 물리페이지로 분할되어 사용된다. 또한 P바이트의 크기를 갖는다(물리페이지는 물리프레임 이라고도 불린다)
- 시간 상의 어느 시점에서도 가상 페이지의 집합은 세 개의 중첩되지 않는 부분 집합으로 나누어진다.
- unallocated : VM시스템에 의해 아직까지 할당되지 않은 페이지들, 비할당된 블록들은 이들과 관련된 데이터를 하나도 가리고 있지 않으며, 따라서 디스크상에 어떤 공간도 차지하지 않는다.
- cached : 현재 물리메모리에 캐시되어 할당된 페이지들
- uncached : 물리메모리에 캐시되지 않은 할당된 페이지들
9.3.1 DRAM 캐시의 구성
- 메모리 계층 구조 내에서 DRAM 캐시의 위치는 이들이 구성된 방식에 큰 영향을 가진다. DRAM이 최소한 SRAM보다 10배는 더 느리고, 디스크는 DRAM보다 100,000배 더 느리다는 점을 상기해야 한다. 따라서 DRAM 캐시미스는 SRAM 캐시에서의 미스에 비교하면 값이 매우 비싸며, 그 이유는 DRAM 캐시 미스는 디스크에서 처리되지만 SRAM 캐시미스는 대개 DRAM 기반 메인메모리로 부터 지원 받기 때문이다. 더 나아가, 디스크 섹터로 부터 첫 번째 바이트를 읽는 비용은 섹터에서 연속적인 바이트를 읽는 것보다 약 100,000배 더 느리다. 최소한 DRAM 캐시의 조직이 전적으로 엄청난 미스비용으로 진행되었다. 최소한 DRAM 캐시의 구성은 전적으로 엄청난 규모의 미스비용으로 영향받는다.
- 캐시히트 : CPU에서 요청한 데이터가 캐시에 존재하는 경우
- 캐시미스 : CPU에서 요청한 데이터가 캐시에 존재하지 않는 경우
- 섹터 : 디스크의 저장공간을 나누는 단위 중 최소단위
- 큰 규모의 미스 비용과 첫 번째 바이트를 접근하는데 드는 비용 때문에 가상페이지는 커지고 있으며, 대개 4KB에서 2MB까지 값을 가진다. DRAM 캐시는 완전결합성이다. 즉, 모든 가상페이지는 물리페이지에 둘 수 있다. 미스 발생시 교체 정책은 더 큰 중요성을 가정하는데, 그것을 잘못된 가상페이지를 교체하는 것과 관련된 비용이 매우 높기 때문이다. 그래서 운영체제는 하드웨어가 SRAM 캐시에 대해서 처리하는 것보다 훨씬 더 복잡한 DRAM 캐시를 위한 교체 알고리즘을 사용한다. 마지막으로 디스크의 큰 접근 시간 때문에 DRAM은 항상 write-through 대신에 write - back을 사용한다.
9.3.2 페이지테이블
- 모든 캐시에서 처럼 VM 시스템은 가상페이지가 DRAM 어딘가에 캐시되었는지 결정하기 위한 방법을 가지고 있어야한다. 그렇다면, 이 시스템은 어떤 물리페이지를 캐싱했는지 결정해야 한다. 만일 미스가 존재한다면 시스템은 디스크 어디에 가상페이지가 저장되어 있는지 결정해야 하며, 물리메모리중에서 희생자 페이지를 선택해야 하고, 가상페이지를 디스크에서 DRAM으로 복사해서 희생자페이지를 교체한다.
- 이러한 역량은 운영체제 소프트웨어와 MMU내의 주소 번역 하드웨어, 가상페이지를 물리페이지로 매핑하는 페이지테이블이라고 알려진 물리메모리에 저장된 자료구조의 조합으로 제공된다. 주소 번역 하드웨어는 이들이 가상주소를 물리주소로 변환할 때마다 페이지 테이블을 읽는다. 운영체제는 페이지 테이블의 콘텐츠 관리와 페이지들을 디스크와 DRAM 사이에서 왔다 갔다 하는 것을 관장한다.
- 페이지테이블의 기본구조이다. 페이지테이블은 페이지테이블엔트리(PTE)의 배열이다. 가상주소 공간의 각 페이지는 페이지테이블 내에 고정된 오프셋 위치에 PTE를 갖는다. 편의상 PTE가 한개의 유효비트, n개의 주소필드로 구성된다고 가정하겠다. 유효비트는 가상페이지가 현재 DRAM에 캐시되어 있는지를 나타낸다. 만일 유효비트가 세팅 되었다면, 주소필드는 가상페이지가 캐시되어 대응되는 DRAM의 물리페이지의 시작을 나타낸다. 만일 유효비트가 세팅되어있지 않다면, NULL 주소는 가상페이지가 아직 할당되지 않았음을 나타낸다. 그렇지 않은 경우에 주소는 디스크 상의 가상페이지의 시작 부분을 가리킨다.
- DRAM 캐시가 완전결합성(Fully associative)이므로 물리페이지가 모든 가상페이지를 포함할 수 있다.
9.3.3 페이지 적중
- CPU가 DRAM에 캐시되어 있는 가상메모리의 워드를 한 개 읽을 때, 주소번역 하드웨어는 PTE2를 찾기 위해서 인덱스로 가상주소를 사용하고, 이것을 메모리에서 읽는다. 유효비트가 세팅되어 있기 때문에 주소번역 하드웨어는 VP2가 메모리에 캐시되어 있다는 것을 알고 있다. 그래서 PTE내의 물리메모리 주소를 사용해서 해당 워드의 물리주소를 구성한다.
9.3.4 페이지 오류
- 가상 메모리 용어에서 DRAM 캐시미스는 페이지오류(Page Fault) 라고 알려져 있다.
CPU는 DRAM에 캐시되어 있지 않은 VP3내의 워드를 참조했다. 주소번역 하드웨어는 메모리에서 PTE3를 읽으며, VP3가 캐시되어 있지 않다는 것을 유효비트로 부터 유추해서 페이지 오류 예외를 유발 시킨다.
- 페이지 오류 예외는 커널 내에 페이지 오류 예외 핸들러를 호출해서 희생자페이지인 PP3에 저장된 VP4를 선택한다. VP4가 변경되었다면 커널을 다시 디스크에 복사한다. 어떤 경우든지 커널은 VP4에 대한 페이지 테이블 엔트리를 수정해서 VP4가 더 이상 메인메모리에 캐시 되지 않았다는 사실을 반영한다. 다음으로, 커널은 VP3를 디스크에서 메모리 내의 PP3로 복사하고, PTE3를 갱신하고 그 후에 리턴한다. 핸들러가 리턴할 때 오류 인스트럭션을 재시작하고, 이것은 오류 가상주소를 주소번역 하드웨어로 재 전송한다. 그러나 이번에는 VP3가 메인메모리에 캐시되어 있으며, 페이지 적중은 정상적으로 주소번역 하드웨어에 의해서 처리된다.
- 가상메모리 용어에서 블록은 페이지라고 알려져 있다. 디스크와 메모리 사이에 페이지를 전송하는 동작은 스와핑 또는 페이징이라고 알려져있다. 페이지들을 디스크에서 DRAM으로 스와핑해 들어오며, DRAM에서 디스크로 스와핑 되어 나간다. 미스가 발생할 때, 하나의 페이지로 스와핑되어 들어오는 마지막 순간까지 기다리는 전략은 요구페이징(Demand Paging)이라고 알려져있다.
9.3.5 페이지의 할당
- 운영체제가 가상메모리의 새로운 페이지를 할당할 때 디스크 상에 공간을 만들고, 디스크에 새롭게 만든 페이지를 가리키도록 한다.
9.3.6 문제 해결을 위한 또 한 번의 지역성 등장
- 프로그램이 전체 실행하는 동안 참조하는 서로 다른 페이지의 수가 전체 물리 메모리의 크기보다 더 클지라도 지역성의 원리는 시간상의 어느 시점에서라도 이들이 동작집합(Working set)또는 거주집합(Resident set)이라고 알려진 보다 작은 활성화된 페이지 집합에서 동작하는 경향을 보일것이라는 점을 약속한다.
- 우리의 프로그램이 좋은 시간 지역성을 가지고 있으면, 가상메모리 시스템은 상당히 잘 동작한다. 하지만 만일 동작집합 크기가 물리메모리 보다 더 크면, 프로그램은 쓰레싱(thrashing)이라고 알려진 불행한 상황을 만들 수 있는데, 이 경우 페이지들이 연속적으로 스왑해서 들어오고 나가기를 반복한다.
9.4 메모리 관리를 위한 도구로서의 VM
- 다수의 가상페이지들이 동일한 공유된 물리페이지에 매핑 될 수 있다.
- 요구페이징과 분리된 가상 주소공간의 조합은 메모리가 시스템에서 사용되고 관리되는 방식에 주요한 영향을 미친다. 특히 VM은 링킹과정, 로딩, 코드와 데이터의 공유, 응용으로의 메모리 할당을 단순화 해준다.
- 링킹을 단순화 한다. 별도의 주소공간은 각 프로세스들이 각 메모리 이미지에 대해서 코드와 데이터가 실제로 물리메모리내 어디에 위치하는지에 상관없이 동일한 기본 포맷을 사용하도록 해준다. 64비트 주소공간에 대해서 코드 세그먼트는 항상 가상주소0X400000에서 시작한다. 데이터 세그먼트는 일정거리를 띄어두고 코드 세그먼트 다음에 위치한다. 스택은 유저 프로세스 주소공간의 최상위 부분을 차지하며 아래로 자란다. 이러한 통일성은 링커의 설계와 구현을 매우 단순화 해주며 물리메모리 상에서 궁극적인 코드와 데이터의 위치에 독립적인 완전한 링크된 실행 가능 파일을 만들 수 있게 해준다.
- 로딩을 단순화 해준다. 가상메모리는 또한 실행파일과 공유목적 파일들을 메모리에 로드하기 쉽게 해준다. 목적파일의 .data와 .text섹션들을 새롭게 생성된 프로세스에 로드하기 위해서 리눅스로 하는 코드와 데이터 세그먼트를 위한 가상의 페이지를 할당하고, 이들을 무효로 표시하고(즉, 캐시되지 않은 상태), 이들의 페이지테이블 엔트리를 목적파일의 해당 위치를 가리키게 한다. 흥미로운 점은 로더가 실제로 디스크로부터 메모리로 데이터를 전혀 복사하지 않았다는 것이다. 각 페이지가 최초로 참조 될 때, CPU가 인스트럭션을 선입하거나 메모리위치를 참조하는 인스트럭션을 실행할 때, 데이터는 요청에 의해 자동으로 페이지화 된다. 이와같은 가상페이지를 이므이의 파일내의 임의의 위치로 매핑하는 개념은 메모리 매핑이라고 알려져있다.
- 공유를 단순화 해준다. 별도의 주소공간은 운영체제에 사용자 프로세스와 운영체제 자신 사이에 공유를 관리하는 일정한 매커니즘을 제공한다. 일반적으로 각 프로세스는 다른 프로세스와 공유되지 않은 자신만의 사적인 코드, 데이터, 힙, 스택 영역을 가진다. 이 경우에 운영체제는 다응되는 가상페이지를 중첩되지 않는 물리페이지로 매핑하는 페이지 테이블을 만든다.
- 그렇지만 일부 경우 프로세스들이 코드와 데이터를 공유하는 것이 바람직 할 때가 있다. 예를 들어, 모든 프로세스는 동일한 운영체제 커널 코드를 호출해야 하며 모든 C프로그램은 표준 C라이브러리 루틴을 호출한다. 커널과 표준 C라이브러리 코드를 각 프로세스에서 별도로 포함시키기 보다 운영체제는 다수의 프로세스가 서로 다른 프로세스에 들어있는 가상 페이지들을 동일한 물리 페이지들로 적절히 매핑해서 이 코드들이 한 개의 사본을 공유할 수 있게 한다.
- 메모리 할당을 단순화 해준다. 가상메모리는 추가적인 메모리를 사용자 프로세스에 할당하기 위한 간단한 매커니즘을 제공한다. 사용자 프로세스로 돌고있는 프로그램이 추가적인 힙공간을 요청할 때 운영체제는 적당한 수의, 연속적인 가상페이지를 할당하고, 이들을 물리메모리 내에 위치한 임의의 물리페이지로 매핑한다. 운영체제는 페이지 테이블이 동작하는 방식 때문에 물리메모리에서 연속적인 페이지를 찾을 필요가 없다. 페이지들은 물리 메모리내 랜덤하게 흩어져있다.
9.5 메모리 보호를 위한 도구로서의 VM
- 모든 현대 컴퓨터 시스템은 운영체제가 메모리 시스템에 접근하는 것을 제어할 수 있는 수단을 제공한다. 사용자 프로세스는 자신의 읽기 - 허용 코드 섹션을 수정하도록 허용되지 않아야 한다. 또한 커널내의 코드와 데이터 구조들도 읽거나 수정할 수 없어야 한다. 모든 관련 프로세스들이 명시적으로 허용하지 않았다면(명시적인 프로세스 간 통신 시스템 콜을 호출해서) 다른 프로세스의 사적메모리를 읽거나 쓸 수 없어야한다.
- 별도의 가상주소 공간을 제공하면 사적메모리를 다른 프로세서로부터 분리하는 것이 쉬워진다. 그러나 주소 번역 매커니즘은 보다 섬세한 접근 제어를 제공하기 위한 자연스러운 방법으로 확장될 수 있다.
- CPU가 주소를 만들 때 마다 PTE를 읽기 때문에 PTE에 허가비트를 추가해서 주소번역 하드웨어가 가상페이지 내용으로의 접근을 제어하는것은 간단하다.
- 프로세스는 SUP0인 페이지만 접근 허용, READ,WRITE는 이 페이지에 대한 읽기와 쓰기 접근을 제어한다.
- 만일 어떤 인스트럭션이 이 허가사항을 위반한다면, CPU는 일반 보호 오류를 발생시켜서 SIGSEGV 시그널을 위반한 프로세스로 보내서 커널내의 예외 핸들러로 제어를 이동시킨다. 리눅스 쉘은 이와 같은 예외를 ‘세그먼트 오류(Segmentation Fault)’라고 본다.
- 한 시스템의 프로세스들은 CPU와 메인메모리를 다른 프로세스들과 공유한다.
- 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리 VM이라고 알려진 메인메모리의 추상화를 제공한다. 가상메모리는 각 프로세스에 하나의 크고 통합된 사적 주소공간을 제공한다. 이것은 하드웨어 예외, 하드웨어 주소번역, 메인메모리, 디스크파일, 커널 소프트웨어들 사이의 상호작용이다. 가상메모리는 한 개의 깔끔한 매커니즘을 사용해 세 주요 기능을 제공한다.
- 메인메모리를 디스크에 저장 된 주소공간에 대한 캐시로 취급해서 메인메모리내 활성화 영역만 유지하고, 데이터를 디스크와 메모리간에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.
- 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
- 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.
코테
1966 프린터 큐
#include <bits/stdc++.h>
using namespace std;
int main()
{
int testn;
int n, m;
int importance;
int count;
scanf("%d", &testn);
for (int i = 0; i < testn; i++) {
count = 0;
scanf("%d %d", &n, &m);
priority_queue<int> pq; // 내림차순 정렬해야 pop할 때 높은게 빠져나옴.
queue<pair<int, int>> q;
for (int j = 0; j < n; j++) {
scanf("%d", &importance);
q.push({ j, importance });
pq.push(importance);
}
while (!q.empty()) {
// 위치값과, 우선순위 값을 가져온 뒤 pop수행
int location = q.front().first;
int value = q.front().second;
q.pop();
// 값 비교
if (pq.top() == value) {
pq.pop();
++count;
if (m == location) {
printf("%d\\n", count);
break;
}
}
else q.push({ location, value });
}
}
return 0;
}
어렵다.. 어려워어엉
728x90