
지난 번엔 논리 메모리 주소를 물리 주소로 변환하는 것에 대해 배웠는데, 이 작업은 운영체제가 전혀 관여하지 않는다.
이번엔 운영체제가 관여하는 가상 메모리 시스템의 메모리를 효율적으로 관리하고자 사용하는 페이지 replacement algorithm에 대해 알아본다.

## Demanding Paging

: 실제로 필요할때 페이지를 메모리에 올림

- IO 양 감소, 메모리 사용량 감소(한정된 메모리를 효율적으로 사용 가능), 빠른 응답시간, 더 많은 유저 수용

![메모리에 없는 페이지의 페이지 테이블](/images/os/vm1.png)

- 처음엔 모든 페이지 엔트리가 invalid로 초기화되어있음.
- Valid bit(당장 필요한 부분)은 demanding paging으로 메모리에 이미 올라가 있다 (4,6,9)
- invalid bits는 backing store(스왑 영역)에 있다.
- read나 write의 참조가 일어나 주소를 변환 해야할 때 invalid bit이 set되어있으면 page fault 났다고 함. (그럴때 os가 처리함)

### page fault

![페이지 폴트의 순서](/images/os/vm2.png)
![페이지 폴트 대처법](/images/os/vm3.png)

- refer(1)하려고 했는데 invalid(메모리에 올라와있지않으면) trap 발생해 cpu가 운영체제로 넘어감
- 운영체제가 스왑영역에서 페이지 올림. 그다음 invalid를 valid로 바꾸고(5) restart(6)
- page fault는 자주 발생하지 않는다. 하지만 한번 발생하면 운영체제가 넘어가고, 하드웨어적으로 처리하느라 엄청난 시간(오버헤드)이 소모됨

### 빈 페이지가 없는 경우(=Free frame이 없는 경우)

- Page replacement 필요함. 곧바로 사용하지 않을 페이지를 쫓아내고, 어떤 프레임을 뺏어올지 결정해야함
- 동일한 페이지가 여러번 메모리에서 쫓겨났다가 다시 들어올 수 있음
- Replacement algorithm: page fault rate을 최대한 낮추는게 목표
- 위 알고리즘은. 주어진 페이지 레퍼런스 string에서 얼마나 page fault를 내는지로 조사함

## 페이지 Replacement 알고리즘의 종류

### Optimal Algorithm

![옵티멀 알고리즘](/images/os/vm4.png)

- page fault를 가장 적게 하는 알고리즘 (다른 알고리즘의 성능의 upper bound를 제공) / 가장 먼 미래에 참조되는 페이지를 쫓아낸다
- 미래에 참조되는 페이지를 모두 안다고 가정하고 (실제 시스템에선 사용될 수 없으므로 오프라인 알고리즘이라고도 불림) 운영
- 빨간색: 페이지 폴트나는 경우, 연보라: 페이지 폴트 없이 메모리에서 직접 참조된 경우
- 7번째 예시의 경우 5가 필요한데 메모리에 없음. 그니까 가장 먼미래에 참조되는 4를 쫓아낸다.

### FIFO Algorithm

![FIFO 알고리즘](/images/os/vm5.png)

- 이 알고리즘의 나쁜 성질: 메모리 프레임 크기를 늘리면 성능이 더 나빠짐 (FIFO Anomaly라고 부름)

### LRU(Least Recently Used) Algorithm

![LRU Algorithm ](/images/os/vm6.png)
![LRU Algorithm 구현법](/images/os/vm8.png)

- 과거를 중요하게 생각
- 최근은 아니더라도 자주 참조되는 페이지를 지울 우려가 있음
- 구현방법: 참조시점대로 페이지를 LinkedList 형태로 정렬함. 새 참조가 들어오면 중간에 끼우기만 하면됨. 쫓아낼때도 비교 필요 없이 맨 위에 있는 페이지(LRU)

### LFU(Least Frequently Used) Algorithm

![LFU 리스트로 구현](/images/os/vm9.png)
![LFU 힙으로 구현](/images/os/vm10.png)

- 참조횟수가 가장 적은 페이지를 지움
- 최저 참조횟수인 페이지가 여럿이면 임의로 선정하거나 성능향상을 위해 가장 오래전에 참조된 페이지를 지우게 구현할수도 있음
- 장점: LRU처럼 직전만 보는게 아니라 장기적인 시간 규모를 보기때문에 페이지의 인기도를 좀 더 정확히 반영 가능
- 단점:
- 구현방법: LRU와 달리 새 참조가 들어오면 다른 참조의 횟수와 비교를 해서 자리를 정해야함 => 그래서 list 말고 힙을 사용 / root를

![LRU, LFU 알고리즘 예제](/images/os/vm7.png)

- 둘다 장단점이 있음.

가장 참조횟수가 적은 페이지를 운영체제는 알 수 없다. 왜냐면 프로세스가 요청한 페이지가 이미 메모리에 있으면 cpu가 운영체제에게 넘어가지않음. 그래서 접근 시간을 os가 모름. 그러나 페이지 폴트가 나면 cpu가 운영체제로 넘어가 언제 그 페이지가 메모리로 올라왔는지 등의 정보를 얻게 됨.  
사실 위 알고리즘을 os가 정렬하고 해야하는데 페이지가 이미 메모리에 존재하는 경우엔 os가 관련 정보를 알 수 없다. page fault 시에만 알 수 있다.
-> 클락 알고리즘 등장

## cache

- 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해두었다가 이후에 요청이 오면 캐쉬에서 바로 서비스
- paging system 외에도 캐시메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용
- 시간 제약: 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리면 실제 시스템에서 사용 불가

## Clock Algorithm

![클락 알고리즘](/images/os/vm11.png)
![클락 알고리즘의 시계모양 예시](/images/os/vm12.png)

- LRU의 근사 알고리즘 (second change 알고리즘)
- 레퍼런스 빝을 운영체제가 바꾸면서 지나감. 레퍼런스 비트가 0이라는건 시계바늘이 한번 도는 동안 참조가 한번도 없었다는 것
- 하드웨어: refer bit을 1로 바꿈/ os는 이 비트가 0인걸 쫓아냄
- modified bit과 reference bit를 함께 사용하면 좋다.

## page frame의 allocation

![페이지 프레임 할당](/images/os/vm13.png)

- 지금까지는 프로그램 여러개가 물리메모리에 같이 올라가있었다. 쫓아낼땐 어떤 프로세스에 있는 건지 무관하게 쫓아냈다. 하지만 그 프로세스가 원활하게 실행되려면 다 같이 올라와있는게 좋다.
- equal / proportional / priority allocation

## global vs. local replacement

- 전역: 교체시 다른 프로세스에 할당된 프레임을 뺏어올 수 있음, 프로세스별 할당량 조절하는 방법임, FIFO, LRU, LFU 등의 알고리즘을 전역으로 사용시에 해당
- 로컬: 자신에게 할당된 프레임 내에서만 교체, 여러 알고리즘을 프로세스 별로 운영시

## Thrashing

: 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당받지 못한 경우 발생

![thrashing diagram](/images/os/vm14.png)

- IO 하는 동안 CPU가 놀기 때문에 CPU 사용률이 처음에 낮았다가, 멀티 프로그래밍이 더해질수록 CPU 사용률이 높아짐
- 그러다가 thrashing이 발생하면 cpu 사용률이 떨어지고 page fault가 빈번히 발생
- 운영체제가 보기엔 CPU 사용률이 낮네? 프로그램 더 올려야겠다. => 프로세스가 추가되면 프로세스당 할당된 프레임 수가 더욱 줄어들고, 프로세스는 swap in out하느라 바빠지고 CPU는 할일이 없어짐 (시스템이 비효율적이게 됨)

