크래프톤 정글 - 5-1Week 24.02.08 - 24.02.14 부제 : 설날과 CSAPP

슬럼프가 오지 않는다.

회고

설날이 껴 있어서 1박2일 전주에 내려갔다 왔다.

오랜만에 가족, 친척을 봐서 좋았지만 내심 이렇게 2일동안 뒤쳐지는게 아닐까 하고 생각을 하기도 했다. 참 무서운 곳이다 정글은.

설날이 껴있기에 정글도 5주차를 2주동안 진행해서 5-1과 5-2로 나누도록 하겠다.

5-1주차에는 CSAPP에 집중하려고 노력했다.

일단 책의 범위도 많고, 한번 할 때 완벽하게는 당연히 못하지만 꼼꼼하게 잘 읽어놓으면 다음에 무조건 도움이 될 것이라고 생각해서 하루에 한 챕터씩 끝내려고 노력했다.

정말 힘들었지만 그래도 CSAPP와 조금 더 친해진 느낌이 든다.

미래의 일이나 여러가지 고민이 점점 많아지는 것 같다.

내가 잘하고 있다고는 생각하지만 이게 언제까지 일지도 잘 모르겠고, 앞으로 잘 해낼 수 있을까도 음 사실 이건 크게 걱정 안되는 것 같다. 나야 뭐 개 잘할거니까.

걱정되는건 더 잘하고 싶다는 것?

경쟁이 아니라 협업이고 동료지만, 그럼에도 불구하고 나는 가장 눈에 띄고 빛나고 싶다고 생각하는걸보면 욕심쟁이일지도.

누구나 잘하는 부분이 있고, 집중하는 부분이 있으니. 그렇다면 나는 이번 정글의 목표 중 하나를 CSAPP나 운영체제를 열심히해서 전공자들과 불편함 없이 대화할 수 있는 것. CSAPP는 이 정글 내에서 가장 잘하는것을 목표 중 하나로 하고 싶다.

5-2는 malloc 구현이다. 재미 있을 것 같다. 레츠꼬 레츠꼬!!

CSAPP

6. 메모리 계층구조

• 메모리 시스템은 여러가지 용량, 비용, 접근 시간을 갖는 저장장치들의 계층구조다.
• CPU 레지스터들은 가장 자주 이용하는 데이터를 보관한다. 작고 빠른 캐시 메모리는 CPU부근에서 비교적 느린 메인메모리에 저장된 데이터와 인스트럭션들의 부분집합에 대한 준비장소로 사용된다. 메인메모리는 크고 느린 디스크들에 저장된 데이터를 준비하는데 사용되고, 다시 이 디스크들은 네트워크로 연결된 다른 머신들의 디스크나 테이프에 저장된 데이터를 위한 준비장소로 사용된다.
• 메모리 계층구조는 잘 작성된 프로그램이 어느 특정 수준의 저장장치를 다음 하위 수준의 저장장치보다 좀 더 자주 접근하는 경향을 갖기 때문에 작동하다. 그래서 다음 수준에 있는 저장장치는 더 느릴 수 있으며, 비트당 크기도 더 크고 값도 더 싸다. 전체적인 효과는 계층의 바닥 근처의 값싼 저장장치만큼 값이 싸지만, 계층의 꼭대기 부근의 빠른 저장장치의 성능으로 프로그램에 데이터를 제공하는 큰 메모리 풀Pool이다.
• 좋은 지역성을 갖는 프로그램들은 동일한 집합의 데이터 원소들에 계속해서 접근하려는 경향이 있거나, 근처의 데이터 집합 접근하려한다.

6.1 저장장치 기술

6.1.1 랜덤 - 접근 메모리

• 랜덤 - 접근 메모리(RAM)는 두 종류를 가진다. - 정적, 동적. 정적 램 SRAM은 동적 램 DRAM보다 더 빠르고 훨씬 더 비싸다. SRAM은 캐시 메모리로 사용되며 CPU칩 내부 또는 외부에 장착된다. DRAM은 메인 메모리와 그래픽 시스템의 프레임 버퍼로도 사용된다.

정적RAM

• SRAM은 각 비트를 이중안정(bistable) 메모리 셀(cell)에 저장한다. 각 셀은 여섯 개의 트랜지스터 회로로 구현된다. 이 회로는 두 개의 전압 구성 또는 상태로 무한히 머물러 있을 수 있는 특성을 가지며, 이 두 가지 상태외의 다른 상태들은 모두 불안정해지게 된다. - 여기에서 시작해서 이 회로는 안정한 상태 중의 하나로 빠르게 이동하게 된다. 이러한 메모리 셀은 역진자와 유사하다.
• 진자는 왼쪽으로 완전히 기울거나 오른쪽으로 완전히 기울어 질 때 안정화된다. 다른 위치에서 이 진자는 한쪽으로 기울어지게 된다. 원리적으로 진자는 수직 방향으로도 무한히 균형을 유지할 수 있지만, 이 상태는 준 안정상태다 - 최소한의 외력이 가해져도 넘어지게 되고, 일단 넘어지면 결코 수직 위치로는 되돌아가지 않는다.
• 이중안정 본성으로 인해 SRAM 메모리 셀은 자신의 값을 전원이 공급되는 한 무한히 유지하게 된다. 심지어 이 회로는 전기적 잡음 같은 외력이 전압을 흔들 때도 외력이 없어지면 안정한 값으로 돌아갈 것이다.

동적RAM

• DRAM은 각 비트를 전하로 캐패시터에 저장한다. 캐패시터는 매우 작다. 각 셀은 캐패시터 하나와 접근 트랜지스터 하나로 구성된다. 그러나 SRAM과는 달리, DRAM 셀은 외란에 대해서 매우 민감하다. 캐패시터 전압이 달라지면 다시 회복할 수 없다. 햇볕에 노출되면 캐패시터 전압이 변한다.
• 여러가지 원인의 누수전류(leakage current)는 DRAM 셀이 10에서 100mm초 사이에 전하를 상실하게 한다. 다행스럽게도 나노초 클럭 사이클 시간으로 동작하는 컴퓨터에 대해서 이 유지시간은 꽤 긴 것이다. 메모리 시스템은 주기적으로 메모리의 모든 비트를 읽었다가 다시 써주는 방식으로 리프레시(refresh)해야 한다. 일부 시스템은 또한 오류정정코드를 사용하는데 컴퓨터 워드들은 추가적인 비트들을 사용해서 회로가 워드내에 모드 단일 오류를 감지하고 정정 할 수 있다.

일반 DRAM

• DRAM 칩내의 셀들은 슈퍼셀들로 나누어지며, 각각은 w DRAM 셀들로 이루어진다. d * w DRAM은 총 dw 비트의 정보를 저장한다. 슈퍼셀들은 row와 column로 이루어진 직사각형의 배열로 구성되어있다.
• 정보는 pin이라고 부르는 외부 커넥터를 통해 칩의 안과 밖을 흘러다닌다.
• 핀들의 집합 - 1바이트 칩 내부 또는 외부로 전송할 수 있는 8개의 데이터 핀들과 두 비트 행과 열 슈퍼셀을 연결하는 두 개의 addr 핀으로 구성, 제어정보를 전달한다.
• 각각의 DRAM칩은 w비트를 일정시간에 DRAM칩으로, 그리고 칩으로부터 전송할 수 있는 메모리 컨트롤러로 알려진 회로에 연결된다. 슈퍼셀(i,j)의 내용을 읽으려면 메모리 컨트롤러는 행 주소 i를 DRAM에 보내고 다음에 열 주소 j를 보낸다. DRAM은 슈퍼셀(i,j)의 내용을 컨트롤러로 보내주는 것으로 응답하게 된다. 행주소 i는 RAS(row access strobe)요청이라고 부른다. 열 주소 j는 CAS(column access strobe)요청이라고 부른다. RAS와 CAS 요청이 같은 DRAM 주소 핀을 공유한다.
• 이차원 배열 구조의 단점은 주소가 두 단계로 보내져야 하며, 이로 인해 접근시간 access time이 증가한다는 점이다.

메모리 모듈

• DRAM 칩은 메인 시스템보드의 확장 슬롯에 꽂을 수 있는 메모리 모듈 형태로 패키징된다.
• 메모리 주소 A에서 64비트 워드를 가져오려면, 메모리 컨트롤러는 A를 슈퍼셀 주소로 변환하고 이것을 메모리 모듈로 보낸다. 그러면 메모리 모듈은 i, j를 각 DRAM에 보낸다. 여기에 대한 응답으로 각 DRAM은 자신의 (i, j) 슈퍼셀의 8비트 내용을 출력한다. 모듈 내의 회로는 이 출력들을 모아서 64비트 워드로 구성하고, 이것을 메모리 컨트롤러에게 돌려준다.
• 메인 메모리는 복수의 메모리 모듈을 메모리 컨트롤러에 연결하여 연동 될 수 있다. 이 경우, 컨트롤로가 주소 A를 받을 때 컨트롤러는 A를 가지고 있는 모듈 k를 선택해서 A를(i, j) 형으로 변환하고 (i, j)를 모듈 k로 보낸다.

Enhanced DRAM

DRAM 메모리의 종류

• Fast Page Mode DRAM , FPM DRAM : 재래식 DRAM은 슈퍼셀의 행 전체를 자신의 내부 행 버퍼에 복사하며, 이중 한 바이트만 사용하고 나머지는 모두 버린다. FPM DRAM은 행 버퍼로부터 직접적으로 같은 행에 연속적으로 접근할 수 있게 지원 받도록 개선한 것이다.
• Extended data out DRAM , EDO DRAM : FPM DRAM을 개선한 형태로 각각의 CAS 신호가 보다 촘촘한 간격으로 발생할 수 있도록 했다.
• Synchronous DRAM, SDRAM : 재래식 FPM, EDO DRAM은 메모리 컨트롤러와 통신할 때 명시적인 explicit 제어신호들을 사용한다는 면에서 비동기형이다. SDRAM은 이 제어신호의 상당 부분을 메모리 컨트롤러를 구동하는 동일한 외부 클럭 신호의 상승 에지로 대체한다.
• Double Data-Rate Synchronous DRAM, DDR SDRAM : 두 개의 클럭 에지 모두를 제어신호로 사용해서 DRAM의 속도를 두 배로 올려 SDRAM을 개선한 것이다.
• VideoRAM VRAM : 그래픽 시스템의 프레임 버퍼로 사용된다.

비휘발성 메모리

• DRAM과 SRAM은 전원이 꺼지면 정보도 잃어버리기 때문에 휘발성이다. 반면에, 비휘발성 메모리는 이들의 전원이 꺼져도 정보를 유지한다. 역사적인 이유로 이들은 모두 Read Only Memory, ROM이라고 부른다. ROM은 이들이 재기록reprogram 될 수 있는 횟수와 이들을 재기록하는 방법으로 구별된다. ROM 디바이스에 저장된 프로그램들은 종종 펌웨어 firmware라고 부른다. 컴퓨터 시스템의 전원이 공급되면 ROM에 저장된 펌웨어를 실행 시킨다. 일부 시스템들은 펌웨어에 PC의 BIOS(Basic Input/Output System) 같은 적은 수의 기본 입출력 함수를 제공한다.

메인 메모리 접근하기

• 데이터는 버스라고 하는 공유된 전기회로를 통해서 프로세서와 DRAM 메모리간에 앞뒤로 교환된다. CPU와 메모리간의 매 전송은 버스 트랜잭션이라고 부르는 일련의 단계들을 통해 이뤄진다. 읽기 트랜잭션은 데이터를 메인 메모리에서 CPU로 이동 시키고, 쓰기 트랜잭션은 CPU에서 메인 메모리로 이동시킨다.
• 버스는 주소, 데이터, 제어신호를 포함하는 병렬 선들의 집합이다. 특정 버스 설계에 따라 데이터와 주소 신호들은 같은 전선들을 공유할 수 있거나, 서로 다른 전선들을 사용할 수 있다. 또한 두 개 이상의 장치들은 같은 버스를 공유 할 수 있다. 제어라인들 트랜잭션들을 동기화하고 현재 어떤 종류의 트랜잭션이 수행되고 있는지 알려주는 신호들을 전송해준다.
• I/O 브릿지는 시스템 버스의 전기적 신호를 메모리 버스의 전기적 신호로 변환한다.

6.1.2 디스크 저장장치

디스크의 구조

