24.03.16 운영체제, PintOS

운영체제

19. 완전한 가상 메모리 시스템

19.1 VAX/VMS 가상 메모리

• VMS는 컴퓨터의 구조적 결함을 소프트웨어로 보완한 훌륭한 사례다. 운영체제가 이상적인 개념과 환상을 제공하기 위해 하드웨어에 의존하지만, 하드웨어가 모든것을 해내지 못할 경우도 있다. 하드웨어 결함에도 불구하고 시스템이 효과적으로 작동하기 위해서 VMS 운영체제가 무엇을 하였는지 볼 것이다.

메모리 관리 하드웨어

• VAX-11은 프로세스마다 512바이트 페이지 단위로 나누어진 32비트 가상주소 공간을 제공한다. 가상주소는 23비트 VPN과 9비트 오프셋으로 구성되어있다 VPN의 상위 두 비트는 페이지가 속한 세그멘트를 나타내기 위해서 사용되었다. 이 시스템은 하이브리드 구조를 갖고 있다.
• 주소공간의 하위 절반은 ‘프로세스 공간’으로 알려져 있으며 각 프로세스마다 다르게 할당된다. 프로세스 공간의 첫 번째 절반에 사용자 프로그램과 힙이 존재한다. 힙은 주소가 큰 쪽으로 증가한다. 프로세스 공간의 두 번째, 즉 큰쪽 절반은 주소가 작은 방향으로 증가하는 스택이 존재한다. 주소공간의 상위 절반은 그 중 반만 사용되면 시스템 공간(S)으로 불린다. 운영체제의 보호된 코드와 데이터가 이곳에 존재하며, 이 방식으로 여러 프로세스가 운영체제를 공유한다.
• VMS 설계자들의 첫 목표는 VMS가 페이지 테이블 저장을 위해 메모리를 소진하는것을 막는것이었다.
• 이 시스템은 페이지 테이블로 인한 메모리 압박의 정도를 경감시키기 위한 두 가지 방법을 사용했다.
  • 첫째, VAX-11은 사용자 주소공간을 두 개의 세그멘트로 나누어 프로세스마다 각 영역을 위한 페이지 테이블을 가지도록 했다. 스택과 힙 사이의 사용되지 않는 주소 영역을 위한 페이지 테이블 공간이 필요없게 되었다.
  • 둘째로, 운영체제는 사용자 페이지 테이블들을 커널의 가상 메모리에 배치하여 메모리 압박을 더 줄일 수 있었다. 페이지 테이블을 할당하거나 크기를 키울 때 커널은 자신의 가상 메모리, 세그멘트 S에 공간을 할당한다. 메모리가 고갈되면, 커널은 페이지 테이블의 페이지를 디스크로 스왑하여 물리 메모리를 다른 용도로 사용할 수 있게 한다.
• 커널 가상 메모리에 페이지 테이블을 넣으면 주소 변환 과정이 훨씬 더 복잡해진다.

실제 주소 공간

• 코드 세그멘트는 절대로 페이지 0에서 시작하지 않는다. 대신 이 페이지는 접근 불가능 페이지로 마킹되어 있으며 널-포인터(NULL-Pointer) 접근을 검출할 수 있게한다. 주소 공간 설계시 한 가지 고려해야 할 사항은 효과적인 디버깅 지원 여부이다. 접근 불가능한 페이지 0은 그런 자원의 한 형태이다. 조금 더 중요한 사실은 커널의 가상 주소공간이 사용자 주소공간의 일부라는 것이다. 문맥교환이 발생하면 운영체제는 P0과 P1의 레지스터를 다음 실행될 프로세스의 페이지 테이블을 가리키도록 변경한다. 하지만, S베이스와 바운드 레지스터는 변경하지 않기 때문에 결과적으로 ‘동일한’ 커널 구조들이 각 사용자 주소 공간에 매핑된다.
• 몇 가지 이유로 커널은 여러 공간들로 매핑된다. 그러한 구조를 택하면 커널의 동작이 쉬워진다.
• 이 주소공간에 관한 마지막 이슈는 보호와 관련있다. 운영체제는 응용 프로그램이 운영체제의 데이터나 코드를 읽거나 쓰는 것을 원하지 않는다. 운영체제의 자료를 보호하기 위해서 하드웨어가 페이지별로 보호수준을 다르게 설정할 수 있어야 한다. 이를 위해 VAX는 페이지 테이블의 Protection bit에 보호수준을 지정한다. 특정 페이지를 접근하기 위해서 필요한 CPU의 권한 수준이 기록된다. 시스템 데이터와 코드는 사용자의 데이터와 코드보다 더 높은 보호 수준으로 지정된다.