### 전역 교체 방법1. working set model

![working set model](/images/os/vm15.png)
![워킹 셋 결정하는 법](/images/os/vm17.png)

- working set: 프로세스실행을 위해 한꺼번에 메모리에 올라와있어야하는 페이지, 집중적으로 참조되는 페이지들의 집합
- 프로세스의 워킹 셋 전체가 메모리에 올라오지 않으면 모든 프레임을 반납한 후 swap out
- 이 워킹 셋이 한번에 메모리에 올라와있도록 보장함으로써 page fault가 덜 일어나게 함 / thrashing 방지

![워킹 셋 결정하는 법](/images/os/vm16.png)

- 과거 델타 시간동안 참조된 페이지의 집합을 보고 워킹 셋으로 간주 / 즉, 참조된 후 델타 시간동안 해당 페이지를 메모리에 유지한 후 버림
- 워킹 셋의 크기는 그때그때 바뀐다. (t1, t2를 보면 다르다는 걸 알 수 있음)

### 전역 교체 방법2. PFF(Page-Fault Frequency) Scheme

![워킹 셋 결정하는 법](/images/os/vm18.png)

- page fault rate의 상한값, 하한값을 두고 상한값을 넘으면 프레임을 더 할당. 하한값 이하면 할당 프레임수를 줄임
- 프로그램의 상태에 따라 가파른 정도가 다름.

## Page Size가 너무 작으면?

- 페이지 수 증가(더 잘게 썰게 되니까), 테이블의 크기 증가, 대신 internal fragmentaion 감소
- 꼭 필요한 정보만 메모리에 올라와 메모리 사용하기 효율적
- Disk transfer의 효율성 감소 (seek/rotation vs. transfer): 페이지 폴트 때마다 seek해야해서
- 요즘은 페이지를 크게 하는게 트렌드임


가상 메모리 시스템의 페이지 교체 알고리즘을 알아보자


팀을 이뤄서 롤링페이지 웹앱을 만드는 사이드 프로젝트를 하고 있다. 
나는 프론트엔드 개발을 맡았다. 그래서 백엔드 팀원들과 같이 API 명세서를 작성하는데, 
롤링페이지의 색과 폰트를 미리 정해두고 각각에 번호를 부여해 1,2 이런식으로 데이터를 전달해주자는 이야기가 나왔다. 
그런데 뭔가 말로 설명하지 못할... 찜찜함이 있어서 동료 개발자인 웨지님에게 물어보니 이런 답이 왔다.

## 클라이언트에게 불친절한, 서버 의존적인 API

![웨지님](/images/blog/2203/apitip.png)

카톡을 보고 무릎을 탁 쳤다!! **클라이언트에게 불친절한, 서버 의존적인 API** !!!

폰트나 컬러의 경우 폰트명, 헥사코드처럼 거의 합의된 형태의 이름/표현법이 있는데 이걸 코드로 관리하는게 비효율적으로 느껴졌다. '굳이...?' 싶었던 것이다.

번거로울 뿐더러 폰트와 컬러 데이터를 이름 대신 코드로 관리해 서버 측에서 다시 해석해야하기 때문에 서버 의존적이라고도 할 수 있다. 
사용자가 폰트나 컬러를 선택해야하는 부분의 프론트 개발을 할 때 '이 코드가 무슨 색/폰트였지?' 싶어 찾아보게 될 게 뻔했다.

개발보다 기획과 설계가 더 어렵다. 서버/클라이언트 한 쪽에 과한 부담이 가지 않도록 신경 쓰며 개발해야겠다. 


적절한 표현을 찾았을 때의 스프라이트 샤워

클라이언트에게 친절한 백엔드 API 만들기


지난번에 사용자 프로세스를 메모리에 연속적으로 올리는 방법을 배웠다.  
프로그램을 연속적으로 메모리에 할당하게 되면 시작 논리 메모리 주소만 알면 실제 물리 메모리의 주소로 변환하기 아주 쉬웠다.  
이번엔 메모리를 나눠 피지컬 메모리에 불연속으로 할당하는 기법을 배워본다.

## 불연속 할당

### segmentation: 프로그램을 의미있는 단위별로 자름

- 코드/데이터/스택 세그먼트로 나누거나 더 잘게 자를 수도 있음.
- 크기가 균일하지 않아 dynamic storage allocation problem 문제 일어남

### 페이징: 프로세스의 virtual memory를 같은 크기로 잘라 페이지 단위로 나눔

![페이징 기법 설명](/images/os/osmm6.png)

- 가상 메모리의 내용이 페이지 단위로 **불연속적** 으로 저장됨
- hole의 크기가 균일하지 않은 것을 걱정할 필요 없음
- 주소 바인딩(변환)을 페이지별로 해야함/ 일부는 backing storage에, 일부는 피지컬 메모리에 저장.

### 페이징 테이블

![페이징 예시](/images/os/osmm8.png)

- 각각의 프로세스별로 존재하며/ 논리 메모리가 물리적 메모리의 어느 부분에 들어가 있는가를 매핑해둔 테이블
- 3번 페이지는 7번 프레임에 들어가있다. (페이징 프레임: 페이지가 들어가있는 공간)
- 페이지 테이블은 메인 메모리에 상주.

![페이징 예시](/images/os/osmm10.png)

- Page-table base register (PTBR)가 페이지 테이블을 가리킴
- Page-table limit register (PTLR)가 테이블 크기를 보관
- 모든 메모리 접근 연산에는 2번의 메모리 액세스가 필요 (페이지 테이블 접근 1번, 실제 데이터/명령어 접근 1번)
- 속도 향상을 위해 associative register(TLB) 사용
  
#### TLB (Translation Look-aside Buffer)

- 주소 변환을 위한 **캐시** 메모리. 고속의 lookup hardware cache!
- 페이징 테이블의 일부 (자주 조회되는 주소)를 저장
- 병렬 검색. tlb에 없으면 TLB Miss 라고 함.
- TLB의 전체를 검색해봐도 없으면 메인 메모리에 있는 page table에서 프레임 번호를 얻음.
- TLB는 컨텍스트 스위칭 때 flush

## 2단계 페이지 테이블

![2단계 페이징](/images/os/osmm11.png)

### 왜 필요한가?

- 현대의 컴퓨터는 주소 공간이 매우 넓은 프로그램을 지원한다. 그러나 대부분의 프로그램이 그 주소공간 중 일부만 사용하므로 페이지 테이블 공간이 심하게 낭비된다.

### 해결 방법

- 페이지 테이블 자체를 페이지로 구성 (다단계 페이징 기법)
- 사용하지 않는 주소 공간에 대한 외부 페이지 테이블은 NULL로 설정해 대응하는 내부 페이지 테이블을 생성X
- 페이지 테이블을 두단계 거침. 속도가 빨라지진 않지만 페이지 테이블을 위한 공간이 줄어듦
- 메모리 공간은 결국 적게 쓰지만 페이지 테이블의 수가 증가하므로 시간이 소요됨 (tradeoff)  

![2단계 페이징](/images/os/osmm7.png)