• 디스크는 원판(platter)로 구성된다. 각 원판들은 두개의 옆면 즉 표면으로 이루어져 있으며, 이들은 자성을 띤 기억 물질로 코팅 되어 있다. 원판의 중심부에 있는 회적하는 축(spindle)은 원판을 고정된 회전율로 돌려주며, 이 비율은 대개 분당 5,400 에서 15,000번 회전하는 비율(RPM)을 갖는다. 디스크는 일반적으로 밀봉된 저장기에 들어있는 한 개 이상의 원판들을 가진다.
• 디스크의 각 표면은 트랙이라고 하는 여러개의 동심원들로 이루어져있다. 각 트랙은 섹터들의 집합으로 나누어진다. 각 섹터는 섹터위에 자성물질로 인코딩 된 동일한 수의 데이터 비트(일반적으로 512바이트)를 가진다. 섹터들은 아무 데이터도 기록되지 않은 갭으로 분리되어있다. 갭은 섹터를 식별하는 포맷팅 비트를 저장한다.
• 디스크 용량 : 디스크 용량은 다음의 기술 요소들에 의해 결정된다.
  • 기록밀도(bits/in) : 1인치의 트랙에 집어 넣을 수 있는 비트의 수
  • 트랙밀도(tracks/in) : 원판 중심에서 반지름의 11인치 길이에 넣을 수 있는 트랙의 수
  • 면전밀도(bit/in^2) : 기록밀도 * 트랙밀도

디스크의 동작

• 디스크는 구동팔의 끝에 연결된 읽기/쓰기 헤드를 사용해서 자성 표면에 저장된 비트를 읽거나 쓴다. 이와 같은 기계적 동작은 탐색(seek) 이라고 알려져 있다. 다중 원판을 갖는 디스크는 각 표면마다 별도의 읽기/쓰기 헤드를 가지며, 헤드들은 수직으로 정렬되며 같이 움직인다. 어떤 특정 시간에 모든 헤드들은 동일한 실린더에 위치한다.
• 디스크는 데이터를 섹터 크기의 블록으로 읽고 기록한다. 섹터에 접근하는 시간은 세 개의 주요 부분으로 이루어진다.
  • 탐색시간
    • 특정 타깃 섹터의 내용을 읽기 위해서 팔은 먼저 헤드를 타깃 섹터를 보유한 트랙 위로 위치시킨다. 팔을 이동하기 위해 소요되는 시간을 탐색시간이라고 부른다.
  • 회전 지연 시간
    • 헤드가 트랙 위에 위치하면 드라이브는 타킷 섹터의 첫 번째 비트가 헤드 아래로 지나가는것을 기다린다. 이 단계의 성능은 헤드가 타깃섹터에 도달할 때 표면의 위치와 디스크의 회전속도에 모두 관련된다.
  • 전송시간
    • 타킷섹터의 첫 번째 비트가 헤드 아래에 있을 때, 드라이브는 섹터의 내용을 읽거나 쓰기를 시작할 수 있다. 하나의 섹터를 전송하는 시간은 회전속도와 트랙당 섹터 수에 따라 달라진다.
• 하나의 디스크 섹터에 있는 512바이트에 접근하는 시간은 탐색시간과 회전 지연 시간이 가장 크게 영향을 준다. 섹터내의 첫 번째 바이트에 접근하는데 긴 시간이 걸리지만, 나머지 바이트들은 실질적으로 시간이 걸리지 않는다.
• 탐색 시간과 회전 지연 시간이 대략 같기 때문에 탐색시간을 두 배해서 간단히 디스크 접근 시간을 추정할 수 있다.

논리적 디스크 블록

• 디스크들은 다중 표면을 가지고, 표면에 여러 기록 영역을 가지는 복잡한 구조를 갖는다. 이러한 복잡성을 운영체제로 부터 감추기 위해 신형 디스크들은 0, 1, … , B-1로 번호를 붙인 B섹터 크기의 논리블록의 배열로 이들의 구조를 좀 더 단순한 모습으로 나타낸다. 디스크 패키지 안에 있는 디스크 컨트롤러 라고 하는 작은 하드웨어/펌웨어 디바이스는 논리 블록 수와 실제(물리적) 디스크 섹터와의 매핑을 유지한다.
• 운영체제 디스크섹터를 메인메모리로 읽어 들이는 것과 같은입출력 연산을 수행하려 할때, 디스크 컨트롤러로 명령을 보내서 특정 논리 블록 번호를 읽어들이게 한다. 컨트롤러의 펌웨어는 논리블록 번호를 해당 물리 섹터를 유일하게 식별하는(surface, track, sector) 쌍으로 번역하는 빠른 테이블 참조를 수행한다. 컨트롤러의 하드웨어는 이 쌍을 해석해서 헤드들을 적절한 실린더로 이동시킨 뒤, 섹터가 헤드 아래로 지나가기를 기다리고, 헤드가 검출한 비트들을 컨트롤러상의 작은 메모리 버퍼로 수집해서 이들을 메인메모리로 복사한다.

입출력장치 연결하기

• 그래픽카드, 모니터, 키보드, 디스크 같은 입출력 장치들을 입출력 버스로 CPU와 메인메모리에 연결된다. CPU에 특화된 메모리 버스와 시스템 버스와는 달리, PCI같은 입출력 버스는 하부 CPU에 독립적으로 설계된다.

디스크 접근하기

• 디스크 컨트롤러가 CPU에서 읽기 명령을 받은 후, 논리 블록 번호를 섹터 주소로 번역하고, 섹터의 내용을 읽어서 CPU의 개입없이 이것을 메인메모리에 직접 전송한다. 디바이스가 스스로 읽기 또는 쓰기 버스 트랜잭션을 수행하는 이 과정은 직접 메모리접근 DMA라고 알려져 있다. 이 데이터의 전송은 DMA 전송이라고 알려져 있다.

6.1.3 Soild State Disks

• 일종의 저장장치 기술로 플래시 메모리를 사용하며, 어떤 경우에 종래의 회전하는 디스크에 대한 매력적인 대체품이다.
• SSD 패키지는 종래의 회전하는 디스크에서 기계적인 드라이브를 대체한 하나 이상의 플래시 메모리 칩, 디스크 컨트롤러 같은 역할을 하는 하드웨어/펌웨어 장치이며, 논리 블록들에 대한 요청들을 하부 물리 디바이스에 대한 접근으로 번역하는 플래시 번역 계층으로 이루어져있다.
• SSD에서 읽어오기 작업이 쓰기 작업보다는 더 빠르다는 점에 주목해야 한다. 랜덤읽기와 쓰기 성능간의 차이는 하부 플레시 메모리의 기본적인 특성 때문이다.
  • 랜덤쓰기는 두 가지 이유로 더 느리게 실행된다.
    • 첫째, 한 개의 블록을 지우는 것은 1ms 단위로 상대적으로 긴 시간이 걸리며, 이것은 한 개의 페이지에 접근하기 위해 걸리는 시간보다 한 단위 더 걸린것이다.
    • 둘째, 만일 어떤 쓰기 연산이 이미 존재하는 데이터를 포함하는 페이지p를 수정하려고 한다면, 유용한 데이터를 가지고 있던 같은 블록 내의 모든 페이지는 페이지 p에 쓰기 작업이 일어나기 전에 새로운(지워진) 블록으로 복사 되어야 한다.
• SSD 장점
  • 반도체 메모리로 만들어서 움직이는 부품이 없으며, 따라서 회전하는 디스크 보다 랜덤 접근 시간이 훨씬 빠르고 더 작은 전력을 소모하며 더 견고하다.
• 단점
  • 플래시 블록이 반복적인 쓰기 작업 후에 노화해서 SSD도 노후할 가능성이 있다. 플래시 번역 계층의 노화 평균화 로직(wear leveling logic)은 소거 작업을 모든 블록에 균일하게 걸쳐서 분산하는 방법으로 각 블록의 수명을 극대화 하는 시도를 한다.
  • 가격이 비싸고, 저장용량은 상당히 적다.

6.1.4 저장장치 기술 동향

• 여러가지 저장장치 기술은 서로 다른 가격과 성능간에 절충과정(trade-off)를 가진다.

6.2 지역성(Locality)

• 시간 지역성
  • 좋은 시간 지역성을 갖는 프로그램에서는 한번 참조된 메모리 위치는 가까운 미래에 다시 여러번 참조 될 가능성이 높다.
• 공간 지역성
  • 좋은 공간 지역성을 갖는 프로그램에서는 만일 어떤 메모리 위치가 일단 참조되면, 이 프로그램은 가까운 미래에 근처의 메모리 위치를 참조할 가능성이 높다.
• 운영체제 수준에서 지역성의 원리는 시스템이 메인 메모리를 가장 최근에 참조한 가상주소 공간 블록에 대한 캐시로 사용 될 수 있게 해준다.

6.2.1 프로그램 데이터 참조의 지역성

• 벡터의 각 원소를 순차적으로 방문하는 함수는 stride-1 참조 패턴을 갖는다고 말한다.(원소 크기에 대해서) 우리는 때때로 stride-1 참조 패턴을 순차 참조 패턴이라고 부를 것이다. 연속적인 벡터의 매 k번째 원소를 방문하는 것을 stride-k 참조 패턴이라고 부른다. stride-1 참조 패턴은 프로그램 내 보편적이고 중요한 공간 지역성의 원인이 된다. stride가 증가하면 공간 지역성은 감소한다.
• 보폭 stride은 또한 다 차원 배열을 참조하는 프로그램에 대해서도 중요한 문제다. 이중으로 중첩된 루프는 배열의 원소들을 행 우선 순서로 읽는다. 즉, 내부 루프는 첫 번째 행의 원소들을 읽으며, 다음으로 두 번째 행, 이런식으로 진행한다.

6.2.2 인스트럭션 선입의 지역성

• 프로그램 인스트럭션들은 메모리에 저장되어 있으며, CPU에 의해 선입되어야(읽어야)하기 떄문에 인스트럭션 선입에 관한 프로그램의 지역성도 평가할 수 있다.
• 코드를 프로그램 데이터와 구별하는 가장 중요한 특성은 코드는 런타임에 거의 수정되지 않는다는 점이다. 프로그램이 실행되는 동안 CPU는 메모리로 부터 자신의 인스트럭션들을 읽는다. CPU는 이 인스트럭션들을 거의 수정하거나 지우지 않는다.

6.2.3 지역성 요약

• 동일한 변수들을 반복적으로 참조하는 프로그램은 좋은 시간 지역성을 누린다.
• Stride-k 참조 패턴을 갖는 프로그램에 대해서 stride가 적으면 적을수록 공간 지역성도 좋아진다.
• 루프는 인스트럭션 선입에 대해 좋은시간 및 공간 지역성을 갖는다. 루프 본체가 작을록 루프 반복 실행수는 더 커지고 지역성도 더 좋다.

6.3 메모리 계층구조

6.3.1 메모리 계층구조에서의 캐시

• 일반적으로 캐시는 보다 크고 느린 디바이스에 저장된 데이터 객체를 위한 준비 영역으로 사용하는 작고 빠른 저장장치다. 캐시를 사용하는 과정은 캐싱으로 알려져있다.
• 메모리 계층구조의 중심개념은 각 k에 대해 레벨 k에 있는 보다 빠르고 더 작은 저장장치가 레벨k+1에 있는 더 크고 더 느린 저장장치를 위한 캐시서비스를 제공하는 것이다.
• 레벨 k+1에서 저장장치는 블록이라고 하는 연속된 데이터 객체 블록으로 나뉜다. 각 블록은 유일한 주소 또는 이름을 가지며, 이들은 자신을 다른 블록과 구분해준다. 마찬가지로, 레벨 k에서의 저장장치는 레벨 k+1에 있는 블록들과 같은 크기인 더 작은 집합의 블록들로 나뉜다. 시간상 아무때나 레벨 k에 있는 캐시는 레벨 k+1에서 온 블록들의 부분집합의 사본을 포함한다.
• 데이터는 항상 레벨 k와 k+1 사이에서 블록 크기의 전송 유닛 단위로 복사된다. 블록 크기가 계층구조의 인접한 모든 쌍들 사이에서 고정되어 있는 반면, 다른 레벨의 쌍들은 서로 다른 블록 크기를 가질 수 있다.

캐시 적중

• k+1로부터 객체d를 필요로 할때 k에 저장된 블록 중 d가 캐시되어 있다면 캐시적중이라고 한다.

캐시 미스

