
## disk의 구조

- 로지컬 블럭: 디스크의 외부에서 보는 디스크의 최소 단위 (주소를 가진 1차원 배열처럼 취급)
- 섹터: 디스크를 내부에서 관리하는 최소 단위 (원 모양에서 잘려있는 작은 조각)
  - logical block이 물리적인 디스크에 매핑된 위치
  - sector 0은 최외곽 실린더의 첫 트랙에 있는 첫번째 섹터

## Disk management

### 물리 formatting (low-level formatting)

- 디스크를 컨트롤러가 읽고 쓸 수 있게 섹터들로 나눔
- 각 섹터는 header + 실제 데이터(보통 512바이트) + trailer로 구성됨
- 헤더와 트레일러는 sector number, ECC(Error correcting code) 등의 정보가 저장되며 controller가 직접 접근 및 운영

### 파티셔닝

- 디스크를 하나 이상의 실린더 그룹으로 나누는 과정
- os는 이걸 독립적 disk로 취급 (logical disk)

### 논리 formatting

- 파일 시스템을 만드는 것
- FAT, inode, free space 등의 구조 포함

### 부팅

- ROM(전원이 꺼져도 정보가 유지됨)에 있는 'small bootstrap loader'를 실행
- sector 0 (boot block이 있는 곳)을 로드해 실행
- sector 0은 full bootstrap loader program
- os를 디스크에서 load해 실행 (운영체제 커널의 파일을 메모리에 올림)

## disk scheduling