페이지 교체

• VAX의 PTE는 다음과 같은 비트를 가지고 있다. 유효(vaild), 보호 필드(protection field), 변경(modify or dirty) 비트, 운영체제가 사용하기 위해 예약한 비트, 물리 페이지 위치를 저장하기 위한 물리 프레임 번호(PFN)이 있다. VMS 교체 알고리즘은 어떤 페이지가 자주 사용중인지를 하드웨어 지원 없이 판단해야 한다.
• 개발자들은 메모리 호그(Memory hog)에 대해서도 고민했다. 메모리 호그는 메모리를 너무 많이 사용하는 프로그램을 의미한다. 지금까지 우리가 살펴보았던 대부분의 정책들은 메모리를 많이 소비하는 프로세스에 대한 대비책이 없다.
• 위의 두 가지 문제를 해결하기 위해 세그멘트된 FIFO 교체 정책을 제안했다. 각 프로세스는 상주 집합 크기(RSS : resident set size)라고 불리는 메모리에 유지할 수 있는 최대 페이지 개수를 기정받는다. 즉, 페이지들은 FIFO 리스트에 보관되며 페이지 개수가 RSS보다 커지면 제일 먼저 들어왔던 페이지가 쫒겨난다.
• 순수한 FIFO의 성능은 안좋기 때문에 성능의 개선을 위해 전역 클린 - 페이지 프리 리스트(global clean-page free list)와 더티 페이지 리스트(dirty page list) 라고 하는 두 개의 second chance list를 도입했다. 이 리스트는 전역 자료 구조이다. second-chance list는 메모리에서 제거되기 전에 페이지가 보관되는 리스트이다. 프로세스 P가 자신의 RSS를 넘긴다면 자신의 FIFO에서 페이지가 제거된다. 제거된 페이지가 클린 상태라면 클린 - 페이지 리스트에, 더티 상태라면 더티 - 페이지 리스트에 추가된다.
• 다른 프로세스 Q에 빈 페이지가 필요하면 전역 클린 리스트에서 첫 번째 프리 페이지를 꺼낸다. 원래의 프로세스 P가 해당 페이지가 회수되기 전에 그 페이지에 대해 폴트를 발생시키면, P는 클린(또는 더티) 리스트에서 페이지를 가져가서 다시 사용하게 된다. 이런식으로 디스크 접근을 피한다.
• 또 다른 최적화 기법은 VMS의 작은 페이지 크기를 극복할 수 있게 하였다. 디스크는 전송단위가 클수록 성능이 좋기 때문에 클러스터링 기법을 도입했다. 클러스터링 기법을 써서 VMS는 전역 더티 리스트에 있는 페이지들을 작업 묶음을 만들어서 한 번에 디스크로 보낸다. 쓰기 횟수는 줄이고 한 번에 쓰는 양은 늘려서 성능을 향상 시키기 때문에 클러스터링은 대부분 현대 시스템에서 사용된다.

그외의 기법