• 반면, 캐시되지 않는다면 캐시 미스가 발생한 것이다. 미스가 존재할 때 레벨 k에서의 캐시는 레벨 k+1에 있는 캐시로 부터 d를 포함하는 블록을 가져오며, 만일 k캐시가 이미 꽉 찬 상태라면 기존 블록에 덮어쓰기도 한다.
• 블록을 덮어 쓰는 과정은 블록을 교체하거나 추출하는 것으로 알려져 있다. 추출되는 블록은 때로 희생블록이라고 부른다. 캐시 교체 정책에 따라, 랜덤 교체정책이라면 랜덤으로 희생블록을 선택하고, LRU 교체 정책을 갖는 캐시는 가장 과거에 접근한 블록을 선택한다.

6.4 캐시 메모리

6.4.1 기본 캐시 메모리 구조

• 캐시의 구성은 순서쌍(S, E, B, m)으로 규정할 수 있다.
  • S : S = 2^s 개의 캐시 집합 배열
  • E : E개의 캐시 라인. 각 집합의 구성
  • B : B = 2^b 바이트의 데이터 블록. 유효비트 한 개, 태그 비트로 구성.
  • m : 주소의 크기
• 캐시의 크기 C는 SEB로 나타낸다.

6.4.2 직접 매핑 캐시

• 캐시는 집합 당 캐시 라인의 수 E에 의해 서로 다른 클래스로 구분된다. 집합당 정확히 한 개의 라인을 갖는 경우 직접 매핑 캐시라고 알려져 있다.
• 캐시가 어떤 요청이 적중인지 미스인지 결정하고, 요청한 워드를 뽑아내기 위해 수행하는 세 작업.
  • 집합 선택
  • 라인 매칭
  • 워드 추출
• 태그와 인덱스 비트를 합치면 메모리 내 각 블록을 유일하게 지정한다.
• 여러 블록이 동일한 캐시 집합에 대응된다.
• 동일한 캐시 집합에 대응되는 블록들은 태그를 사용해서 유일하게 구별된다.

6.4.3 집합 결합성 캐시

• 각 집합이 하나 이상의 캐시 라인을 갖는다 1<E<C/B 인 캐시는 E-중 집합 결합성 캐시라고 부른다.

6.4.4 완전 결합성 캐시

• 모든 캐시 라인들을 갖는 하나의 집합으로 구성된다(E = C/B)
• 하나의 집합에 모든 라인이 들어간다. TLB 같이 작은 캐시에서만 그 사용이 적절하다.

6.4.5 쓰기와 관련된 이슈

• write - through
  • w의 캐시 블록 전체를 다음 하위 레벨로 써준다.
  • 매 쓰기 작업마다 버스 트래픽을 발생시킨다는 단점이 있다.
• write-back
  • 한 갱신을 지연시켜 이 블록이 블록 교체 알고리즘에 의해 캐시에서 축출될 때에만 갱신된 블록을 하위레벨에 써준다.
  • 지역성으로 버스트래픽을 상당해 줄일 수 있지만 좀 더 복잡하다는 단점이 있다.
  • 캐시는 캐시블록이 수정되었는지 여부를 나타내는 dirty hit를 각 라인마다 추가로 유지해야한다.

쓰기 미스를 다루는 방식

• write - allocate
  • 해당 블록을 다음 하위 레벨에서 캐시로 가져오고 난 뒤에 캐시블록을 갱신한다.
  • write-back에서 사용한다.
• no - write - allocate
  • 캐시를 통과하고 워드를 직접 다음 하위 레벨에 써준다.
  • write - through 에서 사용한다.

6.5 캐시 친화적 코드 작성하기

• 공통적인 경우 빠르게 동작하게 만들어라
• 각 내부 루프의 캐시 미스 수를 최소화 하라
• 지역 변수들에 대한 반복적인 참조는 좋으며, 그 이유는 컴파일러가 이들을 레지스터 파일에 캐싱할 수 있기 때문이다(시간 지역성)
• stride-1 참조 패턴은 좋으며, 그 이유는 메모리 계층구조의 모든 레벨에서 데이터를 연속적인 블록들로 저장하기 때문이다(공간 지역성)

8. 예외적인 제어흐름

• 시스템들은 또한 내부 프로그램 변수에 의해 표시되지 않으며, 프로그램의 실행과는 반드시 관련되어 있지 않은 시스템 상태의 변화에도 반응할 수 있어야 한다.
• 급격한 변화를 예외적인 제어흐름이라고 부른다. 예외적인 제어흐름은 컴퓨터 시스템의 모든 수준에서 발생한다.

8.1 예외 상황

• 예외 상황은 부분적으로는 하드웨어와 운영체제에 의해서 구현된 예외적인 제어흐름의 한 가지 형태다.
• 예외 상황은 어떤 프로세서 상태의 변화에 대한 대응으로, 제어흐름의 갑작스런 변화다.
• 프로세서가 이벤트가 발생했다는 것을 감지하면, 예외 테이블이라고 하는 점프 테이블을 통해서 이 특정 종류의 이벤트를 처리하기 위해 특별히 설계 된 운영체제 서브루틴(예외처리 핸들러)으로 간접 프로시저 콜을 하게된다.
• 예외처리 핸들러가 처리를 끝마치면, 예외상황을 발생시킨 이벤트의 종류에 따라서 다음과 같은 세 가지 중의 하나의 일이 발생한다.
  1. 핸들러는 제어를 현재 인스트럭션으로 돌려준다.
  2. 핸들러는 제어를 다음 인스트럭션으로 돌려준다.
  3. 핸들러는 중단된 프로그램을 종료한다.

8.1.1 예외처리

• 한 시스템 내에서 가능한 예외 상황의 종류마다 중복되지 않는 양의 정수를 예외번호로 할당하고 있다. 이 숫자들의 일부는 프로세서 설계자가 부여한 것이다. 나머지 번호는 운영체제 커널(운영체제의 메모리가 상주하는 부분)설계자가 할당한다.
• 시스템 부팅 시, 운영체제는 예외 테이블이라고 하는 점프 테이블을 할당하고 초기화해서 엔트리 k가 예외 상황 k에 대한 핸들러 주소를 갖는다.
• 런타임에 프로세서는 이벤트가 발생했다는 것을 감지하고, 대응되는 예외번호 k를 결정한다. 프로세서는 그 후에 예외 테이블의 엔트리 k를 통해서 간접 프로시저 콜을 하는 방법으로 예외 상황을 발생시킨다. 예외 상황은 프로시저콜과 유사하지만 차이점이 있다.
  • 프로세서는 프로시저 콜을 사용해서 핸들러로 분기하기 전에 스택에 리턴 주소를 푸시한다. 그렇지만 예외의 종류에 따라 리턴 주소는 현재 인스트럭션이거나 다음 인스트럭션이 된다.
  • 프로세서는 핸들러가 리턴할 때 중단된 프로그램을 다시 시작하기 위해 필요하게 될 스택상에 추가적인 프로세서 상태를 푸시한다.
  • 제어가 사용자 프로그램에서 커널로 전환하고 있을 때 이 모든 아이템들은 사용자 스택 위가 아니라 커널 스택상에 푸시된다.
  • 예외 핸들러는 커널모드에서 돌아가는데, 이들이 모든 시스템 자원에 완전히 접근할 수 있다는 것을 의미한다.
• 하드웨어가 예외 상황을 촉발해서 남은 작업은 예외 핸들러에 의해 소프트웨어로 진행된다.

8.1.2 예외의 종류

인터럽트

• 인터럽트는 프로세서 외부에 있는 입출력 디바이스로부터의 시그널의 결과로 비동기적으로 발생한다. 하드웨어 인터럽트를 위한 예외 핸들러는 종종 인터럽트 핸들러 라고 부른다.
• 입출력 디바이스들은 프로세서 칩의 핀에 시그널을 보내서 인터럽트를 발생시키고, 인터럽트를 발생시킨 디바이스를 식별하는 예외번호를 시스템 버스에 보낸다.
• 현재의 인스트럭션이 실행을 완료한 후에, 프로세서는 인터럽트 핀이 high로 올라갔다는 것을 발견하고 시스템 버스에서 예외번호를 읽으며, 적절한 인터럽트 핸들러를 호출한다. 핸들러가 리턴할 때, 제어를 다음 인스트럭션으로 돌려준다.

트랩과 시스템 콜

• 트랩은 의도적인 예외 상황으로, 어떤 인스트럭션을 실행한 결과로 발생한다. 트랩 핸들러는 제어를 다음 인스트럭션으로 리턴한다. 트랩의 가장 중요한 사용은 시스템 콜이라고 알려진 사용자 프로그램과 커널 사이의 프로시저와 유사한 인터페이스를 제공하는 것이다.
• 사용자 프로그램은 여러 서비스를 종종 커널에게 요청할 필요가 있다. 이런 커널 서비스의 제한된 접근을 하기 위해서 프로세서는 특별한 ‘n’ 인스트럭션을 제공하며, 이들은 사용자 프로그램이 서비스 n을 요청하고자 할 때 사용자 프로그램이 사용할 수 있는 인스트럭션이다. syscall인스트럭션을 실행하면 트랩이 인자들을 해독하고 적절한 커널 루틴을 호출하는 예외 핸들러로 가게한다.
• 보통의 함수는 사용자 모드에서 돌아가며 이 때문에 이들이 실행할 수 있는 인스트럭션은 제한적이며, 이들은 호출하는 함수와 동일한 스택을 사용한다. 시스템 콜은 커널 모드에서 돌아가며, 이로 인해 커널 내에서 정의된 스택에 접근하며, 특권을 가진 인스트럭션을 실행할 수 있도록 해준다.

오류(fault는 error와 다르다)

• 오류는 핸들러가 정정할 수 있는 가능성이 있는 에러조건으로부터 발생한다. 오류가 발생하면 프로세서는 제어를 오류 핸들러로 이동해준다. 만일 핸들러가 에러 조건을 정정할 수 있다면, 제어를 오류를 발생시킨 인스트럭션으로 돌려주어서 거기서부터 재 실행한다. 그렇지 않다면, 핸들러는 커널 내부의 abort 루틴으로 리턴해서 오류를 발생 시킨 응용 프로그램을 종료한다.

중단

• 패리티 에러와 하드웨어 같은 복구할 수 없는 치명적인 에러에서 발생한다. 중단 핸들러는 절대로 응용 프로그램으로 제어를 리턴하지 않는다.

8.2 프로세스

• 프로세스의 고전적인 정의는 실행 프로그램의 인스턴스이다. 시스템 내의 각 프로그램은 어떤 프로세서의 문맥(context)에서 돌아간다. 문맥은 프로그램이 정확하게 돌아가기 위해서 필요한 상태로 구성된다. 이 상태는 메모리에 저장된 프로그램의 코드와 데이터, 스택, 범용 레지스터의 내용, 프로그램 카운터, 환경변수, 열려있는 파일의 식별자를 포함한다.
• 프로세스가 응용에 제공하는 주요 추상화
  • 우리의 프로그램이 프로세서를 혼자서 사용한다는 착각을 제공하는 독립적 논리제어 흐름
  • 우리의 프로그램이 혼자서 메모리 시스템을 가진다는 착각을 제공하는 사적주소 공간

8.2.1 논리적인 제어흐름

• 프로그램 실행을 단일 스텝으로 실행하기 위해서 디버거를 사용하고자 한다면, 우리의 실행 목적파일 내에 들어있거나 프로그램과 동적으로 런타임에 링크된 공유 객체 내의 인스트럭션들에게 일련의 프로그램 카운터PC값들이 대응된다는 것을 관찰할 수 있다. 이러한 PC값의 배열을 논리적 제어흐름 또는 논리흐름이라고 부른다.
• 하나의 프로세서를 사용해서 여러 프로세스들이 교대로 돌아간다. 각 프로세스는 자신의 흐름의 일 부분을 실행하고나서 다른 프로세스들로 순서를 바꾸어 실행하는 동안 선점된다.(일시적으로 정지된다.) 이 프로세스들 중에서 하나의 문맥에서 실행되는 프로그램은 이것이 마치 프로세서를 배타적으로 소유한 것처럼 보인다. 사실은 만일 각 인스트럭션의 소모시간을 정확히 측정하려고 한다면 CPU가 주기적으로 프로그램의 순차적인 인스트럭션 실행이 이유없이 멈춰 있는 것처럼 보인다는 것을 발견한다. 이렇게 동작한다고 문제가 생기지는 않는다. 왜냐하면 프로세서가 정지(Stall)할 때마다 프로그램의 메모리 위치나 레지스터 내용에 변경되는 사항 없이 프로그램 실행은 순차적으로 다시 실행된다.