- 논리 주소: P1(외부 페이지 테이블 인덱스) + P2(내부 페이지 테이블 인덱스) + d(페이지 오프셋)
- 최종 물리 메모리 주소: 외부 페이지 tb에서 P1만큼 떨어진 주소에서 내부 페이지 테이블 주소 얻고 여기서 P2만큼 떨어진 위치에서 페이지 프레임 위치를 얻은 후 해당 프레임에서 d만큼 떨어진 곳


지금까진 메모리 관리하는 법(Memory Management)을 배우면서 CPU가 주는 논리 메모리 주소를 물리 주소로 바꾸는 방법을 배우고 있다.
그 중에서도 불연속 분할 방법인 페이징을 배웠다.
이번엔 단계를 여럿으로 나눠 페이징을 하는 방법에서부터 시작한다!

## 다단계 페이징

- 주소 공간이 커지면 다단계 페이지 테이블 필요
- TLB(주소 변환 돕는 캐시 메모리)로 메모리 접근 시간을 줄일 수 있음

![4단계 페이지 테이블 사용하는 경우 예시](/images/os/mm1.png)

## 페이지 테이블의 Valid, Invalid 비트

![valid, invalid bits](/images/os/mm2.png)

- 페이지 테이블 엔트리에는 사용되지 않는 비트여도 페이지 테이블을 만들어둔다.
- 테이블이라는 자료구조 특성상 위에서부터 천천히 접근하기 때문에 다 만들지만 사용을 안 하므로 i로 표시
- 0번 페이지가 2번 프레임에 있다.

## 메모리 보호

![protection bit](/images/os/mm3.png)

- 페이지 테이블의 각 엔트리마다 protection 비트와 Valid-invalid 비트가 있다.
- protection bit: 페이지 접근 권한

## 지금까지의 문제

- 페이지 테이블의 큰 용량
- 페이지에 메모리가 없어도 프로세스별로 모든 논리 주소에 대응하는 모든 페이지에 대해 페이지 테이블 엔트리를 만들어야함.

## Inverted Page Table (역방향 페이지 테이블)

![역방향 페이지 테이블 그림](/images/os/mm4.png)

- 시스템에 하나의 페이지 테이블만 존재.
- 페이지 프레임 하나당 하나의 페이지 테이블 엔트리 / 페이지테이블 엔트리가 물리메모리의 프레임 개수만큼 존재
- **기존의 논리 페이지 번호를 보고 페이지 테이블에서 그만큼 떨어진 엔트리에 가는 방법이 불가능**
- 엔트리를 다 검색해서 pid, p가 있는 엔트리를 찾고 물리 주소를 얻는다. => 단점임. 좋은 점은 페이지 테이블의 크기가 줄어든다는 것임.

## Shared Pages (페이지 공유)

![공유된 페이지](/images/os/mm5.png)

- **공유되는 부분을 같은 프레임에, 한 카피만 물리적 메모리에 올림**
- 공유되는 부분: 재진입 가능한 코드Re-entrant code (pure code) 라고 한다.
- shared code의 조건 1: **Re-entrant code는 read-only!**
- shared code의 조건 2: **동일한 logical addr에 위치해야함**

## Segmentation : 프로그램을 의미별로 나눔

- 프로그램은 의미 단위인 여러개의 세그먼트로 구성
- 세그먼트: logical unit (논리적인 단위)
- 작게는 프로그램의 함수 하나하나가 세그먼트일수도, 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
- 일반적으로 code, data, stack 부분이 하나의 세그먼트로 정의됨
- e.g. main(), function, global 변수, stack, symbol table, arrays, etc.

## Segmentation Architecture

- 논리 주소: ```<segment-number, offset>```
- paging할 때와 비슷하다. offset의 범위 안에 있지 않으면 trap을 발생시킨다.

![세그먼트 하드웨어](/images/os/mm6.png)

### Segment table

- 각각의 테이블 엔트리는 base(세그먼트 물리주소 시작주소)와 limit(세그먼트 길이)를 가짐
- STBR(Segment-Table Base Register), 프로그램이 쓰는 세그먼트의 갯수를 기억하는 STLR(ST Limit Register)
- 페이지 테이블과 다른 점: **limit이 있음. 페이징 기법은 페이지의 크기가 균일해 결국 오프셋 크기=페이지 크기인데 세그먼트의 경우 의미별로 자르는 거라 길이가 다 다르다(offset보단 작아야함). 그리고 페이징 기법은 시작 주소가 프레임 번호면 되는데(물리적 메모리도 같은 크기의 프레임으로 나눠져있기 때문) 세그먼트 기법에서는 베이스 위치로 어디서 프레임이 시작하는지 정확한 바이트 주소를 줘야 하기 때문.**

### Protection

- 각 세그먼트 별로 프로텍션 비트가 있음
- Valid bit가 0이면 Invalid bit

### 공유

- 의미 단위로 자르기 때문에 페이징보다 공유, 보안에 있어 훨씬 효과적임

### 할당 (allocation)

![세그먼트 할당](/images/os/mm7.png)

- segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생 (external frag)
- segment의 크기가 각기 달라 hole이 발생하는 게 segmentation의 약점

![세그먼트 공유](/images/os/mm8.png)

## 페이징 + 세그먼테이션

- 세그먼트 하나가 여러개의 페이지로 구성됨. 메모리에 올라갈때 페이지 단위로 쪼개져서 올라감
- 세그먼트 테이블 엔트리가 세그먼트의 base 주소를 가지지 않고! 세그먼트를 구성하는 페이지 테이블의 base 주소를 가짐
- d 오프셋이 세그먼트의 길이 이내여야만 유효함 / **d'는 페이지 안에서 얼마나 떨어져있는지 오프셋**


페이징 테이블과 다단계 페이징 기법, 세그멘테이션 기법을 알아본다.

운영체제 프로세스 메모리에 불연속적으로 할당하기


메모리 참조를 하기 위해선 CPU가 논리 메모리 주소를 주면 물리 메모리 주소로 바꿔야한다. 
하드웨어가 해줘야하는 역할들과 메모리 주소 바인딩 방법에 대해 배워보자.

## 논리 주소 vs. 물리 주소

### 논리 주소 (virtual address)

- 프로그램이 실행되면 생기는 독자적인 주소 공간
- 각 프로세스마다 0번지부터 시작
- **CPU가 보는 주소**

### 물리 주소

- 메모리에 실제 올라가는 위치

### 주소 바인딩

- 주소를 결정하는 것
- symbolic address(컴파일)-> logical address(실행을 위해 주소 변환)-> physical address
- 프로그래머 입장에선 숫자가 아닌 symbolic address를 사용.

![주소 바인딩 예시](/images/os/osmm1.png)

- 소스코드: 심볼릭 주소(A,B)가 쓰임. "A,B를 더한 후 C로 점프하라"
- 실행파일: 심볼릭 주소가 논리 주소(20,30)로 바뀜. 각각의 문장이 메모리 0번지~40번지에 들어감.
- 실행시작: 물리적 메모리에 올라간다(= 주소 바인딩된다.)

## 주소 바인딩의 시점

### 컴파일 시점 바인딩

- 컴파일 시점에 이미 물리적 메모리 주소가 결정됨 => 컴파일러가 절대 코드(absolute code) 생성
- 메모리 주소 시작 위치 변경시 재컴파일 해야함
- 실행파일에 있는 `Add '20,30'` 이 논리 주소가 그대로 사용됨. -> **비효율적**
- 컴퓨터 안에서 프로그램이 1개만 실행될 때 그나마 나음

### 실행 시점 바인딩 (Load time)