• demand zeroing과 copy-on-write. 게으른(lazy) 최적화 기법이다. VMS가 사용하는 게으른 기법의 한 형태는 페이지들을 demand zeroing 하는 것이다.
• demand zeroing의 경우 페이지가 주소 공간에 추가되는 시점에는 거의 하는 일이 없다. 페이지 테이블에 접근 불가능 페이지라고 표기하고 항목을 추가한다. 프로세스가 추가된 페이지를 읽거나 쓸 때 운영체제로 트랩이 발생한다. 트랩을 처리하면서 운영체제는 demand zeroing 할 페이지 라는 것을 알게된다. 이 시점에서 운영체제는 물리페이지를 0으로 채우고 프로세스의 주소공간으로 매핑하는 등의 필요한 작업을 한다. 프로세스가 해당 페이지를 전혀 접근하지 않는다면 이 모든 작업을 피할 수 있으며, 이것이 바로 demand zeroing의 장점이다.
• VMS에서 찾아 볼 수 있는 또 다른 멋진 최적화 방법은 copy-on-write(COW)이다. 운영체제가 주소공간에서 다른 공간으로 페이지를 복사할 필요가 있을 떼, 복사를 하지 않고 해당 페이지를 대상 주소 공간으로 매핑하고 해당 페이지의 페이지 테이블 엔트리를 양쪽 주소 공간에서 읽기 전용으로 표시한다. 만약 양쪽 주소 공간이 페이지를 읽기만 한다면 더 이상의 조치는 필요 없게 되며, 운영체제는 실제로 데이터 이동 없이 빠른 복사를 할 수 있게 된다.
• 두 주소공간 중에 하나가 페이지 쓰기를 시도한다면, 운영체제로 트랩을 발생시킨다. 운영체제는 그때 해당 페이지가 COW 페이지라는 것을 파악한다. 그런 후에 새로운 페이지를 (게으르게) 할당하고 ,데이터를 채우고, 이 새로운 페이지 폴트를 일으킨 페이지의 주소공간에 매핑한다. 이제 프로세스는 독자적인 페이지의 사본을 가지게 되고 하던 일을 계속한다.
• COW는 여러가지 이유로 유용하다. 공유 라이브러리들을 여러 프로세스들의 주소 공간에 copy-on-write로 매핑하여 메모리 공간을 절약할 수 있다. copy-on-write fork()를 수행하게 되면 운영체제는 상당한 불필요한 복사를 피할 수 있으며 성능을 개선하면서 정확한 시맨틱을 유지할 수 있다.

19.2 Linux 가상 메모리 시스템

Linux 주소 공간

• Linux 가상 주소공간은 사용자 영역과 커널 부분으로 구성된다. 다른 시스템에서와 마찬가지로 문맥 교환시 현재 실행중인 주소공간의 사용자 영역이 변경된다. 커널 영역은 모든 프로세스에서 동일하다. 다른 시스템과 마찬가지로 사용자 모드에서 실행되는 프로그램은 커널 가상 페이지에 접근할 수 없다. 커널로 트랩이 발생하고 특권 모드로 전환되어야만 커널 메모리에 접근할 수 있다.
• Linux는 커널 가상 주소의 유형이 두 개다
  • 첫 번째는 커널 논리 주소(kernel logical addresses)로 알려져 있다. 이것은 여러분이 일반적으로 생각하는 커널의 가상 주소 공간이다. 이 유형의 메모리가 더 필요한 경우, 커널 코드는 kmalloc을 호출 하기만 하면 된다. 페이지 테이블, 프로세스 별 커널 스택등과 같이 대부분의 커널 데이터 구조가 이 공간에 존재한다. 시스템의 다른 대부분의 메모리와 달리 커널 논리 메모리는 디스크로 스왑할 수 없다.
  • 커널 논리 주소의 가장 흥미로운 점은 물리적 메모리와의 연결이다. 특히 커널 논리 주소는 물리 메모리의 첫 부분에 직접 매핑된다. 이 직접매핑에는 두 가지 의미가 있다. 첫째는 커널 논리 주소와 물리 주소 사이의 변환이 간단하다는 것이다. 결과적으로 이러한 주소는 종종 실제 물리주소 처럼 취급된다. 둘째는 메모리 청크가 커널 논리 주소 공간에서 연속적이면 물리 메모리에서도 연속적이라는 것이다. 이러한 사실은 커널 주소공간의 이 부분에서 할당된 메모리가 연속적인 물리 메모리를 필요로 하는 작업에 적합하다는 것을 의미한다. 이러한 작업에는 직접 메모리 접근 방식(DMA)을 사용하여 장치와 메모리 사이에 입출력 전송을 하는 경우를 들 수 있다.
  • 커널 주소의 다른 유형은 커널 가상 주소(kernel virtual address)이다. 이 유형의 메모리를 얻으려면 커널 코드는 다른 할당자인 vmalloc을 호출한다. vmalloc은 원하는 크기의 가상공간에서 연속적인 영역에 대한 포인터를 반환한다. 커널 논리 메모리와 달리 커널 가상 메모리는 보통 연속적이지 않다. 각 커널 가상 페이지는 연속하지 않는 물리 페이지에 매핑될 수 있으므로 DMA에는 적합하지 않다. 그러나 이러한 메모리는 결과적으로 더 쉽게 할당할 수 있기 때문에 연속된 물리 메모리 청크를 찾는 것이 어려운 대용량 버퍼 할당에 사용된다.