8.2.2 동시성 흐름

• 자신의 실행시간이 다른 흐름과 겹치는 논리 흐름을 동시성 흐름이라고 부르며, 이 두 흐름은 동시에 실행한다고 말한다. 공동으로 실행되는 흐름의 일반적인 현상이 동시성이라고 알려져 있다. 또한 프로세스가 다른 프로세스들과 교대로 실행된다는 개념은 멀티태스킹이라고 알려져 있다. 한 프로세스가 자신의 흐름 일부를 실행하는 매 시간 주기를 타임 슬라이스 라고 부른다. 그래서 멀티태스킹은 타임 슬라이싱이라고도 부른다.
• 동시성 흐름에 대한 개념은 흐름들이 돌아가는 프로세서 코어나 컴퓨터 개수와는 무관하다.
• 두 개의 흐름이 서로 다른 프로세서 코어나 컴퓨터에서 동시에 돌아간다면 이것은 병렬흐름이다.

8.2.3 사적 주소공간

• n비트 주소를 갖는 머신에서, 주소공간은 2^n의 가능한 주소들로 0,1,…,(2^n)-1을 갖는다. 프로세스는 각 프로그램에 자신만의 사적 주소공간을 제공한다. 이 공간의 특정 주소에 연결된 메모리의 한 개의 바이트가 일반적으로 다른 프로세스에 의해서 읽히거나 쓰일 수 없다는 의미로 이 공간은 사적이다.

8.2.4 사용자 및 커널모드

• 운영체제가 완벽한 프로세스 추상화를 제공하기 위해서 프로세서는 응용 프로그램이 접근 할 수 있는 주소공간 부분뿐만 아니라 응용 프로그램이 실행할 수 있는 인스트럭션들을 제한하는 메커니즘을 제공해야 한다.
• 프로세서는 대개 이러한 작업을 지원하기 위해 프로세스가 현재 가지고 있는 특권을 저장하는 일부 제어 레지스터로 모드 비트를 제공한다. 모드 비트가 설정되면 프로세스는 커널모드로 동작한다(슈퍼 바이저 모드라고도 불린다.) 커널모드에서 돌고 있는 프로세스는 인스트럭션 집합의 어떤 인스트럭션도 실행할 수 있으며, 시스템 내의 어떤 메모리 위치도 접근할 수 있다.
• 모드 비트가 세트되지 않을 때, 프로세스는 사용자 모드에서 돌고 있는 것이다. 사용자 모드의 프로세스는 특수 인스트럭션을 실행할 수 없다. 또한 주소공간의 커널 영역에 있는 코드나 데이터를 직접 참조 할 수도 없다. 이러한 시도를 하게 되면 치명적인 보호 오류가 발생한다. 그 대신 사용자 프로그램은 시스템 콜을 통해서 커널코드와 데이터에 간접적으로 접근해야 한다.
• 응용 코드를 실행하는 프로세스는 처음에는 사용자 모드에 있다. 예외가 발생해서 제어가 예외 핸들러로 넘어가면, 프로세서는 사용자 모드에서 커널모드로 변경한다. 핸들러는 커널모드에서 돌아간다. 제어가 응용 코드로 돌아오면 프로세서는 모드를 커널모드에서 사용자 모드로 변경한다.

8.2.5 문맥전환 context switching

• 운영체제 커널은 문맥전환이라고 알려진 예외적인 제어흐름의 상위 수준 형태를 사용해서 멀티태스킹을 구현한다.
• 커널은 각 프로세스마다 컨텍스트를 유지한다. 컨텍스트는 커널이 선점된 프로세스를 다시 시작하기 위해서 필요로 하는 상태다. 이것은 범용 레지스트러, 부동소수점 레지스터, 프로그램 카운터, 상태 레지스터, 사용자 스택, 커널 스택, 여러 커널 자료구조(페이지 테이블, 프로세스 테이블, 파일 테이블)같은 객체들의 값들로 구성된다.
• 커널은 프로세스가 실행되는 동안의 어떤 시점에 현재 프로세스를 선점(일시적으로 정지)하고 이전에 선점된 프로세스를 다시 시작하는 것을 결정할 수 있다. 이 결정은 스케줄링이라고 알려져 있으며, 스케줄러라고 부르는 커널 내부의 코드에 의해 처리된다. 커널이 실행 할 새 프로세스를 선택할 때 커널이 그 프로세스를 스케줄 했다고 말한다.
• 커널이 실행 할 새 프로세스를 스케줄 한 후에 현재 프로세스를 선점(일시적으로 정지) 하는것을 문맥 전환이라고 하며, 이 메커니즘을 사용해서 새로운 프로세스로 제어를 이동한다.
• 문맥전환 수행절차
  1. 현재 프로세스의 컨텍스트 저장
  2. 이전에 선점된(일시적으로 정지된) 프로세스의 저장된 컨텍스트를 복원
  3. 제어를 이 새롭게 복원된 프로세스로 전달한다.
• 문맥전환은 커널이 사용자를 대신해서 시스템 콜을 실행하고 있을 때 일어날 수 있다. 만일 시스템 콜이 어떤 이벤트의 발생을 기다리기 때문에 블록된다면 커널은 현재 프로세스를 sleep시키고 다른 프로세스로 전환한다. 일반적으로, 어떤 시스템 콜이 블록되지 않았다 하더라도 커널은 시스템 콜을 호출했던 프로세스로 제어를 돌려주는 대신에 문맥전환을 수행하는 것을 결정할 수 있다.
• 또한 문맥전환은 인터럽트의 결과로 발생할 수 있다.

8.3 시스템 콜의 에러처리

• Unix의 시스템 수준 함수가 에러를 만날 때 이들은 대개 -1을 리턴하고, 전역 정수 변수인 errno를 세팅해서 무엇이 잘못 되었는지를 나타낸다.

8.4 프로세스의 제어

• Unix는 C프로그램으로 부터 프로세스를 제어하기 위한 많은 시스템 콜을 제공한다.

8.4.1 프로세스 ID가져오기

• 각각의 프로세스는 고유의 양수(0이 아닌) 프로세스ID(PID)를 가진다. getpid함수는 호출하는 함수의 PID를 리턴한다.

8.4.2 프로세스의 생성과 종료

• 프로그래머의 관점에서 프로세스는 다음의 세 가지 상태중의 하나로 생각할 수 있다.
  • 실행중 : 프로세스는 CPU에서 실행하고 있거나 실행을 기다리고 있으며, 궁극적으로 커널에 의해서 스케줄 될 것이다.
  • 정지 : 프로세스의 실행은 정지한 상태이고 스케줄 되지 않는다.
  • 종료 : 프로세스는 영구적으로 정지된다. 프로세스는 다음의 세 가지 이유 중의 하나로 종료된다.
    1. 프로세스를 종료하는 시그널을 받았을 때
    2. 메인 루틴에서 리턴할 때
    3. exit 함수를 호출할 때
• exit 함수는 종료 상태 status로 프로세스를 종료한다.
• 부모 프로세스는 fork 함수를 불러서 자식 프로세스를 생성한다. 새롭게 생성된 자식 프로세스는 완벽하게는 아니지만 부모와 거의 동일하다. 자식은 코드, 데이터 세그먼트, 힙, 공유된 라이브러리, 사용자 스택을 포함하는 부모의 사용자 수준 가상 주소공간과 동일한(그러나 분리된) 복사본을 갖는다. 자식은 또한 부모가 오픈한 파일 식별자 모두와 동일한 사본을 갖는다. 이것은 부모가 fork를 호출했을 때 부모가 오픈한 파일 모두를 읽고 쓸 수 있다는 것을 의미한다. 부모와 새롭게 생성된 자식간의 가장 중요한 차이는 이들이 서로 다른 PID를 가진다는 것이다.
  • fork 함수는 흥미로운데, 그것은 이들이 한 번 호출되지만 두 번 리턴하기 때문이다.
    • 한 번은 호출한 프로세스(부모)
    • 한 번은 새롭게 생성된 프로세스(자식)
• 부모에서 fork는 자식의 PID를 리턴한다. 자식에서 fork는 0을 리턴한다. 자식의 PID가 항상 0이 아니기 때문에 리턴값은 프로그램이 부모에서 실행하고 있는지 자식에서 실행하고 있는지를 구분하는 명확한 방법을 제공한다.
• fork 함수를 처음 배울 때 프로세스 그래프를 그려보면 도움이 된다. 이 그래프는 프로그램 문장들의 부적인 순서를 나타내는 순서 그래프의 단순한 종류다. 각 꼭짓점은 프로그램 문장 하나의 실행에 대응된다.
• 하나의 프로세서에서 돌아가는 어떤 프로그램에 대해, 해당 프로세서 그래프에서 꼭짓점들의 위상학적 정렬은 프로그램에서 문장들의 가능한 전체 정렬을 나타낸다.

8.4.3 자식 프로세스의 청소

• 프로세스가 어떤 이유로 종료할 때, 커널은 시스템에서 즉시 제거하지 않는다. 그 대신, 프로세스는 부모가 청소할 때까지 종료된 상태로 남아있다. 부모가 종료된 자식을 청소할 때 커널은 자식의 exit 상태를 부모에게 전달하며, 그 후 종료된 프로세스를 없애며 이 시점에서 프로세스가 사라지게 된다. 종료되었지만 아직 청소되지않은 프로세스를 좀비라고 한다.
• 부모 프로세스가 종료할 때, 커널은 init 프로세스로 하여금 모든 고아가 된 자식들의 입양된 부모가 되도록 한다. 이 init 프로세스는 PID 1번이며, 시스템 초기화 과정에서 커널에 의해 생성되고, 결코 종료되지 않으며, 모든 프로세스의 조상이다. 만일 어떤 부모 프로세스가 자신의 좀비 자식들을 소거하지 않고 종료하려면, 커널은 이 init 프로세스가 이들을 소거하도록 한다. 그렇지만, 쉘이나 서버같이 오랫동안 실행하는 프로그램들은 항상 자신의 좀비를 소거해야 한다
• 프로세스는 waitpid 함수를 호출해서 자신의 자식들이 종료되거나 정지되기를 기다린다.

에러조건

• 호출하는 프로세스가 자식이 없다면, waitpid는 -1을 리턴하며 errno를 ECHILD로 설정한다. waitpid 함수가 어떤 시그널에 의해 중단되었다면, -1을 리턴하며 errno를 EINTR로 설정한다.

8.4.4 프로세스 재우기

• sleep 함수는 일정 기간동안 프로세스를 정지 시킨다.
• sleep은 요청한 시간이 경과하면 0을 리턴하고, 그렇지 않은 경우에는 남은 시간동안 잠을 잔다. 만일 sleep 함수가 시그널에 의해서 중단되어 완료되지 못한 채로 리턴된다면 후자의 경우가 가능해진다.

8.4.5 프로그램의 로딩과 실행

• execve 함수는 현재 프로그램의 컨텍스트 내에서 새로운 프로그램을 로드하고 실행한다.
• argu 변수는 널로 종료되는 포인터의 배열을 가리키며, 각각의 포인터는 하나의 인자 스트링을 가리킨다. 관습에 의해 argu[0]은 실행가능 목적파일의 이름이다.

8.5 시그널

• 시그널은 작은 메세지 형태로, 프로세스에게 스스템 내에 어떤 종류의 이벤트가 일어 났다는 것을 알려준다.
• 각 시그널 타입은 특정 종류의 시스템 이벤트에 대응된다. 하위 수준 하드웨어 예외는 커널의 예외 핸들러에 의해 처리되며, 정상적으로 사용자 프로세스에서는 볼 수 없다. 시그널은 이러한 예외들을 사용자 프로세스에 노출해주는 메커니즘을 제공한다.

8.5.1 시그널 용어

• 시그널을 목적지 프로세스로 전달하는 것은 두 단계로 이루어진다.
  • 시그널 보내기 : 시그널을 목적지 프로세스로 보낸다. 시그널은 두 이유중 하나로 배달된다.
    1. 시스템 이벤트를 감지했다.
    2. 어떤 프로세스가 커널에 명시적으로 시그널을 목적지 프로세스에 보낼 것을 요구하기 위해서 kill 함수를 호출했다.
  • 시그널 받기 : 목적지 프로세스는 배달된 신호에 대해서 커널이 어떤 방식으로 반응해야 할 떄 목적지 프로세스는 시그널을 받는다. 프로세스는 시그널 핸들러라고 부르는 사용자 수준 함수를 실행해서 시그널을 무시하거나, 종료하거나, 획득할 수 있다.