- 프로그램이 실행 시작되면 물리적 메모리 주소 결정됨
- 로더의 책임 하에 물리적 메모리 주소 부여
- 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우에 가능, 빈 위치에는 실행 시 어디든 올라갈 수 있음

### 런타임 바인딩

- 실행시에 프로세스 메모리 주소가 결정되는건 로드타임 바인딩과 같으나 **프로그램 실행중에도 주소가 바뀔 수 있음**
 (메모리에서 쫓겨난다거나)
- CPU가 주소를 참조할 때마다 바인딩이 어디 됐는지 체크해봐야한다. (address mapping table)
- 주소 참조시마다 바인딩 위치 확인하려면 하드웨어의 지원이 필요함 (base and limit registers, MMU)
- MMU가 주소 변환을 그때그때 해준다.

#### CPU는 물리 주소를 바라볼까?

CPU가 하드웨어라 물리 주소를 바라볼 것 같지만 바라보는 주소는 논리 주소다.  
프로그램이 실행돼 메모리에 올라가도 명령어 코드에 있는 주소는 논리 주소다(load time binding).  
메모리에 올라갈때 시작 위치(`500~`)는 바뀌지만 그 안의 주소는 논리주소로 남아있기 때문임.  

### MMU (Memory Management Unit)

- 논리 주소를 물리 주소로 매핑해주는 하드웨어
- 2개의 레지스터 사용 (base(relocation) register + limit register)
- 방법: 사용자 프로세스가 CPU에서 수행되며 생성하는 모든 주소값에 base register의 값을 더한다.
  
#### MMU 동작 원리 (Dynamic Relocation)

![dynamic relocation](/images/os/osmm2.png)

- 프로세스 P1은 논리주소: `0~3000번지` / 물리주소: `14000번지~`
- CPU 왈: 0번지 ~ 346번지 주셈  
=> 프로그램의 논리주소(346)+시작위치(14000) = 물리주소(14346)

#### 리밋(Limit) 레지스터

- 논리 주소 범위(끝)를 기억한다.
- 만약 악의적인 프로그램이 **실제 자기가 있지 않은 논리 주소를 달라고 하면?** 물리주소가 달라진다. 
=> 다른 프로그램의 피지컬 메모리 주소 주는 걸 방지하기 위해 리밋 레지스터를 사용

##### CPU가 논리 주소로 요청 -> 논리 주소가 리밋 레지스터의 범위 내에 있는지 확인 
-> 리밋 레지스터 범위를 벗어나면 트랩(소프트웨어 인터럽트) 발생시킴 -> 악의적 접근이 아니었으면 relocation(base) register로 주소 변환

=> 그 결과 프로그램은 논리 주소만 다르고, 실제 물리 주소는 알 필요가 없음.

## Dynamic Loading (동적 로딩)

- 프로세스 전체를 메모리에 미리 다 올리는 게 아니라 해당 **루틴이 호출되면 메모리에 로드**
- 메모리를 효율적으로 사용 가능
- 가끔씩 쓰는 많은 양의 코드를 쓸 때 유용 (e.g. 오류 처리 루틴)
- 운영체제가 지원하는게 아니라 라이브러리를 지원해주면 프로그래머가 프로그램 내에 구현

## Overlays (매뉴얼 오버레이)

- 프로세스의 실제 필요한 정보만 메모리에 올림
- 프로세스의 크기가 메모리보다 클 때 유용
- 프로그래머가 직접 메모리에 올렸다 내렸다~ 구현하는거고 프로그래밍이 매우 복잡

## 스와핑

- 프로세스를 일시적으로 backing store로 내쫓는 것
- 중기 스케줄러(스와퍼)가 우선순위 낮은 프로세스를 골라서 swap out
- `swap out`: backing store(swap area)로 내쫓음
- `swap in`: backing store(swap area)에서 다시 불러들임
- 컴파일/ 로드 타임 바인딩이면 돌아올 때 메모리 원래 위치로 돌아와야하기 때문에 별로 쓸데 없음.
- **런타임 바인딩할 때 써서 추후 빈 메모리 영역 아무데나로 가져오는게 가장 효율적임**
- 메모리에서 상당히 방대한 양을 내쫓거나/ 가져오는 거기 때문에 디스크 접근하는 시간의 대부분이 데이터 전송 시간(transfer time)이다. swap 되는 양에 비례함.

## Linking

- 프로그램을 작성하고 컴파일한 후 그 컴파일 된 파일들을 모아 실행파일로 만드는 것

### Static Linking

- **라이브러리가 프로그램의 실행 파일 코드에 포함됨** -> 실행 파일의 크기가 커짐
- 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 (e.g. `printf` 함수의 라이브러리 코드)

### Dynamic Linking (동적 연결)

- 라이브러리가 실행파일 코드에 들어가지 않고 **실행 시에 동적 연결됨**
- 라이브러리 호출 부분에 **라이브러리 루틴의 위치를 찾는 stub**이라는 작은 코드를 둔다.
- 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고, 없으면 디스크에서 읽어온다
- 운영체제의 도움이 필요

## 물리적 메모리

![allocation of physical memory](/images/os/osmm3.png)

- 연속 할당: 프로세스 하나가 메모리의 연속적인 공간에 적재됨
- 불연속 할당: 프로세스 하나를 나눠서 메모리의 여러 영역에 분산해 올림

## 연속 할당

![메모리 연속 할당](/images/os/osmm4.png)

### 고정 분할 방식

- 프로그램이 들어갈 물리적 메모리 영역을 미리 영구적으로 나눠놓음 (partition)
- 융통성이 없음. 최대 수행 가능한 프로그램의 크기가 제한되어있음.
- fragmentation(조각) 발생: 프로그램B가 분할3에 들어갔지만 남음. 프로그램B에게 할당됐지만 사용 안되는 부분 등

### 가변 분할 방식

- 분할의 크기, 갯수가 동적으로 변함
- B가 끝나고 D가 수행되는데 B가 들어갔던 부분은 D에게는 작아서 B가 끝나도 다른 자리로 들어감

#### Hole

![](/images/os/osmm5.png)

- 사진 속 노란 공간이 hole (가용 공간)
- 프로세스가 도착하면 hole에 넣는다.

#### 동적 저장공간 할당(dynamic storage allocation) 문제 (알고리즘)

: 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole 을 찾는 문제

1. First-fit: size가 n 이상인 것 중 맨 처음으로 찾은 hole에 할당
2. Best-fit: size가 n 이상인 가장 작은 hole을 찾아서 할당 / 
홀의 리스트가 크기순 정렬아닌 경우 모든 hole을 탐색하는데 시간 소요
3. Worst-fit: 가장 큰 hole에 할당. 역시 모든 리스트를 탐색해야함. 상대적으로 아주 큰 hole들이 생성됨.

=> First-fit, best-fit이 worst-fit보다 속도/공간 이용률 측면에서 효과적임

#### Compaction

- 외부조각으로 생기는 hole을 한군데로 몰아 아주 큰 hole로 모아 큰 block으로 만듦
- 매우 비용이 많이 드는 방법임
- 런타임 바인딩이 지원되어야 가능함.


논리-물리 메모리 주소 바인딩, 동적 로딩과 프로세스를 연속적으로 메모리에 적재하는 법


주1회씩 예솔님과 일대일 컴퓨터 구조 스터디를 하고 있다. 순차논리에 이어지는 래치, 플립플롭을 이해하느라 고전했다. 
스터디를 하면서 내가 잘못 이해했다는 걸 깨달았다. 그래서 예솔님에게 설명도 더 듣고, 자료도 더 찾아보고 책을 다시 읽어봤다.
래치와 플립플롭을 공부하면서 왜 잘못 이해했었는지, 어떤 실수를 저질렀는지 되돌아본다.