페이지 테이블 구조

• 64 비트 주소로 전환하면 x86의 페이지 테이블 구조가 예상대로 영향을 받는다 x86은 다중 페이지 테이블을 사용하므로 현재 64 비트 시스템은 4레벨 테이블을 사용한다. 그러나 전체 64비트 크기의 전체 가상 주소공간이 아직 사용되지 않고 하위 48비트만 사용한다. 가상주소의 상위 16비트는 사용되지 않고 (변환 과정 중 아무런 역할이 없다) 하위 12비트가 오프셋으로 사용되므로 변환 없이 직접 사용된다. 따라서 변환에는 중간의 36비트가 관여된다. 주소의 P1부분은 최상위 페이지 디렉터리를 색인하는데 사용되며, 변환은 거기서부터 시작하여 페이지 테이블의 물리 페이지가 P4에 의해 색인될 때 까지 한번에 한 레벨씩 변환이 진행되어 원하는 페이지 테이블 항목을 얻게된다.

크기가 큰 페이지 지원

• 페이지가 클 수록 매핑 개수는 더 적어진다. 그러나 페이지 테이블 항목의 개수가 적어진다는 것이 거대한 페이지를 사용하게 만드는 주된 이유는 아니다. 오히려 TLB가 더 효과적으로 작동하고 그에 따른 성능의 이득이 주된 이유이다.
• 프로세스가 많은 양의 메모리를 적극적으로 사용하면 TLB가 변환 결과로 빨리 채워지게 된다. 이러한 변환 결과가 4KB 페이지에 해당하는 경우 TLB미스를 유발하지 않으면서 접근할 수 있는 메모리의 양은 적을 것이다. 결과적으로 많은 수 GB의 메모리가 장착된 컴퓨터에서 실행되는 현대적인 대량 메모리 부하의 경우에는 심각한 성능 저하를 초래한다.
• 거대한 페이지를 사용하면 TLB의 더 적은 슬롯을 사용하더라도 TLB 미스없이 매우 큰 메모리 공간에 접근 할 수 있다는 것이 주된 이점이다. 거대한 페이지 사용에는 다른 이점도 있다. TLB - 미스 경로가 짧다. 즉, TLB 미스가 발생했을 때 더 처리된다. 게다가 특정한 시나리오 에서는 할당이 매우 빠를 수 있다는 것이 이점이다.
• 투명한(transparent) 거대한 페이지 지원 기능은 활성화되면 응용프로그램을 수정하지 않더라도 운영체제는 거대한 페이지를 할당할 수 있는 기회를 자동으로 찾는다.
• 거대한 페이지를 사용하면 내부단편화 문제가 생길 수 있다. 또 스와핑도 제대로 작동하지 않으며, 때로는 시스템이 수행하는 I/O양을 크게 증가시킨다. 일부 다른 경우에는 할당에 드는 오버헤드도 클 수 있다. 전반적으로 한 가지 분명한 사실은 그렇게 오랜 시간동안 시스템이 잘 사용한 4KB 페이지 크기가 예전에 그랬던 것처럼 보편적인 해결책이 아니라는 것이다.

페이지 캐시