• 보내졌지만 아직 받지 않은 시널은 펜딩(pending) 시그널이라고 부른다. 시간상으로 어떤 시점에서 특정 타입에 대해 최대 한 개의 펜딩 시그널이 존재할 수 있다. 만일 어떤 프로세스가 타입 k의 펜딩 시그널을 가지고 있다면 이 프로세스로 다음에 발생하는 k 타입의 시그널은 큐에 들어가지 않고 단순히 버려진다.
• 프로세스는 선택적으로 어떤 시그널의 수신을 블록할 수 있다. 어떤 시그널이 블록될 때 배달은 될 수 있지만 펜딩 시그널은 이 프로세스가 시그널 블록을 끌 때 까지는 수신되지 않는다.
  • 펜딩 시그널은 최대 한 번만 수신된다.

8.5.2 시그널 보내기

• Unix 시스템은 시그널을 프로세스로 보내는 여러가지 메커니즘을 제공한다. 모든 메커니즘은 프로세스 그룹 개념을 사용한다.

프로세스 그룹

• 모든 프로세스는 정확히 한 개의 프로세스 그룹에 속하며, 이것은 양수 Process group ID로 식별한다.
• 기본적으로 자식 프로세스는 자신의 부모와 동일한 프로세스 그룹에 속한다.

키보드에서 시그널 보내기

• Unix 쉘은 작업의 추상화를 사용해서 한 개의 명령줄을 해석한 결과로 만들어진 프로세스에 반영한다. 시간상의 어떤 시점에서도 최대 한 개의 포그라운드 작업과 0또는 그 이상의 백그라운드 작업이 존재한다.
• 쉘은 각 작업마다 별도의 프로세스 그룹을 만든다. 일반적으로 프로세스 그룹 ID는 작업 내에 부모 프로세스들 중의 하나에서 가져온다.

kill 함수로 시그널 보내기

• 프로세스는 kill 함수를 호출해서 시그널을 다른 프로세스로 보낸다.(자기 자신을 포함한다)

8.5.3 시그널의 수신

• 커널이 프로세스 P를 커널모드에서 사용자 모드로 전환할 때, 커널은 프로세스P에 대한 블록되지 않은 펜딩 시그널(pending & blocked)의 집합을 체크한다. 만일 이 집합이 비어있다면(대개의 경우), 커널은 제어를 P의 논리 제어흐름 내의 다음 인스트럭션으로 전달한다.
• 그렇지만 만일 이 집합이 비어있지 않다면, 커널은 집합 내 어떤 시그널 k를 선택해서(대개 가장 작은k) P가 시그널k를 수신하도록 한다. 시그널을 수신하면 프로세스는 어떤 동작을 개시한다. 프로세스가 이 동작을 완료하면, 제어는 P의 논리 제어흐름내의 다음 인스트럭션으로 돌아간다.
• 시그널 타입은 사전에 정의된 기본동작을 가진다.
  • 프로세스가 종료한다.
  • 프로세스는 종료하고 코어를 덤프한다
  • 프로세스는 SIGCONT 시그널에 의해 재시작 될 때까지 정지한다.
  • 프로세스는 시그널을 무시한다.
• 핸들러가 return 문장을 실행할 때, 제어는(대개) 프로세스가 시그널의 수신으로 중단되었던 제어흐름 내 인스트럭션으로 다시 전달된다. 여기서 ‘대개’ 라고 했는데, 그것은 일부 시스템에서 중단된 시스템 콜들이 에러가 발생하면 즉시 리턴하기 때문이다.

8.5.4 시그널 블록하기와 블록 해제하기

• 리눅스는 시그널을 블록하기 위해 묵시적이고 명시적인 방법을 제공한다.
  • 묵시적 블록 방법 : 기본적으로 커널은 핸들러에 의해 처리되고 있는 유형의 모든 대기 시그널의 처리를 막는다.
  • 명시적 블록 방법 : 응용 프로그램들은 sigprocmask 함수와 이들의 도움 함수를 이용해서 시그널들을 명시적으로 블록하거나 블록 해제 할 수 있다.

8.5.5 시그널 핸들러 작성하기

• 핸들러는 이해하기 어렵게 만드는 몇 가지 특성을 가진다.
  1. 핸들러는 메인 프로그램과 동시적으로 돌아가고, 전역변수를 공유하며, 그래서 메인 프로그램과 다른 핸들러에 뒤섞일 수 있다.
  2. 어떻게 그리고 언제 시그널들이 수신될 수 있는지는 종종 직관적이지 않다.
  3. 다른 시스템들은 다른 시그널 처리 방식을 갖는다.
• 안전한 시그널 처리
  • G0. 핸들러는 가능한 한 간단하게 유지하라.
  • G1. 핸들러에서 비동기성-시그널-안전한 함수만 호출하라
  • G2. errno를 저장하고 복원하라
  • G3. 모든 시그널을 블록시켜서 공유된 전역 자료구조들로의 접근을 보호하라
  • G4. 전역변수를 volatile로 선언하라
  • G5. sig_atomic_t로 플래그들을 선언하라(읽기와 쓰기가 원자형 : 중단불가)

호환성 있는 시그널 핸들링

• Unix 시그널 핸들링의 또 다른 지저분한 측면은 서로 다른 시스템들이 서로 다른 시그널 처리 방식을 갖는다는점이다.
• 이런 이슈들을 다루기 위해 POSIX 표준은 sigaction 함수를 정의하고 있으며, 이것은 사용자들이 핸들러를 설치할 때, 사용자들이 원하는 시그널 처리 개념을 명확히 명시하도록 해준다.
  • signal 이라고 부르는 래퍼 함수를 통해 sigaction을 호출한다.
  • signal 래퍼는 다음과 같은 시그널 처리 개념으로 시그널 핸들러를 설치한다.
  • 현재 핸들러에 의해 처리되고 있는 시그널 유형들만 블록된다.
  • 모든 시그널 구현에서 처럼 시그널들은 큐에 들어가지 않는다.
  • 중단된 시스템 콜들은 필요할 때마다 자동으로 재시작된다.
  • 시그널 핸들러가 설치되면, signal이 핸들러의 인자 SIG_IGN, ISIG_DFL 중의 하나를 갖는 핸들러로 불린다.

8.6 비지역성 점프

• C는 비지역성 점프라고 부르는 사용자 수준의 예외적 제어흐름의 형태를 제공하며, 이것은 보통의 콜 - 리턴 순서를 통할 필요없이 하나의 함수에서 현재 실행하고 있는 다른 함수로 제어를 이동한다. 비지역성 점프는 setjmp와 longjmp 함수로 제공된다.
• 비지역성 점프의 중요한 응용은 심하게 중첩된 함수 콜에서, 대개 어떤 에러 조건을 검출한 결과로 즉시 리턴을 허용하는 것이다. 또 다른 중요한 응용은 시그널의 도착으로 중단되었던 인스트럭션으로 돌아가는 대신 특정 코드 위치로 시그널 핸들러를 벗어나서 분기하는 경우다.

8.7 프로세스 조각을 위한 도구

• 리눅스 시스템은 프로세스를 관찰하고 조작하기 위한 여러가지 유용한 도구를 제공한다.
  • STRACE. : 돌고있는 프로그램과 자식들이 호출한 각 시스템 콜의 경로를 인쇄한다.
  • PS. : 현재 시스템 내의 프로세스들(좀비를 포함해서)을 출력한다.
  • TOP. : 현재 프로세스의 자원 사용에 관한 정보를 출력한다.
  • PMAP. : 프로세스의 메모리 맵을 보여준다.
  • /proc. : 여러가지 커널 자료구조의 내용을 사용자 프로그램이 읽을 수 있는 ASCII 문자 형태로 내보내는 가상 파일 시스템

9. 가상 메모리

• 메모리를 보다 효율적이고 더 적은 에러를 갖도록 관리하기 위해서 현대의 시스템은 가상메모리(VM : Virtual Memory)이라고 알려진 메인 메모리 추상화를 제공한다.
• 가상 메모리는 한 개의 깔끔한 메커니즘을 사용해서 세 개의 중요한 기능을 제공한다.
  1. 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급해서 메인 메모리 내 활성화 영역만 유지하고, 데이터를 디스크와 메모리안에 필요에 따라 전송하는 방법으로 메인 메모리를 효율적으로 사용한다.
  2. 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다.
  3. 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다.

9.1 물리 및 가상주소 방식

• 컴퓨터 시스템의 메인메모리는 M개의 연속적인 바이트 크기 셀의 배열로 구성된다. 각 바이트는 고유의 물리주소(PA)를 가진다. 첫 번째 바이트는 주소 0, 다음 바이트는 주소 1, 다음은 2, 이런 식으로 진행된다. 이와 같은 간단한 구조가 주어졌을 때, CPU가 메모리에 접근하는 가장 자연스러운 방식은 물리주소를 사용하는 것이다. 이런 접근법을 물리 주소방식이라고 한다.
• 현대의 프로세스들은 가상주소 방식이라는 같은 주소 형태를 사용한다.
• CPU는 가상주소지정으로 가상주소(VA)를 생성해서 메인메모리에 접근하며, 이것은 메모리로 보내지기 전에 적절한 물리 주소로 변환된다. 가상주소를 물리 주소로 변환하는 작업은 주소 번역이라고 알려져 있다. CPU 칩 내에 메모리 관리 유닛(MMU)이라고 부르는 전용 하드웨어는 메인 메모리에 저장된 참조 테이블을 사용하여 실행 중에 가상주소를 번역하며, 이 테이블의 내용은 운영체제가 관리한다.

9.2 주소공간

• 주소공간은 비음수 정수 주소의 정렬된 집합이다.
• 주소공간의 정수가 연속적이라면, 이 공간은 선형주소공간이라고 한다. 가상메모리를 갖는 시스템에서, CPU는 가상 주소공간이라고 불리는 N=2^n 주소의 주소공간에서 가상의 주소를 생성한다.
• 주소공간의 크기는 가장 큰 주소를 표시하는데 필요한 비트 수로 나타낸다. 현대 시스템은 전형적으로 32비트 또는 64비트 가상 주소공간을 지원한다.
• 또한 컴퓨터 시스템은 이 시스템 내의 M바이트의 물리메모리로 대응되는 물리 주소 공간을 갖는다.
• 메인메모리의 각 바이트는 가상 주소공간으로 부터 선택된 가상주소를 가진다.

9.3 캐싱도구로서의 VM

• 가상 메모리 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다. 각 바이트는 특정한 가상주소를 가지며 배열의 인덱스로 작용한다. 디스크 안의 배열 정보는 메인 메모리에 캐시된다. 메모리 계층구조 안에 있는 캐시는 블록 단위로 분할이 되며, 디스크와 메인메모리 사이에 징검다리 역할을 한다. VM system은 가상메모리를 규정된 사이즈 블록단위로 분할하여 관리한다. 분할된 블록들은 가상 페이지라고 부른다. 각 가상 페이지는 P = 2p바이트의 크기를 갖는다. 이와 비슷하게 물리 메모리도 물리 페이지로 분할되어 사용한다.
• 시간상의 어느 시점에서도 가상 페이지 집합은 세 개의 중첩되지 않는 부분 집합으로 나누어진다.
  • unallocated : VM 시스템에 의해 아직까지 할당되지 않은 페이지들 비할당된 블록들을 이들과 관련된 데이터를 하나도 가지고 있지 않으며, 따라서 디스ㅡ크 상에 어떤 공간도 차지하지 않는다.
  • cached : 현재 물리 메모리에 캐시되어 할당된 페이지들.
  • uncached : 물리 메모리에 캐시되지 않은 할당된 페이지들.

9.3.1 DRAM 캐시의 구성

• 메모리 계층구조 내에서 DRAM 캐시의 위치는 이들이 구성된 방식에 큰 영향을 갖는다. DRAM이 SRAM보다 10배는 더 느리고, 디스크는 DRAM보다 100,000더 느리다. 따라서 DRAM 캐시미스는 SRAM 캐시미스와 비교해서 값이 매우 비싸다.
• 큰 규모의 미스 비용과 첫 번째 바이트를 접근하는데 드는 비용 때문에 가상페이지는 더 커지고 있으며, 대개 4KB에서 2MB 값을 가진다. DRAM 캐시는 완전 결합성이다. 즉, 모든 가상페이지는 물리 페이지에 둘 수 있다. 디스크의 큰 접근 시간 때문에 DRAM은 항상 write-through 대신에 write-back을 사용한다.