## 1. set, reset의 의미를 생각하지 않았다.

set은 단어 뜻 그대로 설정, reset은 set되어있던 값을 재설정하는 역할을 한다. 
과거의 값을 지니고 있는 순차논리 회로에 설정과 재설정을 아예 안 할 순 있어도 설정과 재설정을 동시에 할 순 없다. 그러니 set, reset이 둘다 0인 경우는 유효하나 set, reset이 둘다 1인 경우는 유효하지 않다.

처음 책을 읽었을 땐 set과 reset의 의미보단 두 개의 input(입력값)이라는 데에 치중하며 읽었다. 그냥 입력값이 아니라 semantic한 요소라고 생각하며 읽었어야했다.

## 2. 이전에 저장되어있던 값을 생각하지 않았다.

순차논리는 조합논리와 다르게 입력값(현재 상태)에 이전 값(과거 상태)을 더한다. 
그래서 회로를 볼 때에 그 이전 값(주로 out)을 고려해야하는데 나는 너무 현재 상태 위주로 봤다. 
이쯤 되면 얘 그냥 순차논리를 아예 몰랐던거 아니냐 싶겠지만 이제라도 알았으니 됏쬬,,,^^*

## 3. 회로들의 쓰임새를 덜 생각했다.

![열띤 토론의 흔적](/images/blog/2203/ca31.jpg)

예솔님이 스터디때 나한테 위 D래치를 쓰는 이유에 대해서 물어봤었는데, 대답을 못 했었다. 왜냐면 그 이유를 생각하지 않은 채 그림을 이해하려고 회로만 주구장창 봤기 때문이었다.
이 래치는 입출력인 set, reset 2비트를 out 1비트로 만드는 역할을 한다. 또 reset이 1인 경우엔 값을 재설정하는 기능을 한다.

![열띤 토론의 흔적2](/images/blog/2203/ca32.jpg)

그리고 이 S-R NAND 래치는 set과 reset이 둘다 1인 경우에 과거의 값을 Q로, 과거의 값 bar를 Q bar 값으로 내보낸다. 즉 과거의 상태를 유지한다.

이처럼 이런 래치들의 쓰임새를 생각해보면서 진도를 나갔을 때 회로의 발전과 책의 흐름을 더 따라가기 쉬웠다. 
스터디하면서 머릿속에 많은 물음표가 떴었는데, 이 물음표들을 느낌표로 바꿀 수 있게 노력해준 예솔님께 고맙다.


래치와 플립플롭을 배우면서 했던 실수를 되돌아본다.


요즘 핫한 리액트 프레임워크 `next.js`!!  
처음 `next.js`를 알게 된 건 next.js로 만든 멋진 웹사이트를 보고 나서부터였다. 
그이후로 점점 next.js의 이름을 많이 들었더니, 관심이 안 생길 수가 없었다 👀  
documentation을 좀 읽어보는데 쉽게 따라할 수 있는 튜토리얼이 있다고 해서 한번 따라해봤다.  
그리고 배운 것들을 정리해 보겠음 📂

## Next.js