• 영구장치에 대한 접근 비용을 줄이기 위해 대부분의 시스템은 공격적인 캐싱 서브 시스템을 사용하여 널리 사용되는 데이터 항목을 메모리에 유지한다.
• Linux 페이지 캐시(Page cache)는 세 가지 주요 소스로부터 온 페이지를 메모리에 유지할 수 있도록 통합된다. 세 가지 주요 소스는 메모리 맵 파일(memory map files), 파일 데이터와 장치의 메타 데이터(read(), write()), 및 힙과 각 프로세스를 구성하는 스택페이지(anonymous memory) 이러한 개체들은 페이지 캐시 해시 테이블(page cache hash table)에 보관되므로 데이터가 필요할 때 빠른 검색이 가능하다. 페이지 캐시는 항목이 클린 또는 더티인지를 추적한다. 더티 데이터는 백그라운드 쓰래드(pd flush)에 의해 백킹스토어에 주기적으로 기록되어 갱신된 데이터가 결국 영구 저장장치에 다시 기록되게 한다. 이 백그라운드 활동은 일정시간이 경과하거나 너무 많은 페이지가 더티로 분류되면 일어난다.
• 경우에 따라 시스템의 메모리가 부족하기 때문에 공간을 확보하기 위해 리눅스는 2Q교체 알고리즘의 변환된 형태를 사용한다.
• 기본 아이디어는 간단하다. 표준 LRU 교체 알고리즘이 효과적이지만 흔히 나타날 수 있는 특정 액세스 패턴에 대해서는 효과가 반전될 수 있다. 예를 들어 프로세스가 특히 메모리 크기와 거의 같거나 더 큰 대용량 파일을 반복적으로 액세스 하는 경우 LRU는 다른 파일 전부를 메모리에서 축출한다. 더 안 좋은 사실은 메모리에 존재하는 이 대용량 파일의 페이지들이 쓸모 없다는 것이다. 이 페이지들은 메모리에서 쫒겨날 때까지 한번도 다시 참조되지 않기 때문이다.
• 2Q 교체 알고리즘의 Linux 버전은 두 개의 리스트를 유지하여 메모리를 두 부분으로 나누어서 이 문제를 해결한다. 처음으로 액세스 되면 페이지는 하나의 큐(inactive list)로 들어간다. 다시 참조되면 이 페이지는 다른 큐(active list)로 승격된다. 교체가 필요할 때, 교체 후보는 inactive list에서 가져온다. 또한 Linux는 주기적으로 페이지를 활성 리스트의 맨 아래 페이지를 비활성 리스트로 이동시켜 활성 리스트의 길이가 총 페이지 캐시 크기의 약 2/3가 되도록 유지한다.
• 이 2Q 접근법은 일반적으로 LRU와 매우 유사하게 작동하지만, 대용량 파일의 순환적 접근이 발생하게 되면 이러한 페이지들을 비활성 리스트에만 존재하도록 제한하여 이 문제를 해결한다. 해당 페이지는 메모리에서 축출되기 전에 결코 다시 참조되지 않기 때문에 활성 리스트에 있는 다른 유용한 페이지를 내보내지 않는다.

보안과 버퍼 오버플로 공격

• 주요 위협 중 하나는 버퍼 오버 플로(buffer overflow) 공격으로서 보통의 사용자 프로그램이나 심지어 커널 자체를 대상으로 사용될 수 있다. 이러한 공격의 아이디어는 공격자가 목표 시스템의 주소 공간에 임의의 데이터를 주입할 수 있는 버그를 찾는 것이다. 개발자는 입력이 지나치게 길지 않을 것이라고 잘못 가정하고 안심하고 입력을 버퍼에 복사하기 때문에 이러한 취약점이 발생할 수 있다. 실제로는 입력이 너무 길기 때문에 버퍼의 경계를 넘어 목표의 메모리를 덮어쓴다.
• 버퍼 오버플로에 대한 최초의 그리고 가장 단순한 방어는 주소 공간의 특정 영역에 탑재된 어떤 코드도 실행할 수 없게 만드는 것이다. AMD가 자신의 x86 버전에 도입한 NX(No-eXecute) 비트가 그러한 방어 중하나이다. 현재는 유사한 XD 비트가 Intel CPU 에서도 제공된다. CPU는 해당 페이지 테이블 항목에 이 비트가 설정된 임의의 페이지에서 실행을 금지시킨다. 이 접근법은 공격자가 목표 스택에 주입한 코드가 실행되는 것을 방지하여 문제를 완화한다.
• ROP(Return-oriented programming)는 현재 실행 중인 함수의 복귀 주소가 복귀 명령 다음에 실행되기 원하는 악성 명령어를 가리키게끔 스택을 덮어쓸 수 있는 아이디어다.
• ROP를 방어하기 위해 Linux은 address space layout randomization(ASLR)라는 또 다른 방어책을 추가한다. 가상 주소 공간 내의 고정된 위치에 코드, 스택 및 힙을 배치하는 대신 운영체제는 무작위로 배치하기 때문에 이 유형의 공격을 구현하기 위해 필요한 복잡한 코드 시퀀스를 정교하게 만드는 것이 매우 어렵다. 취약한 사용자 프로그램에 대한 대부분의 공격은 크래시를 야기하지만 실행 중인 프로그램을 제어할 수는 없다.
• ASLR은 사용자 수준 프로그램을 위한 유용한 방어수단 이기 때문에 (KASLR : kernel address space layout randomization)라고 하는 상상할 수 없는 기능으로 커널에 통합되었다.