9.3.2 페이지 테이블

• 물리 메모리에 저장된 자료구조의 조합. 가상 페이지를 물리페이지로 매핑한다.
• 주소 번역 하드웨어는 이들이 가상주소를 물리 주소로 변환할 떄마다 페이지 테이블을 읽는다. 운영체제는 페이지 테이블의 콘텐츠 관리와 페이지들을 디스크와 DRAM 사이에서 왔다갔다 하는 것을 관장한다.
• 페이지 테이블은 페이지 테이블 엔트리(PTE)의 배열이다. 가상 주소공간의 각 페이지는 페이지 테이블 내에 고정된 오프셋 위치에 PTE를 갖는다. 편의상 각 PTE가 한 개의 유효비트(vaild), n 비트의 주소 필드로 구성된다고 가정하겠다. 유효비트는 가상페이지가 현재 DRAM에 캐시되어 있는지를 나타낸다.
• 유효비트가 세팅되었다면, 주소 필드는 가상페이지가 캐시되어 대응되는 DRAM의 물리 페이지의 시작을 나타낸다. 만일 유효비트가 세팅되어 있지 않다면, NULL주소는 가상페이지가 아직 할당되지 않았음을 나타낸다. 그렇지 않은 경우 주소는 디스크상의 가상페이지의 시작 부분을 가리킨다.

9.3.4 페이지 오류

• DRAM 캐시 미스를 페이지 오류(Page fault)라고 한다.
• 가상메모리 용어에서 블록은 페이지라고 알려져 있다. 디스크와 메모리 사이에 페이지를 전송하는 동작은 스와핑 또는 페이징이라고 알려져 있다. 페이지들은 디스크에서 DRAM으로 스와핑해 들어오며(페이징되어 들어오며), DRAM에서 디스크로 스와핑되어 나간다(페이징되어 나간다). 미스가 발생할 때, 하나의 페이지로 스와핑 되어 들어오는 마지막 순간까지 기다리는 전략은 요구페이징(Demand paging)이라고 알려져 있다.

9.4 메모리 관리를 위한 도구로서의 VM

• 운영체제는 각 프로세스마다 별도의 페이지 테이블을 제공하며, 그래서 별도의 가상주소공간을 제공한다.
• 다수의 가상페이지들이 동일한 공유된 물리 메모리에 매핑될 수있다.
• 요구페이징과 분리된 가상 주소공간 조합은 메모리가 시스템에서 사용되고 관리하는 방식에 중요한 영향을 미친다. 특히 VM은 링킹 과정과 로딩, 코드와 데이터의 공유, 응용으로의 메모리 할당을 단순화 해준다.
  • 링킹을 단순화 한다. 별도의 주소공간은 각 프로세스들이 각 메모리 이미지에 대해서 코드와 데이터가 실제로 물리 메모리내 어디에 위치하는지에 상관없이 동일한 기본 포맷을 사용하도록 해준다. 이러한 통일성은 링커의 설계와 구현을 매우 단순화 해주며 물리 메모리 상에서 궁극적인 코드와 데이터의 위치에 독립적인 완전히 링크된 실행가능 파일을 만들 수 있게 해준다.
  • 로딩을 단순화 해준다. 실행 파일과 공유 목적 파일들을 메모리에 로드하기 쉽게 해준다. 목적파일의 .data와 .text 섹션들을 새롭게 생성된 프로세스에 로드하기 위해서, 리눅스 로더는 코드와 데이터 세그먼트를 위한 가상의 페이지를 할당하고, 이들을 무효로 표시하고,(즉 캐시되지 않은 상태) 이들의 페이지 테이블 엔트리를 목적파일의 해당 위치를 가리키게 한다. 흥미로운 점은 로더가 실제로 디스크로부터 메모리로 데이터를 전혀 복사하지 않았다는 것이다. 각 페이지가 최초로 참조될 때, CPU가 인스트럭션을 선입하거나 메모리 위치를 참조하는 인스트럭션을 실행할 때, 데이터는 요청에 의해 자동으로 페이지화 된다.
  • 연속된 가상 페이지를 임의의 파일 내의 임의의 위치로 매핑하는 개념은 메모리 매핑이라고 알려져 있다.
  • 공유를 단순화 해준다. 별도의 주소공간은 운영체제에 사용자 프로세스와 운영체제 자신 사이에 공유를 관리하는 일정한 메커니즘을 제공한다. 일반적으로 각 프로세스는 다른 프로세스와 공유되지 않은 자신만의 사적인 코드, 데이터, 힙, 스택 영역을 가진다. 이 경우에 운영체제는 대응되는 가상페이지를 중첩되지 않는 물리 페이지로 매핑하는 페이지 테이블을 만든다.
  • 일부의 경우 프로세스들이 코드와 데이터를 공유하는 것이 바람직 할 때가 있다. 모든 프로세스는 동일한 운영체제 커널 코드를 호출해야 하며 모든 C프로그램은 표준 라이브러리 루틴을 호출한다. 커널과 표준 C라이브러리 코드를 각 프로세스에 별도로 포함시키기 보다 운영체제는 가상페이지들은 동일한 물리 페이지로 적절하게 매핑해서 이 코드들의 한 개의 사본을 공유할 수 있게 한다.
  • 메모리 할당을 단순화 해준다. 사용자 프로세스로 돌고 있는 프로그램이 추가적인 힙 공간을 요청할 때, 운영체제는 적당한 수의, 연속적인 가상 메모리 페이지를 할당하고, 이들을 물리 메모리 내에 위치한 k개의 임의의 물리 페이지로 매핑한다.

9.5 메모리 보호를 위한 도구로서의 VM

• 모든 현대 컴퓨터 시스템은 운영체제가 메모리 시스템에 접근하는 것을 제어할 수 있는 수단을 제공한다.
• 별도의 가상 주소공간을 제공하면 사적 메모리를 다른 프로세스로부터 분리하는 것이 쉬워진다.
• CPU가 주소를 만들 때마다 PTE를 읽기 때문에 PTE에 허가비트를 추가해서 주소 번역 하드웨어가 가상페이지 내용으로의 접근을 제어하게 한다.
• PTE에 세 개의 허가비트
  • SUP비트는 프로세스들이 이 페이지에 접근하기 위해 커널 모드(수퍼바이저)로 돌고 있어야 하는지를 나타낸다. 커널 모드로 돌고 있는 프로세스들은 모든 페이지에 접근하도록 허용되지만, 사용자 모드에서 돌고 있는 프로세스들은 SUP가 0인 페이지들만 접근이 허용된다.
  • READ와 WRITE 비트는 이 페이지에 대한 읽기와 쓰기 접근을 제어한다.

9.6 주소의 번역

• 주소 번역은 N - 원소 가상 주소공간(VAS : virtual address space)과 M - 원소 물리 주소공간(PAS : physical address space)의 원소들 간의 매핑이다.
• CPU 내에 있는 제어 레지스터인 페이지 테이블 베이스 레지스터(PTBR : Page Table Base Register)는 현재 페이지 테이블을 가리킨다. n비트 가상주소는 두 개의 컴포넌트를 가진다.
  • P비트 가상 페이지 오프셋(VPO : virtual page offset)
  • (n-p)비트 가상페이지 번호(VPN : virtual page number)
• MMU는 VPN을 사용해서 적합한 PTE를 선택한다. 대응되는 물리주소는 페이지 테이블 엔트리에서 가져온 물리 페이지 번호(PPN : physical page number)와 가상주소에서 온 VPO를 연결한 것이다. 물리와 가상 페이지 모두 P바이트이므로 물리 페이지 오프셋(PPO : physical page offset)은 VPO와 동일하다.

그림 9.13

9.6.1 캐시와 VM의 통합

• 가상메모리와 SRAM 캐시를 사용하는 모든 시스템에는 SRAM 캐시를 접근하기 위해 가상주소 또는 물리 주소를 사용할 수 있다. 대부분의 시스템은 물리 주소지정을 선택한다. 물리주소를 사용하면, 다중 프로세스들이 캐시에서 블록을 갖는 것과 마친가지로 가상페이지로부터 블록을 공유하는 것이 단순해진다. 게다가 캐시는 보호 이슈를 다룰 필요가 없어지는데, 접근권한이 주소 번역 과정의 일부로 체크되기 때문이다.
• 메인 아이디어는 주소 번역이 캐시 참조 이전에 일어난다는 것이다. 페이지 테이블 엔트리들이 다른 데이터 워드와 마찬가지로 캐싱될 수 있다는 점에 주목해야 한다.

9.6.2 TLB를 사용한 주소 번역 속도의 개선

• CPU가 가상주소를 생성할 때마다 MMU는 가상주소를 물리 주소로 번역하기 위해 PTE를 참조해야 한다. 최악의 경우, 이것은 메모리로부터 추가적인 선입 작업을 필요로 하며, 이를 위해서 수숩에서 수백 사이클의 비용이 들게 된다. PTE가 L1에 캐싱되어 있다면, 이 비용은 2에서 1사이클로 줄어든다. 그렇지만 많은 시스템들은 이 비용마저 MMU내 번역 참조 버퍼(TLB : translation lookaside buffer)라고 부르는 작은 캐시를 포함해서 제거하려고 한다.
• TLB는 작은 가상주소지정 캐시로, 각 라인의 하나의 PTE로 구성된 하나의 블록을 저장한다. TLB는 대개 높은 수준의 결합성을 가진다. 집합선택과 라인매칭을 위해 사용되는 index와 tag 필드는 가상주소 내의 가상 페이지 번호에서 추출된다.
• 모든 주소 번역 단계들이 온칩 MMU 내에서 수행되기 때문에 매우 빠르다.

9.6.3 다중 레벨 테이블

• 페이지 테이블을 압축하는 보편적인 접근법은 대신 페이지 테이블의 계층구조를 사용하는 것이다.
• 1단계 테이블의 각 PTE는 가상 주소공간 크기를 매핑하는 역할을 하며, 이들 각각의 블록은 연속적인 페이지들로 이루어진다.
• 만일 블록 i안의 모든 페이지들이 할당된다면 1단계 PTE i는 널이다. 그렇지만 최소한 블록 i의 한 개 페이지가 할당된다면 1단계 PTE i는 2단계 페이지 테이블의 베이스를 가리킨다.
• 2단계 페이지 테이블 내의 각 PTE들은 가상메모리 페이지를 관리하며, 이것은 앞에서 단일 레벨 페이지 테이블을 살펴보았을 때와 동일하다.
• 이 기법은 메모리 요구량을 두 가지 방법으로 줄여준다
  1. 만일 1단계 테이블의 PTE가 널이면, 해당 2단계 페이지 테이블이 존재할 필요가 없어진다.
  2. 1단계 테이블만이 항상 메인 메모리에 있을 필요가 있다. 2단계 페이지 테이블은 이들이 필요할 때 VM 시스템에 의해서 생성되고, 페이지 인 또는 아웃 될 수 있으며, 이로 인해 메인 메모리로의 압박을 줄일 수 있다. 과도하게 사용된 2단계 페이지 테이블만이 메인 메모리에 캐시될 필요가 있다.

9.7 사례 연구 : 인텔 코어 i7/리눅스 메모리 시스템

9.7.2 리숙스 가상 메모리 시스템

• 커널 가상 메모리는 커널 내의 코드와 데이터 구조를 포함한다. 일부 커널 가상메모리 영역은 모든 프로세스가 공유하는 물리페이지에 매핑되어 있다. 각 프로세스는 커널의 코드와 전역데이터 구조를 공유한다. 흥미롭게도, 리눅스는 또한 연속적인 가상페이지 집합을 대응하는 연속적인 물리 페이지의 집합에 매핑한다.

리눅스 가상메모리 영역

• 리눅스는 가상메모리 영역(세그먼트)들의 집합으로 구성한다. 한 개의 영역은 기존(할당된) 가상메모리의 연속된 묶음으로, 이들의 페이지는 어떤 형식으로 연관되어 있다. 각각의 기존 가상페이지는 특정 영역에 포함되고 특정 영역의 일부분이 아닌 가상페이지들은 존재하지 않으며, 프로세스에 의해 참조될 수 없다. 영역이라는 개념은 중요한데, 이것은 가상 주소공간이 간격을 가질 수 있게 해준다. 커널은 존재하지 않는 가상페이지를 계속해서 추적하지는 않으며, 이러한 페이지들은 메모리, 디스크 또는 커널 자신 내부에서 추가적인 자원을 소모하지 않는다.
• 커널은 시스템 내 각 프로세스를 위해 고유의 태스크 구조를 관리한다. 태스크 구조의 원소들은 커널이 프로세스를 실행하는데 필요한 모든 정보를 포함하거나 가리킨다.
• 태스크 구조 내 엔트리 중의 하나는 가상메모리의 현재 상태를 구정하는 mm_struct를 가리킨다.