![디스크 스케줄링](https://user-images.githubusercontent.com/50111853/159148036-c372d5a1-4e93-49bb-83b9-56b666e17eb5.png)

- 디스크 스케줄러는 논리 블럭 번호를 보고 스케줄링함.

## FCFS 디스크 스케줄링 알고리즘

![fcfs](https://user-images.githubusercontent.com/50111853/159148126-67014b53-b456-4cae-965d-319f3d59f4a4.png)

- 딱 봐도 헤드가 이동을 많이 하고 비효율적임

## SSTF(Shortest Seek Time First) : 헤드에서 가장 가까운 요청을 먼저 처리

![sstf](https://user-images.githubusercontent.com/50111853/159148152-ae0d187a-24b5-40a2-9afd-21037beca46a.png)

- 현재 헤드에서 가까운 순서대로 요청 처리. 디스크 헤더의 이동 거리가 줄어들지만 starvation 우려가 있다.

## SCAN에 기반한 디스크 스케줄링. (엘리베이터 스케줄링 방식이라고도 함)

![scan](https://user-images.githubusercontent.com/50111853/159148209-6229b149-51f2-46ac-8f0b-d31673125e01.png)

- 큐에 어떤 요청이 들어왔는지에 상관없이 디스크 암이 항상 한쪽 끝에서 다른쪽으로 이동하며 가는 길목에 있는 모든 요청을 처리
- 다른 한쪽에 도달하면 역방향으로 이동하며 다시 이동.
- 문제: 실린더 위치에 따라 대기 시간이 다르다. (가운데 부분은 항상 대기를 짧게 하는데, 극에 있으면 대기 시간이 길어짐)

## C Scan (Circular Scan)

![스크린샷 2022-03-20 오후 1 30 01](https://user-images.githubusercontent.com/50111853/159148224-f807cbe2-c942-41a4-8202-c1076afd4e77.png)

- 헤드가 한쪽->다른쪽으로 이동. 끝에 도달했으면 요청 처리 않고 곧바로 출발점으로 이동
- SCAN보다 균일한 대기시간을 제공

## N Scan

- 출발하면서 기존에 큐에 있던 요청들은 처리하되, 중간에 들어온 요청은 건너뜀. 그리고 돌아갈때 지난번에 들어온 요청들만 처리함

## Look & C Look

![스크린샷 2022-03-20 오후 1 32 19](https://user-images.githubusercontent.com/50111853/159148289-64d182aa-7f29-47c1-b2e9-6d91e269f42e.png)

- 요청이 없어도 끝까지 가고 보는 Scan, C scan의 단점을 개선.
- 한쪽 방향으로 가다가 요청이 더 없으면 방향을 바꿈
- 위 사진의 경우 183 이상의 요청이 없으니 199까지 안 가고 유턴함

## 디스크 스케줄링 알고리즘 결정

- 디스크 스케줄링 알고리즘은 주로 SCAN에 기반한 알고리즘들을 사용함. 룩, 씨룩이 일반적으로 디스크 IO가 많은 시스템에서 효율적
- 파일 할당 방법에 따라 디스크 요청이 영향을 받음
- 디스크 스케줄링 알고리즘은 필요할 경우 다른 알고리즘으로 쉽게 교체할 수 있도록 os와 별도의 모듈로 작성되는 것이 바람직

## Swap-Space Management

![swap space](https://user-images.githubusercontent.com/50111853/159148421-51e543d6-8155-40d1-abcf-156941ffb872.png)

- 프로그램 실행을 위한 메모리의 연장공간으로 Swap area로서 디스크를 사용
- 물리적 디스크를 파티셔닝해 로지컬 디스크를 만들수있다. 그럼 운영체제는 각각의 디스크로 간주하고, 파일시스템을 깔거나 swap area로 사용가능.
- swap in out할때 빠르게 해야하는데 디스크 접근 시간의 대부분은 seek time이라 이걸 줄이는게 중요. 스왑 에리아는 공간 효율성보다 속도 효율성이 중요 (공간은 어차피 프로세스 사라지면 다 지워짐)
- seek time을 줄이기 위해 큰 단위를 순차적으로 할당 (file system은 512 bytes, swap area는 512 kilobytes)

## RAID (Redundant Array of Independent Disks)

- 저렴한 여러 디스크를 묶어서 사용함. 레이드 방식은 여러개다. (중복 저장 또는 분산 저장)

### 사용 목적

- 디스크 처리 속도 향상 :여러 디스크에 내용을 분산 저장해 병렬적으로 읽어옴 (interleaving, striping)
- 신뢰성 향상: 동일 정보를 여러 디스크에 중복 저장. 하나의 디스크가 고장 시 다른 디스크에서 읽어옴 (mirroring, shadowing)
- 단순한 중복 저장이 아니라 일부 디스크에 parity를 저장해 공간의 효율성을 높일 수 있음


Disk란? 파티셔닝과 디스크 스케줄링 알고리즘 비교해보기


지난 번엔 논리 메모리 주소를 물리 주소로 변환하는 것에 대해 배웠는데, 이 작업은 운영체제가 전혀 관여하지 않는다.
이번엔 운영체제가 관여하는 가상 메모리 시스템의 메모리를 효율적으로 관리하고자 사용하는 페이지 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해야해서
- 요즘은 페이지를 크게 하는게 트렌드임


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


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

## 불연속 할당

### 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으로 만듦
- 매우 비용이 많이 드는 방법임
- 런타임 바인딩이 지원되어야 가능함.


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


## 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

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


데드락, 발생 조건과 처리 방법 4가지 (예방, 회피, 탐지, 무시)


세마포어: 프로그래머 관점에서 프로세스를 잘 동기화하는 방법을 보여주는 추상적 접근법.  
고전적인 프로세스 동기화 관련 문제에 대해 알아본다.

## Concurrency Control (병행 제어)

- 프로세스 동기화와 같은 얘기임. 병행 작업할때 잘 제어 하자^^

## Bounded-Buffer Problem (Producer-consumer Problem)

- Bounded Buffer = 유한하다.

<img width="564" alt="스크린샷 2022-02-25 오후 2 06 16" src="https://user-images.githubusercontent.com/50111853/155657222-846c743e-a75c-4253-bbd9-e1f148998db1.png"/>

- 주황색이 데이터가 들어있는 버퍼들 / 회색이 비어있는 버퍼들. 생산자가 버퍼에 데이터를 집어넣는다.
- producer, consumer 프로세스로 총 2 종류의 프로세스가 있음. 이때 프로듀서 프로세스 여러개, 컨수머 프로세스 여러개 가능
- 생산자: Empty buffer에 데이터를 만들어 집어넣는 역할
- 소비자: Full buffer에 데이터를 꺼내감

### 동기화 관련해 일어날 수 있는 문제

1. 공유버퍼이므로 생산자 둘이 한 버퍼에 데이터를 넣으려고 할 수도 있음
2. 소비자 둘이 동시에 데이터를 꺼내가려할 수도 있음
-> 데이터를 넣고 꺼내기 전에 Lock을 걸음으로써 해결가능

### 이 문제에서 semaphore 용도

1. shared data의 mutual exclusion을 위해 binary semaphore 필요
2. 가용 자원(empty buffer)의 개수를 센다 (counting semaphore)

### Bounded-buffer 코드로 해결하기

![바운디드 버퍼 문제 코드](https://user-images.githubusercontent.com/50111853/155870391-2ba9b914-bc80-4b99-b532-2db360b4b13b.png)

- mutex: 락을 걸기 위한 변수 (세마포어)
- P(mutex), V(mutex)가 락을 걸고 푸는 연산임.

## Readers-Writers Problem

![reader-writer problem](https://user-images.githubusercontent.com/50111853/155870504-e706a0ac-4497-4804-b246-db9e4025e43b.png)

- 공유 데이터인 DB의 데이터를 읽고 쓸 때 문제
- **write는 동시에 하면 안 되지만 read는 동시에 가능**

![읽고 쓸 때 문제 해결](https://user-images.githubusercontent.com/50111853/155870566-2f8f3018-ff33-4ecd-91d1-74527f4a74ff.png)

- reader도 writer처럼 배타적으로 해도 되지만 비효율적임
- Reader에선 readcount++함으로서 읽고 있는 자원의 수를 카운트할 수 있음.
- 다만 readcount도 공유 변수라 이거 값 바꿀 때 락 걸고 변경해야함!!!
- 내가 마지막으로 읽고 나가는 프로세스면(if readcount==0) DB에 걸어둔 락을 풀어야함
- reader가 계속 올 경우 writer starvation 될 수도.

## Dining-Philosophers 문제

<img width="412" alt="식사하는 철학자 문제" src="https://user-images.githubusercontent.com/50111853/155872584-47cf73f4-e7a9-423c-995d-6c34f20c7bc0.png"/>

- 철학자들은 밥을 먹거나 생각하거나 둘 중에 하나를 한다.
- 젓가락이 각각 공유자원이고, initially all values are 1 (하나씩 있다)
- 위 코드는 데드락 가능성이 있다.(=모든 철학자가 동시에 젓가락을 든 경우)

### 위 문제 해결 방안 3가지

1. 4명의 철학자만 테이블에 동시에 앉도록 한다
2. 젓가락을 두개 잡을 수 있을 때에만 젓가락을 집게 한다
3. 비대칭 (짝수-왼쪽 젓가락, 홀수-오른쪽 젓가락부터 잡을 수 있도록 제한)

<img width="570" alt="식사하는 철학자 문제" src="https://user-images.githubusercontent.com/50111853/155874415-c1390407-f806-4d66-8b22-a7c6939c9515.png"/>

#### pickup(int i): 젓가락을 잡는 함수

#### test(): 젓가락 들 수 있는 환경인지 확인하는 함수

- 왼쪽, 오른쪽 철학자가 밥 먹고 있으면 if문 만족하지 않아 락 풀지 못함

## 세마포어의 문제점과 그를 보완해주는 모니터

<img width="705" alt="세마포어의 문제점" src="https://user-images.githubusercontent.com/50111853/155872690-5a04d48a-ea2f-4efa-ae5d-04003b0af62d.png"/>

- 세마포어는 동기화하는 법을 알려주고 프로그래머가 제어할 수 있도록 함.
- 모니터: 프로그래밍 언어 차원에서 공유 자원에 접근하는 일을 모니터가 직접 하게 해 프로그래머의 부담을 줄여줌.
- 세마포어는 정확도를 검증하기 어려움/ 프로그래머의 실수가 영향을 끼칠 수 있다. (= 안정성 낮음)
- monitor: 자바의 인스턴스 각각이 lock을 가진다. 자바 내부적으로 모니터를 가지고 있어 synchronized를 쓰면 각 인스턴스의 모니터를 사용할 수 있다.

<img width="501" alt="모니터" src="https://user-images.githubusercontent.com/50111853/155874579-7c3a92a3-f2ce-4af4-8c28-ef16f9b8d7de.png"/>

- 공유데이터에 접근하려면 내부의 프로시저인 모니터를 통해야만함
- 공유 데이터에 접근하는 프로시저를 함수로 구현해두었음
- 모니터 내부 프로시저는 동시에 여러개가 실행이 불가능하도록 모니터가 막고 있음 => **락을 걸 (P,V연산 할) 필요 없음**
- 모니터 안에선 한 프로세스만 활성화된다. 액티브 프로세스가 1개만 있도록 모니터 자체에서 제어한다!!

<img width="509" alt="condition variable" src="https://user-images.githubusercontent.com/50111853/155874631-c2f1adf3-33ea-41d9-a063-304b4d983c26.png"/>

### condition variable

<img width="500" alt="바운디드 버퍼 문제와 조건 변수" src="https://user-images.githubusercontent.com/50111853/155874643-18666c98-a0e3-481a-a93c-e032686834d6.png"/>

- 특정 조건을 만족하지 않은 프로세스를 잠들게 하는데 그 때 그 조건: 컨디션 var
- 위 bonded buffer 문제를 condition var로 해결하자면 공유버퍼가 모니터 안에 있음
- 그래서 생산자든 소비자든 모니터 안에서 활성화되므로 락 걸 필요 X
- 만약 다른 놈이 있을 경우 **빈 버퍼를 기다리는 큐(생산자) 또는 내용이 들어있는 버퍼를 기다리는 큐(소비자)**에 줄을 서고 producer->produce, consumer-> consume 함수 앞에서 기다리며 잠든다.

x.wait(): 프로세스 재워라
x.signal(): 깨워라

## 느낀 점

지난 차시에 내가 binary semaphore = mutex라고 했었다. 바이너리 세마포는 값이 0과 1 중 하나만 가능하기 때문에 '사용 가능한 자원이 있다 또는 없다'를 나타낸다. 뮤텍스 락과 유사하게 상호 배제의 기능을 가진다. 몇몇 시스템에선 아예 뮤텍스 락 없이 이진 세마포가 대신 상호 배제를 보장한다. 이 둘의 차이는 바로 락을 해제할 수 있는 프로세스이다. 뮤텍스의 경우 락을 건 프로세스 자신만이 락을 해제할 수 있는 반면 이진 세마포어의 경우 다른 프로세스가 락을 해제할 수 있다. 누군가에게 세마포어를 설명할 때, '여러 프로세스가 동시에 한 자원에 접근하는 걸 막고자 락을 걸 때, 프로세스가 사용 가능한 자원의 토탈 개수를 나타내는 변수'라고 설명하면 되는 걸까?!

## 복습 문제

1. bounded-buffer problem에서 소비자 프로세스가 데이터를 꺼내갈 때 데이터를 꺼낼 Full 버퍼에만 락을 건다. (O,X)
정답: X, 공유 버퍼 전체에 락을 건다.

2. dining philosophers 문제에서 데드락이 발생하는 경우는?
정답: 모든 철학자가 동시에 젓가락을 잡으려고 하는 경우

3. monitor에서 프로세스가 wait()할 때, 생산자 프로세스는 (꽉 찬/빈) 버퍼를 기다리는 큐에 줄을 서고 소비자 프로세스는 (꽉 찬/빈) 버퍼를 기다리는 큐에 줄을 선다.
정답: 빈, 꽉 찬


프로세스 동기화 관련 문제를 풀어보자 (Bounded-buffer 등)


## 데이터의 접근

Storage Box: Memory 주소 공간  
Execution Box: CPU 프로세스

![컴퓨터 시스템 내 데이터의 접근](https://user-images.githubusercontent.com/50111853/154946794-c1e3a6c1-358d-4b1b-9432-3283ff4300d1.png)

- `저장소(스토리지) <-> 연산(실행)하는 곳` / 어디서든 컴퓨터 시스템에서 이런 경로를 거침
- 데이터가 왔다갔다하고 **여러 execution box가 한 스토리지를 공유하기도** 함. 이때 동기화는 어떻게?

![race condition](https://user-images.githubusercontent.com/50111853/154947007-68147f7c-589d-48d1-a10e-e50a6e4aa0eb.png)

## race condition

- 달리기 레이스처럼 경쟁상태/ 다른 execution box에서 하나의 데이터를 동시에 접근하는 상황  
- 공유메모리를 사용하는 프로세스들간 / 커널 내부 데이터를 접근하는 루틴들 간 (e.g. 커널모드 수행 중에 인터럽트로 커널모드의 다른 루틴 수행)

### 운영체제에서 레이스 컨디션(동시접근)이 발생하는 순간

1. 커널모드 실행중인데 인터럽트가 발생해서 인터럽트 처리루틴 수행될때

   - 둘 다 커널 코드라 커널 주소 공간을 공유

2. 프로그램이 실행될때 유저모드였다가 커널모드였다가 한다.  

   - 커널모드에 있는 프로그램은 CPU를 빼앗는지 않는다.
   - time quantum system은 real system이 아니라 좀 늦게 뺏어도 상관없음.

### Critical Section (임계 구역)

- **다수의 프로세스가 공유 데이터를 동시에** 사용하기 원하는 경우, 각 프로세스의 code segment에는 공유 데이터에 접근하는 코드인 critical section이 존재.
- 한 프로세스가 이미 **critical section**에 있으면 다른 모든 프로세스는 그 안에 들어갈 수 없음.

### critical section 를 소프트웨어 적에서 해결하기 위한 알고리즘

```c
do {
  entry section
  critical section
  exit section
  remainder section
} while(1);
```

### 위 알고리즘의 충족 조건

1. Mutual exclusion(상호 배제) : 한 놈이 이미 안에 있으면 다른 애들은 못 들어감
2. Progress: 아무도 critical section에 없는데 들어가고자하는 프로세스가 있으면 들어가게 해줘야함
3. Bounded waiting(유한 대기): 프로세스가 들어가려고 요청한 후로 언젠간 들어가야한다.

## 알고리즘 1

![고급언어로 짠 알고리즘](https://user-images.githubusercontent.com/50111853/154952318-6d2ac8c4-9604-4719-8b5d-797cd5dda2d0.png)

- 본인의 차례가 아닌 동안 while 돌다가 상대가 critical section에서 나올 때 (=자기 차례가 되면) turn이 1이 됨
- 이 경우 본인이 크리티컬 섹션에 들어갔다가 나와야 상대 차례고 vice versa
- --> p1은 크리티컬 섹션에 여러번, P1는 한번만 들어가고 싶으면 어떡함?
- -> **progress를 잘 충족하지 못한** 알고리즘임.

## 알고리즘 2

![스크린샷 2022-02-21 오후 9 09 35](https://user-images.githubusercontent.com/50111853/154952631-2ead4d13-0160-45bb-955d-6ac696055f77.png)

- 내가 크리티컬 섹션 들어갈 때 플래그를 1로 바꿈.
- 문제: 둘다 깃발만 들고 끊임없이 양보할 수도 있음.

## 알고리즘 3 (피터슨의 알고리즘)

![스크린샷 2022-02-21 오후 9 12 25](https://user-images.githubusercontent.com/50111853/154953064-5932358f-95d3-4cf6-ac52-ac2fce97a769.png)

- 둘다 들어가고싶을때만 니턴 내턴을 따지고, 한 프로세스만 관심 있으면 걔가 들어가는 식
- 문제: busy waiting(=spin lock): 계속 while 문을 돌면서 / CPU와 메모리를 쓰면서 대기함.

하지만 **하드웨어적으로 test&modify를 atomic 수행**하면 간단히 해결 가능
![test and set을 통한 상호 배제](https://user-images.githubusercontent.com/50111853/154954226-8547f53d-fed3-4188-b0f9-67b62b463468.png)

## 세마포어(Semaphores)

- 프로그래머 입장에선 추상적으로 락을 걸고 풀고, 공유자원의 수를 셀 수 있으면 편하다. -> 그래서 나온 것이 세마포어!
- Semaphore S: 정수 값을 갖는 변수 / 앞의 방식들을 추상화
- S = 자원의 개수 (5면 자원이 5개 있는거)
- 추상 자료형(논리적 자료형): object, operation
- 공유 자원을 획득, 반납할때 이 처리를 담당

![세마포어](https://user-images.githubusercontent.com/50111853/154954534-b1138b44-d7c4-4e23-bcce-d4198e4c0d84.png)

**p 연산: 공유 데이터를 획득하는 과정** p연산해서 자원 가져가면 S가 1 줄어듦
**v 연산: 반납하는 과정**

### P(S): 락을 거는 과정

- while 돌다가 S가 양수가 되면(=누군가 자원을 내어놓으면) S의 값을 감소시키며(S--) 자원을 냉큼 획득.
- 계속 돌면 busy waiting과 다를 바 없다

### V(S): 자원 반납

P, V 두 연산은 atomic 연산을 통해서만 접근 가능

## Critical Section of n Processes

![p, v 연산이 있는 임계구역 알고리즘](https://user-images.githubusercontent.com/50111853/155309323-a8a0dee5-7ae2-437c-839c-d4deaa05625c.png)

### busy-wait 방식

- 프로그래머는 세마포어 지원이 되면 P, S 연산만 구현하면 된다. (추상적으로 지원)
- Sleep Lock: Block and wake up 방식 (락 없는 프로세스는 CPU를 쓰는게 아니라 아예 blocked 상태다)

![block/ wakeup implementation](https://user-images.githubusercontent.com/50111853/155310277-c83b8c1e-1f51-4a75-b95c-8f8de3ebc806.png)

L: 프로세스를 담고 있는 리스트

![스크린샷 2022-02-23 오후 8 25 11](https://user-images.githubusercontent.com/50111853/155310450-0925d238-74dd-40ce-ab1d-e30d50911e27.png)

#### P연산

- if문 안으로 못 들어가면(= 남은 자원이 없으면) S.L 리스트에 프로세스를 넣고 block 해둔다.
- 그 후 V연산을 통해 **자원이 반납되면** 리스트 중 한 프로세스를 깨워서 변수값 1 빼고 시작.

#### V연산

- 여기서 S는 자원의 개수를 세는거랑은 좀 다름. 음수면 누가 자원을 기다리고 있다. 양수면 자원을 쓰고 있다. busy-wait의 경우랑 좀 다르다.
- 자원을 내놨는데도 S의 값이 0이라는건 P연산에서 누가 -를 했다는 것
- V연산에는 자고 있는 걸 깨워주는 wakeup 함수를 포함하고 있음.

## Busy wait vs. Block/wakeup

- 보통은 block/wakeup이 더 효율적 but 프로세스의 상태를 block/wake할 때도 오버헤드 든다.
- critical section의 길이가 긴 경우 block / wakeup이 적당
- critical section의 길이가 매우 짧은 경우 busy-wait이 나을 수도 있음

## 2 Types of Semaphores

### Counting semaphore

- 세마포어 변수 값(자원의 개수)이 1 이상으로 갈 수 있을 때
- 여분의 자원 개수를 셀 때

### Binary semaphore

- 0 또는 1값만 가질 수 있는 semaphore

#### 데드락

: 둘 이상의 프로세스가 서로 상대방이 충족할 수 있는 이벤트를 무한히 기다리는 현상
![데드락](https://user-images.githubusercontent.com/50111853/155311534-bf48d4b9-dab6-4039-8db0-d9048fe4a556.png)

해결법: 자원 획득 순서를 똑같이 맞추면 됨. P0, P1 부분을 이렇게 수정하면 된다!

![데드락 해결법](https://user-images.githubusercontent.com/50111853/155312017-70fa1eff-98fe-46a2-b2d9-9f7e6e7d6127.png)


프로세스 동기화 알고리즘 (레이스 컨디션, 임계 구역, 세마포어)


## CPU Scheduling

- CPU를 어떤 프로세스에게 줄 지 결정
- CPU Job이 io bound와 cpu bound 잡이 섞여있기 때문에 필요함!
- 특히 사용자와 인터랙션 하는 IO Bound Job이 cpu 필요할 때 빨리빨리 가져야 사용자가 불편하지 않음.

## CPU Scheduling이 필요한 경우

1. running -> blocked ('나 cpu 필요없어...' io 요청하는 시스템 콜)
2. running -> ready (할당된 시간 다씀. 타이머 인터럽트)
3. blocked -> ready (io 완료 후 인터럽트. 얘한테 바로 cpu 가는거 아님)
4. terminate (프로세스가 종료됐을 때)

1,4는 자진 반납(nonpre-emtive) / 2,3은 preemtive(강제로 빼앗음)

## CPU scheduler (독립적X, 운영체제 안의 CPU 스케줄링 담당 코드)

- ready인 프로세스 중 이번에 CPU를 받을 프로세스를 고른다.

## Dispatcher

- 실제로 CPU를 주는 놈.
- context switching을 하는 놈

## 스케줄링 성능 척도

### 시스템 입장

1. CPU Utilization: CPU에 일 많이 시켜야 꿀임

- cpu를 사용한 시간 대비 일한 시간의 비율 (최대한 일 많이 해야 좋음)

2. Throughput (처리량)

- CPU Burst의 갯수. 처리 완료한 갯수  

### 프로세스 입장

1. Turnaround Time (소요시간, 반환시간)  

- cpu를 받아서 다 쓸 때까지 걸린 시간 (CPU burst 시작~끝)

2. Waiting Time (대기 시간)

- 프로세스가 기다린 시간
- pre emtive의 경우 waiting 타임이 여러차례 쌓여서 길어짐

3. Response Time (응답 시간)

- 첫번째 응답이 오는데 걸린 시간 (타임 쉐어링 환경을 위한 기준)

#### 식당 예시

cpu utilization: 요리사가 요리한 양
throughput: 처리한 손님의 개수
turnaround time: 고객이 들어와 주문하고 식사하고 나가는데 걸린 시간
waiting time: 코스요리에서 다음 메뉴 나오는 거 기다린 시간의 총합
response time: 첫번째 음식이 나올때까지 기다린 시간

## CPU 스케줄링 알고리즘

### FCFS (선착순/ First come, First Served)

- 별로 효율적이진 않다. CPU를 많이 쓰는 프로세스가 cpu를 가지면 CPU를 적게 쓰는 프로그램이더라도 기다려야 한다.
- 관여한 **프로세스의 평균 웨이팅 타임**이 길어진다.
- convoy effect: 앞에 거대한 놈이 기다리고 있어서 기다리고 있어야하는 경우를 말함.

### SJF (Shortest Job First)

- 프로세스를 사용하려는 시간 즉 CPU burst가 가장 짧은 놈에게 프로세스를 줌
- preemtive: 일단 cpu 잡으면 해당 cpu burst가 완료될 때까진 cpu를 선점하지 않음
- nonpreemtive: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 cpu burst time을 가지는 프로세스가 도착하면 cpu 빼앗아서 줌
- nonpreemtive: **shortest average waiting time**

#### SJF의 문제점

1. starvation: 어떤 프로세스에겐 CPU가 계속 안 올 수도 있다.
2. 예측이 쉽지 않음: 얼마나 CPU burst time이 필요한지 프로세스 자신도 모름

- Exponential averaging:

### Priority scheduling (우선순위)

- 우선순위가 **가장 높은** 프로세스에게 CPU를 준다
- preemtive는 더 우선순위가 높은 프로세스가 나타나면 cpu를 넘겨주고, nonpre는 넘겨주지 않음
- 작은 숫자가 우선순위가 높음.
- SJF도 일종의 priority scheduling
- Starvation의 해결법: 에이징(aging) 기법. 우선순위가 낮은 프로세스라도 오래 기다리게 되면 우선순위를 높여주자.

## 라운드 로빈

![round robin scheduling](https://user-images.githubusercontent.com/50111853/154834115-4b900873-d810-4c8b-bff2-173cbb397a53.png)

- **각 프로세스가 동일한 크기의 할당 시간(Time Quantum)**을 가짐.
- Large Q: FCFS / Small Q: 매우 빈번한 Context Switch, 시스템 성능 저하 우려
- 응답 시간이 빨라짐.
- 굳이 예측할 필요 없이 CPU를 짧게 쓰는 프로세스가 짧게 쓰고 나갈 수 있음
- **CPU를 대기하는 시간과 쓰는 시간이 비례**
- 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.

## Multilevel Queue

- ready queue를 우선순위별로 여러개로 분할, 모두 cpu 쓰려고 기다림
- 차별적임. 그래서 multilevel feedback queue를 도입

### multilevel feedback queue

![multilevel feedback queue](https://user-images.githubusercontent.com/50111853/154834381-cc5b1e4b-79d5-4a24-bbec-9f2cbfa6b1f2.png)

- foreground(interactive): 라운드로빈
- background(batch, no human interaction): 선착순
- Queue에 대한 스케줄링이 필요
  - Fixed priority scheduling: fore 부터 -> background / starvation 우려 있음
- **처음 들어온 프로세스는 우선순위 우선으로** 해줬다가 여러번 필요할 수록 우선순위가 뒤로 밀린다.

## multiple processor scheduling

![다수의 프로세서 스케쥴링](https://user-images.githubusercontent.com/50111853/154839986-bc4d10c5-9745-4d89-8aa7-803fd6b825da.png)

- cpu가 여러개면 스케줄링은 더 복잡해짐
- **load sharing**: 일부 프로세서에 Job이 몰리지 않게 부하를 공유

## real time scheduling

- real time: 정해진 데드라인 내에 끝나야함
- 미리 스케줄링을 해서 적재적소에 배치 / 주로 주기적으로 작업하는 프로세스가 많음
- hard real time systems: 반드시 데드라인 안에 끝내야
- soft real time systems: 일반 프로세스에 비해 높은 우선순위를 갖도록

## Thread scheduling

- Local 스케줄링: (user level thread가) 운영체제는 그냥 그 프로세스한테 cpu 줄지 안 줄지 결정. 어떤 쓰레드한테 줄지는 쓰레드 내부가 선택
- 글로벌 스케줄링: 커널 레벨 쓰레드의 경우, 커널의 단기 스케줄러가 어떤 쓰레드를 스케줄할지 결정

## 알고리즘 평가하는 법

![알고리즘 성능 평가](https://user-images.githubusercontent.com/50111853/154840176-a16412ec-636c-4366-8531-7feb11dcfc8b.png)

- Queueing models: 도착률과 처리율(service rate) 등으로 성능을 계산
- 구현 & 성능 측정: 실제 시스템에 알고리즘을 구현해 실제 작업의 성능 측정


운영체제

'운영체제'에 관한 글들을 모아봤어요.