Skip to content

Commit 5b86c71

Browse files
102092102092
authored
Merge pull request #72 from java-squid/sigrid
운영체제 14주
2 parents f3fbfbe + 702076f commit 5b86c71

File tree

2 files changed

+150
-0
lines changed

2 files changed

+150
-0
lines changed

‎operating-system/memory-hierarchy/sigrid/README.md‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
# 메모리 계층 구조
2+
![](https://i.imgur.com/Ga7efAW.png)
3+
## 개요
4+
* 메모리 계층 구조는 메모리에 필요에 따라 여러 종류로 나누어 둠으로서, CPU가 메모리에 훨씬 빨리 접근하도록 유도하기 위함이다.
5+
* Registers, Cache: CPU 내부에 존재하므로, 빠르게 접근할 수 있다.
6+
* 캐시
7+
* ![](https://i.imgur.com/YIk9tLP.png)
8+
* Memory: CPU 외부에 존재하므로, Registers와 Cache보다 느리게 접근할 수 있다.
9+
* RAM: Random Access Memory. RAM은 어느 위치에 저장된 데이터든지 접근(읽기 및 쓰기)하는 데 동일한 시간이 걸리는 메모리이기에 ‘랜덤(Random, 무작위)’이라는 명칭이 주어졌다.
10+
* Hard Disk: 직접 CPU에 접근할 수 없다. CPU가 하드 디스크에 접근하기 위해서는, 하드 디스크의 데이터를 메모리로 이동시킨 후에야 메모리에 접근해야 한다. 따라서 매우 느리다.
11+
12+
## 특징
13+
### 비용적 측면
14+
* 메모리 구조에서 상층으로 갈수록 더 비싸진다.
15+
### 참조의 지역성 (Locality of Reference)
16+
* 자주 쓰이는 데이터는 자주 쓰이고, 그렇지 않은 데이터는 그렇지 않다. CPU는 자동으로 자주 쓰이는 데이터이고, 또는 자주 쓰일 것 같은 데이터를 캐시로 읽어온다.
17+
* 자주 쓰이는 데이터는, 전체 데이터 양에 비해 작은 양이다. 따라서, 캐시는 메모리보다 더 작아도 된다.
18+
### 속도적 측면
19+
* CPU와 가까이 있는 레지스터가 가장 빠르게 접근 가능하고, 밑으로 내려갈 수록 접근 속도가 느려진다.

‎operating-system/virtual-memory/sigrid/README.md‎

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
# 가상 메모리란?
2+
## 개요
3+
* 가상 메모리는 물리 메모리의 용량 한계를 극복하려는 목적을 지니고 있다.
4+
* 예를 들어, 물리 메모리가 100MB인데 200MB의 소프트웨어를 구동하고자 하는 것이다.
5+
* **당장 필요한 부분만** 메모리에 적재시켜 구동하는 방식을 이용한다.
6+
* 기본적으로 가상 메모리의 용량은 무제한이지만, 실질적으로는 물리 메모리의 용량에 국한된다. 가상 메모리의 용량은 **물리 메모리 + 스왑영역**이다.
7+
8+
## Demanding Paging
9+
![](https://i.imgur.com/ezgs1jj.png)
10+
* 페이징이란 **논리 메모리 == 가상 주소**를 fixed-size로 분할하는 것을 의미하고, 프레임이란 **물리 메모리**를 fixed-size로 분할하는 것을 의미한다. [참고](https://jhnyang.tistory.com/290)
11+
* 페이징 기법은 **고정 분할 방식**을 이용하는데, 물리 주소 공간을 **같은 크기** 로 분할하는 것을 의미한다.
12+
* 페이지와 프레임은 서로 크기가 같으므로, 1:1 매핑이 가능하다. 매핑 내역은 Page Table에 기록된다.
13+
* 현재 프로세스 실행에 요구되는 페이지만 메모리에 올리는 것을 **Demanding Paging**이라고 한다.
14+
* Page Table에는 Valid bit이 추가되어, 해당 페이지-프레임의 메모리 상 존재 여부를 나타낸다. 만약 현재 페이지가 메모리에 적재되어 있다면 1을, 적재되어 있지 않다면 0을 나타낸다.
15+
* 현재 페이지 2번이 메모리에 적재되어 있지 않고, Valid bit도 0으로 표시되어 있다. 페이지 2번을 메모리에 적재시키는 과정을 한 번 살펴보도록 하자.
16+
![](https://i.imgur.com/aGcbk30.png)
17+
* CPU에서 P1의 2번째 페이지에 접근하는데 valid bit값이 0이다. 그러면 CPU에 인터럽트 신호를 발생시켜서 OS 내부의 ISR로 점프한 후, 디스크 내부에 있는 프로세스 P1에 있는 2번째 페이지를 메모리에 할당하는 작업을 수행한다. **-> 과정 더 알아보기**
18+
19+
### Page Fault (페이지 실패)
20+
![](https://i.imgur.com/dBh57Ap.png)
21+
* CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 다시 말해서, 페이지 테이블의 valid bit가 0인 경우이다.
22+
* Page Fault가 발생했을 때 처리하는 과정이다.
23+
* 해당 페이지가 메모리에 있는 지 보기 위해 valid bit을 확인한다.
24+
* valid bit이 0이라면, CPU에 인터럽트 신호를 보내어 OS 내부의 해당 ISR로 jump한다.
25+
* 해당 ISR에서 디스크[backing store]를 탐색하여, 해당 프로세스의 페이지를 찾는다.
26+
* 해당 페이지를 비어있는 프레임에 할당한다.
27+
* 페이지 테이블에, 프레임 번호를 설정하고 valid bit이 1로 변경하여 해당 테이블을 갱신한다.
28+
* 다시 명령어로 돌아가서 실행한다.
29+
30+
### Pure Demanding Paging
31+
* 프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않는다.
32+
* 그러므로 프로그램을 실행하자마자 page fault가 발생한다. 즉, 순수하게 필요한 페이지만 올리는 것을 말한다.
33+
* Pure Demanding Paging의 장점은 메모리를 최대한 효율적으로 사용할 수 있다. 하지만 시작부터 page fault가 발생하므로 속도 면에서 느리다.
34+
35+
### Pre-paging
36+
* pure demanding paging과 반대 개념이다.
37+
* 프로그램을 실행할 때 필요할 것이라 판단되는 페이지를 미리 올리는 것이다.
38+
* 장점은 page fault가 발생할 확률이 적으므로 속도면에서 빠르지만, 단점으로 미리 올라간 페이지를 사용하지 않는다면 메모리가 낭비된다.
39+
40+
### Swapping & Demanding Paging
41+
* 공통점은 둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행한다.
42+
* 차이점은 Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동한다.
43+
44+
### Effective Access Time
45+
* Demanding Paging은 페이지 테이블에 해당 페이지가 없으면 backing store에서 메모리로 가져오는 과정이 있다. 따라서, 페이지 테이블에 해당 페이지가 있을 때와 없을 때 시간 차이가 발생한다.
46+
* 이러한 시간 차이를 고려하여 **평균적으로 어느 정도 소요되는지 계산하는 것을 유효 접근 시간**이라 한다.
47+
48+
```
49+
p: 페이지 부재 확률(probability of a page fault = page fault rate)
50+
Tm: 메모리를 읽는 시간
51+
Tp: Page fault가 발생했을 때 소요되는 시간(대부분 backing store(디스크)를 읽는 시간이 차지한다.)
52+
T = (1-p)Tm + pTp
53+
```
54+
```
55+
Tm = 200nsec (DRAM)
56+
Tp = 8msec (seek time + rotational delay + transfer time)
57+
T = (1-p)200 + p(8,000,000) = 200 + 7,999,800 * p
58+
p = 1/1,000 => T = 8.2usec (40배 정도 느림)
59+
p = 1/399,990 => T = 220nsec (10% 정도 느림)
60+
```
61+
* 페이지 부재의 확률은 극히 낮다. 지역성의 원리(Locality of reference)에 의하기 때문이다. 지역성의 원리는 시간적 지역성, 공간적 지역성이 있다.
62+
* **시간적 지역성**: CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것을 의미한다.
63+
* **공간적 지역성**: CPU는 어느 메모리 공간을 읽을 때, 인접한 범위 내에서 읽는다는 것을 의미한다. 특히, 절차적 프로그래밍으로 구현되어 있을 경우 순서대로 읽는 경우가 빈번하다.
64+
65+
## Page Replacement
66+
* Demanding Paging은 요구되는 페이지만 backing store에서 가져온다. 하지만 프로그램들이 계속 실행함에 따라, 요구 페이지도 계속 늘어나게 된다. 그러다보면, 언젠가는 메모리가 가득 차게 될 것이다.
67+
* 여기서, 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면, 이미 메모리에 적재되어 있는 backing store로 보내고 -- 이를 **page-out**이라고 한다.
68+
* 한 편으로, 이미 backing store로 page-out이 된 페이지를 **victim page**이라고 한다.
69+
70+
## Victim Page
71+
![](https://i.imgur.com/vJme440.png)
72+
73+
* 그러면 어느 페이지를 탈락시켜야 할 것인가? 메모리에 올라가 있는 페이지 중, CPU에 수정(modify)되지 않는 페이지를 골라야 한다.
74+
* 수정되지 않은 페이지는 page-out이 될 때, backing store에 쓰기(write) 연산을 하지 않아도 된다. backing store는 읽기(read) 시간도 느리기 때문에, 쓰기 연산까지 하면 시간이 더욱 느려질 것이다.
75+
* 해당 페이지가 수정되었는 지, 수정되지 않았는지 파악하기 위하여 페이지 테이블에 modified bit(dirty bit)를 추가하여 이를 검사한다. 해당 페이지가 수정되었다면 modified bit을 1로, 수정되지 않았다면 0으로 둔다.
76+
* 만약 수정되지 않은 페이지가 여러 개가 있다면, 랜덤으로 하거나 FIFO로 하는 등 알고리즘을 경우에 따라 선택할 수 있다.
77+
78+
![](https://i.imgur.com/dl99Unh.png)
79+
80+
## Other Paremeters in Page Table Entry
81+
* Page base addresses
82+
* Flag bit
83+
* Accessed bit: 접근이 있었나?
84+
* Dirty bit: 내용이 수정된 적이 있나?
85+
* Present bit: 현재 페이지에 할당된 프레임이 있나?
86+
* Read/Write bit: 읽기와 쓰기 권한이 있나?
87+
88+
## 페이징 기법의 동적 주소 변환 과정
89+
* 가상 메모리의 스왑 공간에 있는 가상 주소를 물리 메모리의 실제 주소로 변환하는 과정을 **동적 주소 변환** 이라고 한다.
90+
![](https://i.imgur.com/hh38gWH.png)
91+
* 가상 주소를 물리 주소로 변환하는 과정
92+
1. 가상 주소 30번지가 어느 페이지에 있는지 찾음 -> 페이지 3의 0번째 위치
93+
2. 페이지 테이블의 페이지 3으로 가, 해당 페이지가 프레임 1에 있음을 알아냄
94+
3. 물리 메모리 프레임 1의 0번째 위치에 접근 -> 가상 주소 30번지의 물리 주소
95+
* 가상 주소에 값을 저장할 때의 주소 변환 과정
96+
![](https://i.imgur.com/QOargpt.jpg)
97+
1. 가상 주소 18번지가 어느 페이지에 있는지 찾음 -> 페이지 1의 8번째 위치
98+
2. 페이지 테이블의 페이지 1로 가, 해당 페이지가 프레임 3에 있음을 알아냄
99+
3. 프로세스가 저장하려는 값을 프레임 3의 8번 위치에 저장
100+
* 부족한 물리 메모리의 크기 == 스왑 영역으로 대체
101+
* 페이지 테이블 수는 프로세스의 크기와 일치
102+
103+
### 페이지 테이블의 매핑 방식
104+
![](https://i.imgur.com/MauGglv.png)
105+
106+
#### 직접 매핑
107+
* 페이지 테이블 전체가 운영체제 영역에 위치하는 경우
108+
* 특징
109+
* 모든 페이지 테이블이 물리 주소에 있다.
110+
* 변환속도가 빠르다.
111+
* 메이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터(PTBR)가 가지고 있다.
112+
#### 연관 매핑
113+
![](https://i.imgur.com/uIeNT7d.png)
114+
* 페이지 테이블 전부가 스왑영역에 위치하는 경우
115+
* 특징
116+
* 일부 테이블만 무작위로 선정하여 물리 메모리로 가져온다.
117+
* Translation Lookasider Buffer (TLB)
118+
![](https://i.imgur.com/4xrEkMC.png)
119+
* 가상 메모리 주소를 물리적인 주소를 변환하는 속도를 높이기 위해 사용하는 버퍼
120+
* 페이지 테이블은 주 기억장치(물리)에 기본적으로 위치하므로, 페이지 테이블에 접근하는 과정 하나와 기억 장치에 필요한 데이터 두 번을 액세스하는 과정이 필요함
121+
* TLB가 hit일 경우 가상 주소를 물리 주소로 변환하기 위한 페이지 테이블에 접근할 필요가 없음.
122+
* TLB는 메모리가 아닌 프로세서에 내장되어 있기에 훨씬 빠름.
123+
* TLB의 프레임 주소를 토대로 데이터를 불러오기 위한 1번의 메모리 접근만 있으면 됨.
124+
* 탐색 과정
125+
* TLB를 사용하여 페이지가 물리 메모리(프레임)에 올려져 있는지 확인한다.
126+
127+
## Reference
128+
* https://velog.io/@codemcd/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-15.-%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%AC
129+
* https://velog.io/@thalals/OS-8.%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC%EC%9D%98-%EA%B8%B0%EC%B4%88
130+
* https://velog.io/@kjh3865/%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-Virtual-Memory
131+
* http://jidum.com/jidums/view.do?jidumId=473

0 commit comments

Comments
 (0)