9.8 메모리 매핑

• 리눅스는 가상메모리 영역의 내용을 디스크의 객체에 연결해서 초기화한다. 영역들은 다음 두 종류의 객체 중의 하나로 매핑될 수 있다.
  1. 리눅스 파일 시스템 내의 일반 파일 : 한 영역은 실행가능 목적파일과 같은 일반 디스크 파일의 연속적인 섹션으로 매핑될 수 있다. 파일 섹션은 페이지 크기의 조각들로 나누어지고, 이들은 각각 가상페이지의 초기 내용을 포함하고 있다. 요구 페이징 때문에 CPU가 처음 페이지에 접근할 때까지는 이 가상페이지들 중 아무것도 실제로 물리 메모리로 스왑되어 들어오지 않는다. 만일 이 영역이 파일 섹션보다 더 크다면, 이 영역은 0으로 매핑된다.
  2. 무기명 파일 : 한 영역은 또한 무기명 파일로 매핑될 수 있다. 이 파일은 커널이 만든 것이며, 모두 이진수0을 포함한다. CPU가 이 영역의 가상페이지에 처음으로 접근할 때, 커널은 물리 메모리 내에서 적당한 희생자 페이지를 찾아내고, 만일 이것이 dirty하다면 희생자 페이지를 스왑아웃하고, 희생자 페이지를 이진수0으로 덮어쓰고, 이 페이지가 존재한다고 표시하기 위해 페이지 테이블을 갱신한다. 어떤 데이터도 실제로는 디스크와 메모리 사이에 이동하지 않았다는 점에 유의해야 한다. 이 이유에서 무기명 파일로 매핑된 영역 내의 페이지들은 때로 무요구(demand-zero) 페이지 라고 불린다.

9.8.1 다시보는 공유객체

• 각각의 프로세스를 위해 물리 메모리 상에 이와 같이 공통으로 사용하는 코드를 중복해서 두는 것은 매우 낭비다. 메모리 매핑을 통해서 어떻게 객체들이 다수 프로세스들에 의해 공유될 수 있는지 깔끔한 메커니즘을 가지게 됐다.
• 객체는 공유 가상메모리 영역으로 공유객체 또는 사적객체로 매핑될 수 있다. 공유객체를 자신의 공유 주소공간으로 매핑한다면, 이 프로세스가 이 영역에 쓰는 모든 내용은 자신의 공유 메모리 내로 객체를 매핑한 다른 프로세스들도 볼 수 있게 된다. 나아가서 이러한 변경된 내용은 디스크 상의 원래의 객체에도 반영된다.
• 반면에 사적객체에 매핑된 영역에 관한 수정사항들은 다른 프로세스들은 볼 수 없으며, 이 영역에서 프로세스가 수행한 모든 쓰기 작업들은 디스크 상의 객체에는 반영되지 않는다. 공유된 객체가 매핑된 가상메모리 영역은 종종 공유영역이라고 불린다. 사적영역과 비슷하게 정의된다.
• 사적객체를 매핑하는 각 프로세스에 대해서, 대응되는 사적영역에 대한 페이지 테이블 엔트리는 읽기 - 허용으로 표시되어 있으며, 영역 구조체는 사적 copy-on-write로 표시 되어있다. 두 프로세스 모두 자신의 사적영역에 쓰려고 하지 않는 한, 이들은 물리 메모리에 단 한 개의객체 사본을 계속 공유한다. 그렇지만 한 프로세스가 사적영역내의 일부 페이지에 쓰려고 하는 순간 쓰기 작업은 보호 오류를 유발한다.
• 핸들러는 이 페이지의 새로운 사본을 물리 페이지 내에 만들고, 페이지 테이블을 갱신해서 새로운 사본을 가리키도록 하며, 그 후에 이 페이지에 대한 쓰기 허가를 복원한다. 오류핸들러가 리턴할 때, CPU는 이 쓰기작업을 재실행한다.

9.9 동적메모리 할당

• 동적메모리 할당기는 힙이라고 하는 프로세스의 가상메모리 영역을 관리한다.
• 힙이 미초기화된 데이터 영역 직후에 시작해서 위쪽으로(높은 주소 방향으로) 커지는 무요구 메모리 영역이라고 가정할 것이다. 커널은 힙의 꼭대기를 가리키는 변수 brk를 사용한다.
• 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다. 각 블록은 할당 되었거나 가용한 가상메모리의 연속적인 묶음이다. 할당된 블록은 응용하기 위해 명시적으로 보존되었다. 가용한 블록은 할당을 위해 사용할 수 있다. 가용블록은 응용이 명시적으로 할당할 때 까지 가용한 상태로 남아있다. 할당된 블록은 응용에 의해 명시적으로 또는 메모리 할당기 자신에 의해 묵시적으로 반환될 때까지 할당된 채로 남아있다.
• 메모리 할당기 두 가지 유형
  • 명시적 할당기 : 응용이 명시적으로 할당된 블록을 반환해줄 것을 요구한다.
  • 묵시적 할당기 : 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 할당기가 검출 할 수 있을 것을 요구한다. 가비지 컬렉터라고 알려져 있다. 자동으로 사용하지 않은 할당된 블록을 반환시켜주는 작업을 가비지 컬렉션이라고 부른다.

9.9.1 malloc과 free 함수

• malloc 함수는 블록 내 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다. 32비트 모드에서 malloc은 주소가 항상 8의 배수인 블록을 리턴하고 64비트 모드에서 주소는 항상 16의 배수다.
• sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다. 성공한다면 이전의 brk값을 리턴하고, 아니면 -1을 리턴하고 errno을 ENOMEM으로 설정한다. 만일 incr이 0이면 sbrk는 현재 brk값을 리턴한다. 프로그램들은 할당된 힙 블록을 free함수를 호출해서 반환한다. 인자는 할당된 블록의 시작을 가리켜야 한다.

9.9.3 할당기의 요구사항과 목표

• 명시적 할당기들은 다소 엄격한 제한사항 내에서 동작해야한다.
  • 임의의 요청순서 처리하기 : 응용 프로그램은 각각의 가용블록이 이전의 할당 요청에 의해 현재 할당된 블록에 대응되어야 한다는 제한사항을 만족하면서 임의의 순서로 할당과 반환요청을 할 수 있다.
  • 요청에 즉시 응답하기 : 할당기는 할당 요청에 즉시 응답해야한다. 따라서 할당기는 재요청하거나 버퍼 요청을 할 수 없다.
  • 힙만 사용하기 : 확장성을 갖기 위해서 할당기가 사용하는 비확장성 자료구조들은 힙 자체에 저장되어야 한다.
  • 블록 정렬하기(정렬요건) : 할당기는 블록들이 이들이 어떤 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.
  • 목표1. 처리량 극대화 하기
  • 목표2. 메모리 이용도를 최대화 하기

9.9.4 단편화

• 나쁜 힙 이용도의 주요 이유는 단편화라고 알려진 현상인데, 이것은 가용메모리가 할당 요청을 만족시키기에는 가용하지 않았을 때 일어난다.
• 내부 단편화
  • 내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다.
  • 내부 단편화는 정량화 하기가 간단하다. 이것은 단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이다.
• 외부 단편화
  • 외부 단편화는 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리 할 수 있는 단일한 가용블록은 없는 경우에 발생한다.
  • 외부 단편화는 내부 단편화보다는 훨씬 더 측정하기 어려운데, 그것은 이전 요청의 패턴과 할당기 구현에만 의존하는 것이 아니라 미래의 요청 패턴에도 의존하기 때문이다.
  • 외부 단편화가 측정하기 어렵고 예측하기 불가능하기 때문에 할당기들은 대개 많은 수의 더 작은 가용블록들 보다는 더 적은 수의 더 큰 가용블록들을 유지하려는 방법들을 채택한다.

9.9.6 묵시적 가용리시트

• 헤더는 블록이 할당 되었는지 가용상태인지를 나타내기 위해 최소 중요비트(할당된 비트)를 사용한다. 헤더 다음에는 응용이 malloc을 불렀을 때 요구한 데이터가 따라온다. 데이터 다음에는 사용하지 않는 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다.
• 이러한 구조를 묵시적 리스트라고 부르는데 그것은 가용블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다. 할당기는 간접적으로 가용블록 전체 집합을 힙 내의 전체 블록을 다니면서 방문 할 수 있다. 어떤 특별히 표시한 마지막 블록이 필요하다.
• 묵시적 가용리스트의 장점은 단순성이다. 중요한 단점은 할당된 블록을 배치하는 것과 같은 가용리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것이다.

9.9.7 할당한 블록의 배치

• 요청한 블록을 저장하기에 충분히 큰 가용블록을 검색하는데 수행하는 방법을 배치정책이라고 한다.
• first fit : 가용리스트를 처음부터 검색해서 크기가 맞는 첫 번째 가용블록을 선택한다.
  • 장점 : 리스트의 마지막에 가장 큰 가용블록을 남겨두는 경향이 있다
  • 단점 : 리스트의 앞 부분에 작은 가용 블록들을 남겨두는 경향이 있어서 검색시간이 늘어난다.
• next fit이 first fit보다 최악의 메모리 이용도를 갖는다.
• best fit이 일반적으로 first fit이나 next fit 보다는 더 좋은 메모리 이용도를 가진다.

9.9.8 가용블록의 분할

• 할당기가 크기가 맞는 가용블록을 찾은 후에 가용블록의 어느정도를 할당할지에 대해 정책적 결정을 내려야 한다. 한 가지 옵션은 이 가용블록 전체를 사용하는 것이다. 간단하고 빠르지만 큰 단점은 내부 단편화가 생긴다는 것이다.

9.9.9 추가적인 힙 메모리 획득하기

• 할당기는 커널에게 sork 함수를 호출해서 추가적인 힙 메모리를 요청한다. 할당기는 추가 메모리를 한 개의 더 큰 가용블록으로 변환하고, 이 블록을 가용리스트에 삽입한 후에 요청한 블록을 이 새로운 가용블록에 배치한다.

9.9.10 가용블록 연결하기

• 오류 단편화(false fragmentation)를 극복하기 위해 실용적인 할당기라면 연결(coalescing)이라는 과정으로 인접 가용블록들을 통합해야 한다. 이 과정에서 언제 연결을 수행해야 할 지에 관한 중요한 정책결정을 해야 한다.
• 블록이 반환될 때마다 인접블록을 통합해서 즉시연결이나 일정 시간후에 가용블록들을 연결하기 위해 기다리는 지연연결을 선택할 수 있다.

9.9.11 경계태그로 연결하기

• 각 블록의 끝 부분에 풋터(footer)를 추가하는 것으로, 이 풋터는 헤더를 복사한 것이다. 만일 각 블록이 이와 같은 풋터를 포함하게 되면, 할당기는 시작 위치와 이전 블록의 상태를 자신의 풋터를 조사해서 결정할 수 있게되며, 이것은 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.
• 단점은 각 블록이 헤더와 풋터를 유지해야 하므로 만일 응용이 많은 작은 크기의 블록을 다룬다면 상당한 양의 메모리 오버헤드가 발생할 수 있다.

9.9.14 분리 가용리스트

• 단일 연결 가용블록리스트를 사용하는 할당기는 한 개의 블록을 할당하는데 가용블록의 수에 비례하는 시간이 필요하다. 할당시간을 줄이는 대표적인 방법으로 알려진 분리저장장치(segregated storage)는 다수의 가용리스트를 유지하며, 각 리스트는 거의 동일한 크기의 블록들을 저장한다. 기본적인 아이디어는 모든 가능한 블록 크기를 크기 클래스 size class 라고 하는 동일 클래스의 집합들로 분리하는 것이다.
• 할당기는 가용리스트의 배열을 관리하고, 크기 클래스마다 크기가 증가하는 순서로 한 개의 가용리스트를 가진다. 할당기가 크기 n의 블록이 필요하면 적당한 가용리스트를 검색한다. 만일 크기가 맞는 블록을 찾을 수 없다면, 다음 리스트를 검색하는 식으로 진행한다.