![nextjs](https://nextjs.org/static/images/learn/foundations/next-app.png)

Next.js는 리액트 프레임워크 중 하나다. 위 사진 속에 보이듯 routing, data fetching, SSR 등을 할 수 있게 해준다.  
리액트를 쓸 때 라우팅을 하려면 `react-router-dom`을 따로 쓰고 설정을 해줘야했는데, next.js를 쓰면 얘가 알아서 해준다.  
여러모로 개발자가 리액트로 개발하는데 아주 큰 도움을 준다! (잠깐 써보고 벌써 체감했다.)

또 개발 단계의 앱을 프로덕션 단계로 만들고 싶을 때 Rust로 만들어진 Next.js 컴파일러가 프로덕션 최적화를 한다.
이 때 앱을 **컴파일**(브라우저가 이해하는 언어로 변환),
**번들**(웹 페이지에서 필요한 파일 수를 줄이기 위해 의존성 모듈이나 파일을 합치는 것),
**minify**(불필요한 코드, 여백을 줄여 파일 사이즈 줄임),
**코드 스플릿**(페이지에서 필요한 코드만 로딩해 앱의 초기 로드 시간을 줄이고자 앱 코드들을 작은 번들로 나누는 것)을 해
프로덕션 단계로 만든다. 

프로덕션 준비가 완료된 빌드 단계에서 Next.js 앱은 아래 네가지 파일을 갖게 된다. 
빌드가 완료되면 유저들이 사용할 수 있는 런타임 단계가 된다.

1. 정적 생성(SSG)된 HTML 파일들
2. 서버에서 렌더링할 JS 코드
3. 클라이언트에서 인터랙티브한 페이지를 만들 JS 코드
4. CSS 파일

## 렌더링

Next.js에서 가능한 렌더링 방법은 서버 사이드 렌더링(SSR), 정적 사이트 생성(SSG), 클라이언트 사이드 렌더링(CSR)이 있다. 
이 중 SSR과 SSG는 

### Pre-rendering

![pre-rendering](https://nextjs.org/static/images/learn/data-fetching/pre-rendering.png)

Next.js는 모든 페이지를 pre-render한다. 클라이언트 쪽의 JS가 아니라 
Next.js가 모든 HTML 페이지를 미리 만들어놓는다. 성능과 SEO 결과가 더 좋아진다.
만들어진 각각의 HTML은 그 페이지에서 필요한 최소한의 JS 코드를 포함한다. 
브라우저에서 페이지가 load되면 그때 그 JS 코드가 실행되어 페이지를 더 인터랙티브하게 한다. (이 과정을 **hydration**이라고 한다.)  
`<Link/>`같은 인터랙티브 컴포넌트는 js가 로드된 후 사용가능하다.

브라우저에서 자바스크립트를 꺼두고 Next.js로 만든 페이지에 들어가보면 더 확실히 알 수 있다.  
Next.js가 우리의 웹앱을 정적 HTML로 만들어놓았다는 것을!
만약 그냥 리액트 웹앱이면 자바스크립트 없이 동작하지 않았을 것이다.  

### Pre-rendering의 2가지 방법 (정적 생성 & 서버사이드 렌더링)

Next.js에선 이 두 방법 중 뭐를 쓸지 내가 직접 고를 수 있고, 섞어서도 개발할 수 있다.
Static generation과 server-side rendering의 차이는 **언제 페이지의 HTML을 생성하느냐**다.  
(개발 모드에서는 무조건 매 요청마다 pre-render된다.)

#### Static Generation: 빌드 시에 HTML 생성

![빌드 시 HTML 생성](https://nextjs.org/static/images/learn/data-fetching/static-generation.png)

- 왠만하면 이게 좋다. 왜냐면 한번 빌드된 페이지를 쓰면 되니까 서버가 매 요청마다 페이지를 렌더링하는 것보다 훨 속도가 빠르다.

#### Server-side Rendering: 매 요청 시에 HTML 생성

![매 요청시 HTML 생성](https://nextjs.org/static/images/learn/data-fetching/server-side-rendering.png)

- 만약 자주 업데이트되는 데이터가 있거나 매 요청마다 페이지의 내용이 달라져야한다면 서버 사이드 렌더링을 쓰는게 좋다.
- 정적 생성 방식보다는 느릴지 몰라도 항상 up-to-date!

## getStaticProps로 데이터가 들어간 Static Generation하기

Next.js에선 페이지 컴포넌트를 export할 때 getStaticProps라는 비동기 함수를 같이 export할 수 있다.

### getStaticProps

- 프로덕션 시 빌드 타임에 실행됨
- 파일 시스템, API, DB 등의 외부 데이터를 fetch해와 페이지의 props로 return할 수 있다.

#### 사용법

lib 디렉토리를 만들고 `gray-matter`를 사용해서 데이터를 내보낸다.  
참고로 그냥 `await.fetch()`를 해서 API로 가져온 데이터도 사용할 수 있다.  
`getStaticProps`는 **page에서 export된 파일만 가능하다.**

```js
// lib/posts.js

import fs, { readdirSync } from 'fs'
import path from 'path'
import matter from 'gray-matter'

const postsDirectory = path.join(process.cwd(), 'posts') // current directory/posts

export function getSortedPostsData() {
    const fileNames = fs/readdirSync(postsDirectory)
    const allPostsData = fileNames.map(fileName => {
        const id = fileName.replace(/\.md&/, '') // .md 지우고 id로 설정

        const fullPath = path.join(postsDirectory, fileName)
        const fileContents = fs.readFileSync(fullPath, 'utf8') // path에 있는 파일 내용 읽어오기

        const matterResult = matter(fileContents) // post의 metadata(frontmatter)
        
        return {
            id,
            ...matterResult.data
        }
    })
    
    // 날짜별로 sort
    return allPostsData.sort(({ data: a}, {data: b}) => {
        if (a < b) {
            return 1
        } else if (a > b) {
            return -1
        } else {
            return 0
        }
    })
}
```

```js
// pages/index.js  
import { getSortedPostsData } from '../lib/posts'

export async function getStaticProps() {
  const allPostsData = getSortedPostsData()
  return {
    props: {
      allPostsData  // prop으로 모든 블로그 포스트 넘겨주기
    }
  }
}

export default function Home({ allPostsData }) {
// ...
}
```

## 짱편한 라우팅

바로 위에서 언급한 next.js의 라우팅에 대해 이야기해보겠다. Next.js에서 한 페이지는 'pages' 폴더 안에 있는 한 파일 속 리액트 컴포넌트다.  
그래서 그 파일 이름으로 라우팅이 된다.

예를 들어 `pages/posts/first-post.js` 파일이 있으면 저절로 `posts/first-post` 로 경로가 설정된다.
다른 라우팅 라이브러리가 필요하지 않아서 진짜... 너무너무너무너무너무 편하다!!!

## Link

Next.js에서 다른 컴포넌트로 이동할땐 `<a/>` 태그 대신 `<Link/>` 태그를 사용한다.  
이때 중요한 점은 **클라이언트 사이드** navigation을 한다는 것이다.

### Client-side navigation

![client side nav](https://nextjs.org/static/images/learn/navigate-between-pages/client-side.gif)

위 이미지를 보면 페이지 전환이 일어나도 노란 CSS 설정이 계속 남아있다.
브라우저가 페이지 전체를 다시 로드하지 않고, client-side에서 navigation을 하기 때문에 일어나는 현상이다.
next.js의 `<Link/>`가 아니라 기본 html tag인 `<a/>`를 쓰면 브라우저가 전체 페이지를 새로고침하기 때문에 노란 CSS가 사라질 것이다.

그 외에도, client-side navigation은 자바스크립트를 이용해 페이지를 전환하기 때문에 브라우저의 기본 navigation보다 더 빠르다.

```javascript
export default function FirstPost() {
    return (
        <>
            <h1>First Post</h1>
            <h2>
                <Link href="/">
                   <a> Back to home</a>
                </Link>
            </h2>
        </>
    )
}
```

간단히 코드를 짜보면 이런식으로 `<Link>` 안에 `<a>`를 넣으면 된다. (링크 태그만 쓰는거 아님!)

## Code splitting and prefetching

**Next.js does code splitting automatically, so each page only loads what’s necessary for that page.**

Next.js는 자동으로 코드를 분리해줘서 페이지별로 로드된다.
처음에 홈페이지가 렌더될 때 다른 코드들은 같이 로드되지 않는다.
그렇기에 한 페이지에서 에러가 나도 다른 페이지들은 작동한다.

또 Link 태그가 브라우저의 viewport 안에 나타날 경우, Next.js가 자동으로 그 목적지 페이지의 코드를 미리 가져와둔다(prefetch).  
그래서 그 페이지로 좀 더 빠르게 이동할 수 있다.

## Static asset

- public 디렉토리 아래에 저장
- ```import Image from 'next/image'``` 컴포넌트를 쓰자.

### Nextjs의 ```<Image/>``` 를 쓰면 좋은 점

- 이미지 최적화해줌. WebP 지원되는 브라우저면 저절로 이미지 resizing을 도와준다.
- 심지어 외부 이미지 링크에서 가져오더라도 최적화가 가능하다. 그저 빛 ⭐️

### on-demand 최적화

- 빌드 시가 아니라 사용자 요청이 들어올때 이미지를 최적화한다. 이미지가 많아도 빌드 성능에 영향을 끼치지 않는다.
- lazy loaded! viewport에 들어올 때 이미지를 load한다.

## Third-Party JavaScript

```js
<Script
    src="https://connect.facebook.net/en_US/sdk.js"
    strategy="lazyOnload"
    onLoad={() =>
        console.log(`script loaded correctly, window.FB has been populated`)
    }
/>
``` 
앱에 부가적인 기능(analytics, ads, widgets)을 위한 스크립트들을 추가할 땐 `next/script`를 사용하자.
`strategy` 속성으로 언제 그 script가 로드될지를 지정할 수 있다.

## CSS Styling

Next.js에는 CSS-in-JS의 한 종류인 `styled-jsx`가 빌트인 내장되어있다.
리액트 컴포넌트 안에서 CSS를 쓸 수 있고, 또 CSS 스타일의 범위가 제한된다.**(=scoped)**  
styled-components나 emotion을 써본 사람에게는 더 쉬울 것이다.

### Layout Component

Next.js에서는 CSS 설정을 할 때도 도움을 준다. `className`을 설정하면 뒤에 랜덤한 문자열(해시)을 붙여 자동적으로 고유한 클래스 이름을 만들어준다.  
CSS 이름이 겹칠 걱정은 하지 않아도 된다!

`components/layout.js`에 `components/layout.module.css`를 적용하면 된다.  
[module.css](https://nextjs.org/docs/basic-features/built-in-css-support#adding-component-level-css)는 unique한 클래스 이름을 만들어 충돌을 방지해준다.

### API 등 서버와 소통하는 함수는 루트 디렉토리에

블로그 메인에서 recent posts (최근 글 목록)을 보여주고 싶었다. 
이럴 경우, 내 블로그는 SSR이라 **최근 글 목록을 가져오는 함수**를 컴포넌트에 넣으면 안 된다. 
그래서 루트 디렉토리에 Api 폴더를 만들고 거기다가 API 역할을 해줄 함수들을 작성해주는 게 좋다.

## Next.js 튜토리얼을 따라하며 느낀 점

튜토리얼이 친절하고 너~~~무 유용한 프레임워크라 그런가 배우면서 즐거웠다. 
리액트로 프로젝트를 할 때 추가로 불러와 쓰는 라이브러리가 많았다. 
그에 따라 설정할 것도 많아서 헷갈리곤 했는데 Next.js가 내게 도움을 주니 정말 마음에 든다. 
앞으로 많은 프로젝트를 Next.js로 하게 되지 않을까?


SSR 첫걸음, 더 쉬워진 라우팅, 클라이언트사이드 네비게이션...

Next.js 튜토리얼 직접 따라해보기


지난 주에 조합논리를 배웠고 이번 주는 순차논리와 순차 논리 회로들에 대해 이야기했다.

## 조합논리

`출력 = f(입력)`

## 순차논리

`출력 = f(입력 + 저장돼있던 어떤 값)`
이 때 **입력은 현재 상태**, **저장되어있던 값은 과거 상태**를 의미한다.

## **메모리**

: 집이 늘어선 거리(street). 이 집에는 정해진 개수만큼 비트를 저장할 수 있는 방이 있다.  
이 데이터는 데이터 버스에 실어 나른다. (버스: 1개 이상의 장치가 공동으로 사용하는 회선, 회선의 집합)

## RAM (Random Access Memory)

- Random access란? **어느 위치에든 똑같은 속도로 접근하여 읽고 쓸 수 있다**  
- 메모리 배열에 저장된 **행, 열 각각의 주소를 조합해** 읽는다.
- RAM이 8기가라면 8기가 만큼의 공간이 있음. (추상적인 의미가 아님) 
램이 클 수록 공간이 그만큼 넓으니 여러 프로그램을 사용할 수 있는 것.

### SRAM, DRAM (둘 다 휘발성)

|   | SRAM | DRAM |
|---|------|------|
| 구성요소  | 트랜지스터+래치 | 커패시터+소수의 트랜지스터 |
| 속도   | 더 빠름(D램의 100배 이상)| 느리지만 구조가 간단(=> 집적도 향상 쉬움) |
| 가격  | 비쌈 | SRAM 대비 저렴 (cuz 집적도 향상이 쉬움) |
| 용도  | L2, L3 CPU | 컴퓨터 메인 메모리 |
| 데이터 휘발 | 전원 차단시 바로 데이터 지워짐 | 내부에 전류를 일시적으로 저장하는 커패시터가 있어 1주 정도는 보관 가능 |
| 특징   |  | 커패시터와 연결된 스위치가 off되더라도 전류가 새서 메모리 갱신 (재충전) 필요 |

## 블록 장치

블록 장치란 블록 단위로 IO 작업을 수행하는 장치를 말한다. 
디스크 드라이브, SSD, 플래시 메모리가 블록 장치에 속한다.

### 디스크 드라이브

우리가 아는 것처럼 동그란 디스크 판이 회전하면 디스크 헤드가 데이터를 읽는다.

- 디스크 영역을 **자화(자성을 띄도록)** 시켜서 데이터를 저장한다. (비휘발성) 
데이터 알갱이가 자성에 따라 `0` 또는 `1`을 의미하고, 비트를 전류로 변환한다.
- 속도는 **느리지만** 기록의 **밀도가 높고** 주소 공간 필요 없다.
- 블록 단위로만 입출력이 가능해 1바이트만 바꾸고 싶어도 전체 블록을 다 읽고 그 바이트를 바꾼 다음 전체 블록을 다시 써야한다.
- **비트 밀도가 안쪽이 더 높다.** 그래서 최신의 디스크는 외부에 더 많은 섹터를 넣어 낭비를 줄인다.

그러나 디스크 드라이브는 **점점 SSD(Solid State Drive)로 교체**되는 중임

### SSD

: 디스크 드라이브 모양의 패키지에 넣은 플래시 메모리

### 플래시 메모리

- `EEPROM` (전기적으로 프로그래머블, 데이터 삭제 후 재기록 가능)
- 원하는 위치를 맘대로 읽을 수 있음(LIKE RAM)
- 블록 단위로 지우고 씀
- 읽을 때는 임의 접근, 쓸 때는 블록 접근

## I/O 장치 (입출력 장치, 주변장치, peripheral)

: 키보드, 마우스 등 사용자의 입력을 받는 장치와 프린터처럼 출력을 하는 컴퓨터 주변 장치

## 과거: I/O Street과 Memory Street을 분리했다

![과거의 IO 연결](/images/os/io2.jpg)

- 이유 1. 작은 패키지에 우겨넣기엔 컴퓨터가 너무 컸음
- 이유 2. 메모리 Street에 집이 많지 않았어서 IO까지 담기엔 무리였음

## 현재: 메모리 Street의 일부를 I/O 장치에 할당

![현재의 io 연결](/images/os/io1.jpg)

- 이유: 운영체제의 **기본 데이터 처리 단위가 커져서**(32, 64비트) **메모리 거리의 주소 수가 많아짐** ⇒ 빈 집 늘어남

## 입출력 슬롯

컴퓨터에는 표준 입출력 슬롯이 있어 **일관된 방식**으로 IO 장치를 연결할 수 있다.

![io slot](https://t1.daumcdn.net/cfile/blog/0277363D51C2BBE23B)

### 입출력 장치에 메모리를 할당하는 방법 (like 서부시대의 땅 분배)

1. (메모리가?) 빈 집들 중 IO 장치에게 할당할 수 있는 영역(주소들)을 고른다.
2. 각 슬롯의 장치는 자신에게 할당된 주소를 모두 사용 가능하다.
3. 각 슬롯은 CPU가 슬롯-장치 매핑을 할 수 있는 특별 주소를 가진다.

## 입출력 장치 컨트롤러

![IO Controller의 내부 구성도](/images/os/io4.png)

- 프로세서는 이 입출력 컨트롤러의 레지스터에 비트들을 쓰거나 읽음으로써 입출력을 수행

## Memory Mapped IO (메모리 영역에 있는 IO)

![memory mapped io](/images/os/io5.png)

- 오늘날의 대부분
- 메모리, IO가 나란히, 연속된 주소 영역에 할당됨
- IO가 차지하는 만큼 메모리 용량은 감소
- CPU는 메모리, IO를 동일한 외부기기로 간주해 액세스할때 표준 데이터 전송 명령 (**read, write)** 사용
    - Read: IO 장치에서 읽어 오는 것
    - Write: IO 장치를 제어 / 출력
- 소프트웨어적으로도 메모리 액세스 & 데이터 입출력이 동일한 것으로 간주되어 load나 store 명령으로 수행 가능

### 장점

포트 입출력 구현할 때 메모리, io 차이 없어서 CPU 로직이 **간단함** ⇒ 더 저렴하고 빠르고 쉬운 CPU ⇒ **RISC가** 추구하는 바(**‘하드웨어와 기계어 명령어의 단순화 원칙’)**와 일치!

### 단점

주소와 데이터 버스를 더 많이 사용

## IO Mapped IO (IO 영역에 있는 IO)

![io mapped io](/images/os/io6.png)

- Isolated IO라고도 한다. (분리된 IO)
- 메모리, IO가 별개의 주소 영역에 할당됨
- CPU는 이 둘을 구분해야하므로 read/write 외에도 IO에 접근하는 신호(in/out)가 필요함
- 메모리 액세스: load, store
- io 입출력: input, output 명령에 의해 수행됨

### 장점

어드레싱 능력이 제한된 CPU 사용할 때 유리 (메모리 용으로 주소영역 전체를 사용 가능)

### 단점

Memory mapped io 방식 대비 하드웨어 구조가 복잡

## 명령어 비교

![memory-mapped io 의 예시](/images/os/io7.png)

- 데이터 레지스터 주소: 412번지
- 상태/제어 레지스터 주소: 413번지
- 상태 레지스터 최하위비트 = RDY 비트로 사용 (3번째 줄)
- 제어 레지스터 최상위비트 = 프린트 동작 start 비트로 사용 (2번째 줄에서 clear, LOAD 80H에서 load)

---

![io-mapped io의 예시](/images/os/io3.png)

이미지 출처: [https://itstory07.tistory.com/881](https://itstory07.tistory.com/881)


메모리를 알아보고 입출력 장치에 메모리 할당하는 방법을 알아본다.

순차논리와 RAM, 디스크 드라이브와 SSD의 특징


## Deadlock (교착 상태)

- 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

## 자원

- 하드웨어, 소프트웨어 등을 포함 (io device, cpu cycle, memory space, semaphore(공유데이터도 자원임) 등)

### 프로세스가 자원을 사용하는 절차

request (요청) - allocate (할당받음, 획득) - use (사용) - release (배출)

## 데드락 발생 조건 4개

1. mutual exclusion 상호배제: 매순간 **하나의 프로세스만이** 자원을 독점적으로 사용
2. no preemption 비선점: 자원을 **빼앗기지 않음**
3. hold and wait 보유대기: 내가 가진 자원을 **가지고 있는 채로** 다른 자원을 대기
4. circular wait 순환대기: 자원을 기다리는 프로세스간에 **사이클이 형성됨**

<img width="300" alt="circular wait" src="https://user-images.githubusercontent.com/50111853/156170865-8b21e26d-0560-4dcf-b1dc-9480802a9d23.png"/>

## 자원 할당 그래프로 데드락이 걸렸는지 알아보자

<img width="597" alt="자원할당그래프" src="https://user-images.githubusercontent.com/50111853/156171575-f644ca2f-ead9-493a-81c9-4b7d5a151dc6.png"/>

Process -> Resource: 프로세스가 자원 요청 (!= 획득)
Resource -> Process: 프로세스에게 자원 할당
사각형 안에 동그라미: 자원의 갯수

<img width="348" alt="데드락 상태인 자원할당그래프" src="https://user-images.githubusercontent.com/50111853/156172148-fb037163-e934-4c2d-aa7e-23fce691bc04.png"/>

위 그림을 보면 싸이클이 있음. 이때 만약 **동그라미(자원의 인스턴스)가 한개면 데드락**임.
**이땐 R2의 자원이 2개지만 싸이클도 2개라 데드락임.**

<img width="335" alt="사이클 1개인 자원할당그래프" src="https://user-images.githubusercontent.com/50111853/156172324-e304cf8d-192c-40c2-9230-91954b4de48b.png"/>

이 그림은 싸이클이 1개, 자원이 2개라 데드락이 아님.

## 데드락 처리 방법

1. 데드락 예방: 자원 할당 시 데드락의 4조건 중 어느 하나가 만족되지 않도록 하는 방법
2. 데드락 회피: 자원 요청에 관련된 추가 정보를 모아 데드락의 가능성이 없는 경우에만 자원을 할당 / 시스템 상태가 원래 상태로 돌아올 수 있을 때만 자원 할당
3. 데드락 탐지 및 recovery: 데드락 발생은 허용하되 탐지 루틴을 두어 탐지 시 recover
4. 데드락 무시: 데드락을 시스템이 책임 안 짐.

유닉스를 포함한 현대의 운영체제는 **대부분 데드락을 Ignorance(무시)** 함. 이유는 **데드락은 빈번하게 일어나지 않기 때문에 괜히 방지했다가 오버헤드 일어날까봐.** 사용자가 알아서 프로세스를 죽이거나 대처하도록 함.

### Deadlock prevention

<img width="552" alt="Deadlock prevention" src="https://user-images.githubusercontent.com/50111853/156172754-68636cf3-2b3b-4a3e-9b71-1dcf2182226f.png"/>

- hold and wait: 프로세스 시작할 때 필요한 모든 자원을 받아놓고 시작함. 자원을 **비효율적으로 사용함.**
- no preemption: cpu, memory는 상태를 쉽게 save, restore할 수 있어서 빼앗음으로써 자원을 사용 가능.
- circular wait: 자원에 순서를 정해 '1번 자원을 획득해야지만 2번을 획득할 수 있다'라는 식으로 제한.

### Deadlock avoidance

<img width="539" alt="데드락 회피" src="https://user-images.githubusercontent.com/50111853/156175031-4050c5d0-58f8-4960-ab01-ce35e68eee21.png"/>

- 가장 단순한 데드락 회피 방법: 프로세스가 시작될때 그 프로세스가 쓸 **모든 자원의 수(최대사용량)를 선언하고 시작** 함으로써 데드락 회피
- 시스템이 safe state에 있으면 데드락 X
- 시스템이 unsafe state에 있으면 데드락 가능성 있음.
- 데드락 회피 방식은 2개의 회피 알고리즘을 통해 시스템이 **unsafe state** 에 들어가지 않는 것을 보장한다.

1. Resource Allocation Graph 알고리즘: 자원당 1인스턴스인 경우
2. Banker's 알고리즘: 자원당 여러 인스턴스인 경우

#### 자원 할당 그래프 알고리즘 (자원당 인스턴스가 1개인 경우)

<img width="558" alt="스크린샷 2022-03-01 오후 10 14 23" src="https://user-images.githubusercontent.com/50111853/156175465-75f2fa10-6e57-4a81-a94a-3ca015612abd.png"/>

- 위 그림에서 **점선: 이 프로세스가 이 자원을 한번이라도 요청할 가능성**이 있다.  
- 데드락 회피 방식은 최악의 상황을 가정하고, 안전한 경우에만 자원을 할당함.

#### Banker's algorithm (자원당 인스턴스가 여러개인 경우)

<img width="582" alt="스크린샷 2022-03-01 오후 10 24 45" src="https://user-images.githubusercontent.com/50111853/156177114-66e22ae5-d894-4e1f-850e-f0ba39da5b85.png"/>

#### 상황 : 5개의 프로세스, 3개의 자원타입(각각 10개,5개,7개)

- 자원 B는 프로세스 A를 최대 9개 요청한다. Max(최대 요청할 양) - Allocation(할당된 양) = Need(추가 요청할 수 있는 양)  
- 이 때 P1처럼 **Available로 Need를 충족할 수 있다면 OK**
- 다만 P0처럼 Available(가용 자원)의 수로 Need를 충족할 수 없다면 자원을 빌려줄 수 없다. (데드락 우려)

### Deadlock Detection & Recovery

<img width="537" alt="wait for graph" src="https://user-images.githubusercontent.com/50111853/156322003-126f093c-e635-4733-9952-326366b0df1f.png"/>

- 프로세스가 요청하면 자원을 일단 준다.
- 위에서 배운 자원할당그래프와 뱅커스 알고리즘, wait-for graph을 사용해 detection

#### Recovery

1. 프로세스 종료: 데드락 걸린 프로세스 다 죽임 or 데드락 사이클이 사라질때까지 하나씩 죽임
2. 프로세스 뺏기: 데드락 걸린 프로세스들 중 비용이 가장 작은 victim을 골라 safe state로 롤백한 후 해당 프로세스를 재시작.

- 프로세스 뺏기 시 starvation 우려: 동일한 프로세스가 계속해서 victim으로 선정되는 경우가 있음. 이를 방지하고자 cost factor에 rollback 횟수도 같이 고려해야함

### Deadlock Ignorance

- 만약 시스템에 데드락이 발생한 경우 사용자가 직접 프로세스르 죽여야함


Categories