다른 보안 관련 문제들 : Meltdown And Spectre

• 각 공격에서 악용되는 일반적인 취약점은 최신 시스템의 CPU가 성능을 향상시키기 위해 온갖 종류의 비법을 수행한다는 것이다. 문제의 핵심에 있는 한 가지 유형의 기법을 speculative execution 이라고 하며, CPU가 향후 실행될 명령을 추측하고 이를 미리 실행하는 기법이다. 추측이 맞으면 프로그램은 더 빠르게 실행된다. 그렇지 않다면, CPU는 아키텍처 상태의 변경 사항을 되돌린 후 다시 실행을 시도하고 이번에는 올바른 실행 경로를 따라 진행된다.
• 이러한 추측의 문제는 프로세서 캐시, 분기 예측기 등과 같이 시스템의 여러 부분에서 실행 흔적을 남기는 경향이 있다는 것이다. 이러한 흔적들은 메모리 내용 심지어 MMU에 의해 보호된다고 생각했던 메모리조차도 취약하게 만들 수 있다.
• 커널 보호를 강화하는 한 가지 방법은 각 사용자 프로세스에서 커널 주소 공간을 최대한 많이 제거하고 대신 대부분의 커널 데이터에 대해 별도의 커널 페이지 테이블을 사용하는 것이다.(커널 페이지 테이블 격리(KPTI : kernel page table isolation)) 따라서, 커널의 코드와 자료 구조를 각 프로세스에 매핑하는 대신에, 최소한만 매핑한다. 이제 커널로 전환할 때 커널 페이지 테이블로 전환되어야 한다. 이렇게 하면 보안이 향상되고 일부 공격 경로는 피할 수 있지만 성능 저하라는 비용을 지불해야 한다.

PintOS

void halt(void){
	power_off();
}

void exit(int status){
	char* p_name = thread_current ()->name;
	char* p = "\\0";
	strtok_r(p_name," ",&p);
	printf ("%s: exit(%d)\\n", p_name, status);
	thread_exit();
}

int read (int fd, void *buffer, unsigned size)
{
	int byte = 0;
	char* _buffer = buffer;
	if(fd == 0)
	{
		while(byte < size)
		{
			_buffer[byte++] = input_getc();
		}
		return byte;
	}
	else if(fd == 1)
	{
		return -1;
	}
	else{

	}
}

int write (int fd, const void *buffer, unsigned size)
{
	char* _buffer = buffer;
	if(fd == 0)
	{
		return -1;
	}
	else if(fd == 1)
	{
		putbuf(_buffer,size);
		return size;
	}
	else
	{

	}
}

• halt, exit, read, write 함수를 구현해보았다.
• 로직은 확인해보았는데, 실제로 pass가 되지않는다.
• 잠시 sema_up 쪽에서 바꿔주었던 try_thread_yield일것이라고 예상해서 바꿔보았지만 그래도 바뀌지 않아서 디버깅을 해봐야겠다.