9.10 가비지 컬렉션

• 가비지 컬렉터는 더 이상 프로그램에서 사용하지 않는 블록들을 자동으로 반환하는 동적 저장장치 할당기다. 이러한 블록들을 가비지 라고한다. 자동으로 힙 저장장치를 반납하는 과정을 가비지 컬렉션이라고 한다. 가비지 컬렉션을 지원하는 시스템에서 응용프로그램은 명시적으로 힙 블록을 할당하지만, 결코 명시적으로 이들을 반환하지 않는다. 대신, 가비지 컬렉터가 주기적으로 가비지 블록을 식별하고 이 블록들을 가용리스트로 돌려주기 위해 적절하게 free를 호출한다.

9.10.1 가비지 컬렉터 기초

• 가비지 컬렉터는 방향성 도달 그래프로 메모리를 고려한다. 그래프의 노드들은 루트노드들과 힙노드들로 나눈다. 각 힙 노드는 힙 내 한 개의 할당된 블록에 대응된다. 방향성edge p→q는 블록 p내부의 위치가 블록 q내부의 위치를 가리킨다는 것을 의미한다. 루트노드는 힙으로의 포인터를 포함하는 힙에 속하지 않는 위치들에 대응된다.
• 어떤 루트노드에서 p로 edge가 존재한다면 p는 도달할 수 있다. 응용프로그램은 어떤 시점에서든 도달 할 수 없는 노드를 다시는 사용할 수 없는 가비지에 대응시킨다. 가비지 컬렉터의 역할을 이 도달성 그래프의 표시를 관리하는 것과 도달 불가 노드들을 free시켜 반환받고, 이들을 가용리스트로 돌려주는것이다.

9.11 C프로그램에서의 공통된 메모리 관련버그

9.11.1 잘못된 포인터의 역참조

• 한 프로세스의 가상 주소공간 내에 어떤 의미 있는 데이터로도 매핑되지 않은 큰 구멍들이 존재한다. 만일 포인터를 이 구멍들 중의 하나로 역참조 하려하면, 운영체제는 프로그램을 segmentation 예외로 종료한다. 또한, 일부 가상메모리는 읽기-가능만 허용되어 있다. 이 영역에 쓰려고 하면 보호 예외로 프로그램을 종료시킨다.

9.11.2 초기화되지 않은 메모리를 읽는 경우

• bss 메모리 위치들(초기화되지 않은 전역 C 변수들 같은)은 항상 로더에 의해 0으로 초기화 되며, 이것은 힙 메모리의 경우에는 그렇지 않다. 보편적인 에러는 힙 메모리가 0으로 초기화 한다고 가정하는 것이다.

9.11.3 스택 버퍼 오버플로우 허용하기

• 입력 스트링의 길이를 조사하지 않고 스택 상의 타깃 버퍼에 쓰려고 한다면 이 프로그램은 버퍼 오버플로우 버그를 갖게 된다.

9.11.4 포인터와 이들이 가리키는 객체들이 같은 크기라고 가정하기

• 한 가지 큰 실수는 객체를 가리키는 포인트들이 이들이 가리키는 객체들과 같은 크기라고 가정하는 것이다.

9.11.5 Off-by-One 에러 만들기

• 덮어쓰기 버그의 한 종류이다.

9.11.6 포인터가 가리키는 객체 대신에 포인터 참조하기

• C 연산자의 결합성과 우선순위에 대해 부주의하면, 포인터가 가리키는 객체 대신에 포인터를 잘못 조작하게 된다.
• 우선순위와 결합성에 대해 의심스럽다면 괄호를 사용해야 한다는 것이다.

9.11.7 포인터 연산에 대한 오해

• 또 다른 공통적인 실수는 포인터에 대한 산술연산이 반드시 이들이 가리키는 객체의 크기 단위로 수행되어야 하는 것이지 바이트 단위로 이루어지는 것이 아니라는 것이다.

9.11.8 존재하지 않는 변수 참조하기

• 더 이상 유효하지 않은 지역변수를 참조하게 되는 경우

9.11.9 가용 힙 블록 내 데이터 참조하기

• 이미 반환한 힙 블록 내 데이터를 참조한는 것이다.

9.11.10 메모리 누수 leak 유발

• 메모리 누수는 프로그래머가 할당된 블록들을 반환하는 것을 잊어서 힙에 가비지를 부주의하게 만들 때 일어나는 조용한 살인자다.
• 만일 leak이 자주 호출되면, 힙은 점차적으로 가비지로 가득 차게 되고, 최악의 경우 전체 가상 주소공간을 소모하게 된다. 메모리 누수는 특히 데몬, 서버와 같이 종료 되지 않는 프로그램들의 경우에 심각하다.

C++

Vector Container

• 자동으로 메모리가 할당되는 배열

Vector의 초기화

vector<자료형> 변수명 벡터 생성

vector<자료형> 변수명(숫자)	숫자만큼 벡터 생성 후 0으로 초기화
vector<자료형> 변수명 = { 변수1, 변수2, ..}	벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[] = {,}	벡터 배열(2차원 벡터) 선언 및 초기화(열 고정, 행가변
vector<vector<자료형>> 변수명	2차원 벡터 생성(열과 행 모두 가변)
vector<자료형>변수명.assign(범위, 초기화할 값)	벡터의 범위 내에서 해당 값으로 초기화

Vector의 Iterators

v.begin() 벡터 시작점의 주소 값 반환

v.end()

벡터 (끝부분 + 1) 주소값 반환

Vector Element Access(벡터의 요소 접근)

v.at(i) 벡터의 i번째 요소 접근(범위 검사o)

v.[i]	벡터의 i번째 요소 접근(범위 검사x)
v.front()	벡터의 첫 번째 요소 접근
v.back()	벡터의 마지막 요소 접근

• at과 []의 차이점
  • 둘 다 같은 n번째 요소 접근이지만 at는 범위를 검사하여 범위 밖의 요소에 접근 시 예외처리를 발생시킨다. []는 범위검사를 하지 않으며 예외처리를 발생시키지 않는다. 또한 해당범위 밖의 요소에 접근을 시도한다면 일반적인 디버깅(g++ or VC++)이 발생한다.

Vector에 요소 삽입/제거

v.push_back() 벡터의 마지막 부분에 새로운 요소 추가

v.pop_back()	벡터의 마지막 부분 제거
v.insert(삽입할 위치의 주소 값, 변수 값)	사용자가 원하는 위치에 요소 삽입
v.emplace(삽입할 위치의 주소 값, 변수 값)	사용자가 원하는 위치에 요소 삽입(move 로 인해 복사생성자 x)
v.emplace_back()	벡터의 마지막 부분에 새로운 요소 추가(move로 인해 복사생성자x)
v.erase(삭제할 위치) or v.erase(시작 위치, 끝 위치)	사용자가 원하는 index값의 요소를 지운다.
v.clear()	벡터의 모든 요소를 지운다.(return size =0)
v.resize(수정 값)	벡터의 사이즈를 조정한다.(범위 초과시 0으로 초기화)
v.swap(벡터 변수)	벡터와 벡터를 스왑한다.

Vector Capacity(벡터 용량)

v.empty() 벡터가 빈공간이면 true, 값이 있다면 false

v.size()	벡터의 크기 반환
v.capacity()	heap에 할당된 벡터의 실제크기(최대크기) 반환
v.max_size()	벡터가 system에서 만들어 질 수 있는 최대 크기 반환
v.reserve(숫자)	벡터의 크기 설정
v.shrink_to_fit()	capacity의 크기를 벡터의 실제 크기에 맞춘다.

삼항 연산자(ternary operator)

• 삼항 연산자는 다른 언어에는 존재하지 않는 C언어와 C++만의 독특한 연산자이다.

지속성 접근시간 민감한지 비트당 트랜지스터 수 비용

SRAM	YES	1X	NO	6	1000X
DRAM	NO(refresh)	10X	YES	1	1X

• C++에서 유일하게 피연산자를 세 개나 가지는 조건 연산자이다.
• 간단하게 if-else문을 대체할 수 있다.

문법

조건식 ? 반환값1 : 반환값2

• 물음표(?) 앞의 조건식에 따라 결괏값이 참(true)이면 반환값 1을 반환하고, 결괏값이 거짓(false)이면 반환값2를 반환합니다.

Keyword

메모리 할당 정책

• 메모리 할당 정책은 메모리 할당 및 해제를 처리하는 방법이나 알고리즘을 말한다. 메모리 할당 정책은 시스템의 성능과 메모리 사용의 효율성에 영향을 미친다.
• 종류
  1. first-fit : 가장 처음으로 충분한 크기의 빈 공간을 찾아 할당한다.
  2. next-fit : 이전 할당된 메모리의 위치부터 순차적으로 빈 공간을 검색해서 할당한다.
     1. next-fit이 first-fit보다 최악의 메모리 이용도를 갖는다는 것으로 밝혀졌다.
  3. best-fit : 충분한 크기의 빈 공간 중에서 가장 작은 공간을 선택해 할당한다.
  4. worst-fit : 충분한 크기의 빈 공간 중에서 가장 큰 공간을 선택해 할당한다.
  5. buddy allocation : 빈 공간을 2의 거듭 제곱 크기로 나누어 관리하고, 작은 공간을 찾아 큰 공간을 분할하거나 합치는 방식으로 할당한다.
  6. slab allocation : 고정된 크기의 객체들을 일정한 크기의 캐시로 관리하고, 할당 요청이 있을 대 해당 캐시에서 객체를 할당한다.

묵시적 리스트

• 모든 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다.
• 대부분의 할당기가 해당 정보를 블록 내부에 저장한다.
• 일반적인 방법으로는 추가적으로 1블록을 사용하여 블록 앞에 블록의 크기를 저장하는 방법이 있다.
  • 이때 추가적으로 사용되는 1워드를 헤더라고 한다.
  • 헤더는 블록 크기와 블록이 할당되었는지, 혹은 가용 상태인지를 인코딩한다.
• 헤더 다음에는 데이터가 존재한다.
• 데이터 이후에는 사용되지 않은 패딩이 따라올 수 있는데, 이들의 크기는 가변적이다.
• 이러한 구조를 묵시적 리스트라고 부르는데, 그것은 가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다.
  • 특별히 마지막 블록이 필요하다는 점에 유의해야한다.
  • 이를 에필로그 헤더라고 부른다.
• 장점
  • 단순하다
• 단점
  • 가용 리스트를 탐색해야 하는 연산들의 비용이 힙에 있는 전체 할당된 블록과 가용 블록의 수에 비례한다는 것이다.

명시적 리스트

• 가용 블록들을 이전 가용 블록과 다음 가용 블록을 가리키는 포인터를 가진 일종의 이중 연결 링크드 리스트 자료구조로 구성하는 방법이다.
• 가용 블록은 프로그램에서 사용되지 않기 때문에, 해당 자료구조를 구현하는 포인터들은 가용블록의 본체 내에 저장 될 수 있다.
• 할당된 블록의 구조는 묵시적 리스트 방식과 동일하며, 단지 가용 블록의 구조만 바뀌는 것에 유의해야 한다.
• first fit 할당 시간을 전체 블록 수에 비례하는 것에서 가용 블록의 수에 비례하는 것으로 줄일 수 있다.

demand-zero memory

• 필요할 때(demand) 할당하고 0으로 초기화해주는(zero) 메모리를 말한다.
• 어떤 자원을 요청하거나 동장을 요청했을 때, 그것이 정말 필요해질 때 까지 실제 자원을 할당하거나 동작을 실행하지 않는 것을 의미한다.
• 즉, 우리가 kernel에게 메모리를 할당해달라고 요청하면(sbrk) kernel은 거의 아무것도 하지 않고(특정한 VM영역이 할당되었다는 최소한의 표시만 해두고) 우리에게 할당이 끝났다고 알려준다. 실제 메모리는 할당되지 않은 상태로 남아있게 된다.
• 이렇게 되면 유저는 메모리가 할당된줄알고 해당 주소에 뭔가를 쓰거나 읽을텐데, 처음 읽거나 쓰려고 하는 순간 실제 메모리(페이지)가 할당되어있지 않기 때문에 page fault가 발생할 것이고, 그제서야 kernel은 사용하지 않는 메모리(페이지)를 할당하고 0으로 채운뒤에 유저가 원래 하려고 했던 명령어를 다시 실행하게 된다.