240219 CS 스터디 - 운영체제

 

Synchronization

Race Condition을 예방하는 방법이 Synchronization이다.

 

+) 생산자-소비자 문제 (프로세스 동기화에 대한 문제 -> 웹서버와 연결시킬 수 있다 | 생산자:클라(요청을 만든다,버퍼에 넣는다) | 소비자:서버(요청을 처리한다,버퍼를 비운다))

https://copycode.tistory.com/67

운영체제 9장 - 프로세스 관리(6) : 생산자-소비자 문제 -

 

데드락이란?

ㅇㅇ

 

데드락이 발생하는 조건 4가지

1. mutual exclusion : 오직 하나의 프로세스만 리소스에 접근

2. hold and wait : 어떤 프로세스가 어떤 리소스를 가진 상태에서 또 다른 리소스를 차지하기 위해 기다리고 있는 상황

3. no preemption : 강제로 뱉어내지 못함. 자발적으로 리소스를 놔줘야 한다

4. circular wait : 순환구조로 기다리는 상황

- 해결 방안 : 모든 자원에 숫자를 붙여서 오름차순으로만 요청 가능하게 하면 순환구조 회피 가능

- 현실적으로는, 데드락 걸릴 수 있는 모든 자원에 int를 붙여주기 어려움

 

데드락을 어떻게 해결할까?

1. 예방

- 데드락의 네 가지 전제를 없애는 것

2. 회피

- resource allocation graph : 모든 간선에 대한 예측 시간을 계산한뒤, 자원할당 그래프를 계속 확인하며 피한다 -> 속도가 너무 느리다 -> 그래서 나온게 뱅커스 알고리즘

- 뱅커스 알고리즘 : 안정상태이면 주고, 안정상태가 아니면 안준다.

3. 탐지와 회복

4. 무시

- 전세계 운영체제 99%가 이 방법을 채택

- 데드락이 자연적으로 발생할 수 있는 확률이 매우 낮기 때문. 24시간 컴퓨터를 켜놓는다고 했을 때, 일년에 몇 번 없다. 

+) 데드락 vs 라이브락(live lock)
라이브락이란? 진전이 없는 상황에서 죽지 않는다
라이브락 해결방안 : 자원 요청 시간을 랜덤으로 하면 된다

 

+) 식사하는 철학자 문제

https://dkswnkk.tistory.com/412

[OS] 식사하는 철학자들 문제(The Dining-Philosophers Problem)

 

Race Condition

두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 실행 결과가 달라지는 상황.

Race의 뜻 그대로 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황.

 

프로세스의 race condition -> 커널코드에서 발생
스레드의 race condition -> 공유자원에서 발생

 

Critical Section이란?

공유 리소스에 여러개의 스레드들이 동시에 접근하여 고치는 부분으로, Race Condition이 발생할 수 있는 구간.

critical section이 정상적으로 동작하기 위해서는 mutual execlusion을 보장해야 한다.

 

ex. 화장실 칸은 여러명이 동시에 들어갈 수 있기 때문에 critical section이다. 화장실이라는 critical section을 보호하기 위해, 한 칸에는 한 명만 들어갈 수 있도록 mutual execlusion property를 만든 것!

 

Mutual Exclusion (상호 배제)

한 프로세스(스레드)가 공유 리소스를 사용하고 있으면, 다른 프로세스(스레드)가 그 리소스를 사용하지 못하도록 막는다.

 

Lock

Mutual Exclusion한 상태를 만들기 위해 사용하는 것이 Lock이다.

Lock은 아래 두 개의 연산을 지원한다.

void acquire() : Wait until lock is free, then grab it
void release() : Unlock and wake up any thread waiting in acquire()

 

Requirements for Lock

- Mutual execlusion : critical section에 한 번에 하나의 스레드만 진입 가능

- Progress : 공유 리소스를 원하는 여러 스레드들이 있을 때, 하나의 스레드는 critical section에 진입할 수 있어야 한다.

- Bounded waiting : starvation-free. 기다리면 언젠가는 내 차례가 와야 한다.

 

하지만 기본적인 Lock으로만 Syncronization을 구현하기에는 현실적으로 무리가 있다.

계속 spin 하는 방식인 Lock보다 더 우아한 Syncronization 메서드를 제공하는게 세마포어와 뮤텍스.

 

뮤텍스(MUTual EXclusive lock)란?

- 공유된 자원에 한 프로세스(스레드)가 접근하는 것을 막아준다. (동기화 대상이 하나)

- 한 스레드(프로세스)에 의해 소유될 수 있는 key를 기반으로 한 상호배제기법.

- contending 되었을 때는 busy-wait 하는 방법과 blocked 하는 방법이 있다.

- 락 소유자(락을 건 사람)만 락을 해제할 수 있다. (세마포어에는 락 소유자라는 개념이 없다)

  - 세마포어를 올리는 함수 앞뒤에다 뮤텍스를 걸어서 사용하기도 한다.

- Busy-wait (Spinlock) : 문고리를 계속 흔들며 기다린다.

- Blocked (Wait-Signal) : 다른 프로세스가 사용중이라 리소스를 못 잡는 상황일 때, 문고리를 계속 돌리고 있지 않고 점잖게 sleep 하고 있다가 깨우면 일어난다.

(교과서에서는 뮤텍스가 보통 spinlock을 지칭한다고 나와있지만, 현실에서는 blocked를 지칭하는 경우가 많다!)

 

그럼 모두 점잖게 기다리면 좋을텐데, spinlock이 왜 필요할까? spinlock의 장점이 있다.
1. 구현이 굉장히 쉽다. (blocking을 구현하려면 프로세스를 제어해야 한다. 스케줄러도 필요.)
2. context switch 오베헤드가 없다.
-> operation이 짧아 contending이 발생할 가능성이 적은 상황에서는 효율적이고 쉬운 방법!
-> 반면, 보호해야 하는 critical section이 긴 경우에는, blocking 되는 뮤텍스가 효율적이다.

 

+) 바이너리 세마포어 vs 뮤텍스의 차이
락 소유권이 있고(뮤텍스) 없고(바이너리 세마포어)!

 

세마포어 -> 뮤텍스를 보완하기 위해 나옴

- 공유된 자원에 여러 프로세스(스레드)가 접근하는 것을 막아준다. (동기화 대상이 하나 이상)

- 현재 공유자원에 접근할 수 있는 스레드(프로세스)의 수(S)를 나타내는 값을 두어 상호배제를 달성하는 기법. S 값이 1이 되면, 현실적으로 뮤텍스와 동일하게 된다.

- Signaling mechanism. 

# Wait() : decrease S by one, and wait until S >= 0
void wait(struct semaphore *sem) {
	sem -> S--;
    while (sem->S < 0); // S가 0보다 작은 경우에는 계속 무한루프하며 대기
}

# Signal() : increase S by one
void signal(struct semaphore *sem) {
	sem -> S++;
}

 

모니터 -> 세마포어를 보완하기 위해 나옴

https://velog.io/@moonheekim0118/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EB%AA%A8%EB%8B%88%ED%84%B0-Monitor

[운영체제] 모니터 (Monitor)

 

물리주소를 쓰면 되는데 왜 가상주소를 쓰는가? (가상주소가 등장하게 된 배경)

- 실제 물리주소에 어디에 올라갈지 몰라서 나중에 바인딩을 하겠다!

- 그렇게 하니까 개발자 편의성도 좋다

- base bound 체크

 

논리주소(=가상주소) : 프로그래머가 생각하는 주소

물리주소 : 실제 메모리 주소

 

가상주소에 bound를 더하면 물리주소가 나온다. 이걸 하는게 MMU 

 

메모리 파편화

- internal fragmentation (내부단편화)
partition에서 한 작업이 차지하고 남은 영역은 사용할 수 없는데, 이 부분을 internal fragmentation이라고 함.

 

- external fragmentation (외부단편화)
한 partition 영역보다 프로그램이 커서 할당 자체를 할 수 없어 영역 전체가 낭비될 때, 이 부분을 external fragmentaion이라고 함.

 

 

메모리 파편화 해결 방법

- Binding

- Fragment

1. Segmentation 기법 (가상 메모리 사용, 내부 단편화 해결)

가상 메모리를 서로 다른 논리적 단위인 segment로 분할해서 메모리에 할당. (동적할당식으로 가변길이)

mapping을 위해 segment table이 필요하다.

 

Segment table

 

프로세스가 필요한 메모리 공간만큼 할당해 주기 때문에 내부단편화 문제는 일어나지 않지만, 중간에 메모리를 해제하면 생기는 외부단편화 문제가 발생한다.

 

2. Paging 기법 (가상 메모리 사용, 외부 단편화해결)

address space를 연속적으로 할당하지 않고, page 라는 단위로 쪼개서 사용하는 것.

 

먼저, 프로세스의 메모리를 page 단위로 자르고, 실제 physical 메모리(ex. RAM)도 page 단위로 쪼갠다. 이 때 쪼개진 physical memory를 frame이라고 부른다. 그리고 virtual memory의 page를 physical memory의 frame으로 매핑한다.

(= LA와 PA를 같은 크기의 page로 쪼갠 뒤, page table이 이 둘을 매핑하는 방식으로 사용) 

 

 

이렇게 paging으로 메모리를 관리하면, external fragmentation이 발생하지 않는다. internal fragmentation은 발생할 수 있지만 치명적인 정도는 아니다.

 

Page table

- Linear page table

모든 virtual address의 page를 순서대로 담아놓은 page table이다.

즉, vpn (virtual page number) 0번부터 N번까지 쭈욱 늘려놓은 것인데, 이는 현대 컴퓨터 환경에서는 사용되지 않는다.

이유...

 

- Hierarchical page table

위와 같은 문제를 해결하기 위해, "안쓰는 page table은 할당하지 않고 있다가 필요할때만 할당하면 되지 않을까?" 라는 방법이 hierarchical page table이다.

 

outer page table과 page table을 나누어서, 사용하는 outer page table만 하위 page table을 할당하는 방식이다.

 

위와 같이 Virtual Address는 outer page table entry의 위치를 나타내는 p1, page table entry의 위치를 나타내는 p2, page frame에서 실제 위치를 나타내는 d로 구성된다.

 

프로세스는 각자 자신의 VA(Virtual Address)만 들고 있지만, 사실 PA(Pyhsical Address)도 있다.

MMU는 PT(Page Table) 를 사용해서 VA(Virtual Address) 를 PA(Pyhsical Address) 로 translate 하여 사용한다. 만약 Invalid bit 같은게 있다면 page fault를 만든다.

 

TLB (Translation Lookaside Buffer)란?

실제 page table을 찾아보지 않고 빠르게 pfn을 찾을 수 있게 하는 하드웨어 로직. (TLB는 캐시에 저장한다)

 

Hierarchical page table을 사용하니, 메모리를 한 번 읽을 때 여러 depth의 페이지 테이블을 읽어야 하는데, 오버헤드가 너무 크다 -> VA (Virtual Address)를 PA (Physical Address)로 변환하는데 굉장히 많은 시간이 필요하다.

 

그래서 TLB 등장. 최근에 translate 한 정보를 미리 저장해두면 편하겠다.

TLB는 vpn과, vpn에 매핑되는 pfn을 가지고 있는데, 만약 어떤 vpn이 TLB에 있으면, page table을 뒤져보지 않고도 바로 pfn을 알 수 있다.

 

하지만 프로세스가 바뀔 경우 TLB를 모두 flush 해줘야 한다는 문제점이 있다. (TLB에 pid를 추가시켜 flush 해주지 않아도 되는 TLB도 많이 사용된다.)

 

https://ddongwon.tistory.com/49

22. 페이징(Paging)과 페이지 테이블(Page table)

 

+) Page Fault가 발생할 때 어떻게 될까? 
1. OS가 (MMU에 있는) page table을 뒤져본다
2. 없으니 OS의 핸들러에게 결정권을 넘긴다
3. OS가 Back Store(스왑공간?)에 있는 page를 찾는다 (Back Store 중요 !!)
4. 물리 공간에 찾은 page를 올린다
5. page table을 업데이트 해준다
6. 아까 없어서 실패했던 instruction 다시 실행

 

Swapping

- 컴퓨터의 메모리가 부족한 상황이 발생하면, 메인메모리에 올라와있는 프로세스 중 잘 안쓰는 프로세스의 내용을 통째로 디스크(ex. ssd)에 써놓고 메인 메모리의 빈 공간을 다른 프로세스를 돌리는데 사용하자!

- Swap out : 물리 메모리가 꽉 찼을 때 디스크로 내보내는 것 

- Swap in : 디스크에서 물리 메모리로 가져오는 것

 

- Swapping의 장점 : 전체 프로세스 메모리의 합이 현재 내가 가진 물리 메모리보다 더 많을 수 있다!

  - ex. 내 컴퓨터의 메모리가 10기가밖에 안되지만, 내가 돌리고있는 프로그램이 사용중인 메모리의 합이 수백기가가 될 수 있다.(하드디스크 공간만 충분하다면..)

 

- Swapping의 단점 : 오버헤드가 크다.

2GB 프로세스 하나를 swap out 하는데 2.7초 정도 걸린다. 그리고 걔를 다시 읽어들이려면 2.7초가 또 걸린다.

2GB 프로세스를 통째로 바꾸려면 5초 이상 걸린다..

-> 프로세스 전체 address space를 디스크에 넣고 빼는게 아니라, page 단위로 쪼개서  넣고 빼자!

-> Demand Paging

 

Demand Paging

원래 swapping은 프로세스 전체를 넣고 빼는 개념이었다.

demand paging은, page 단위로 넣고 빼는 개념!

딱 필요한 것만 메모리로 불러들이고, 나머지는 저장장치에 두자.

 

+) 반대 개념이 PrePaging
Prepaging - 당장 필요하지 않지만 지역성을 고려해 미리 가져오는거
Demand Paging - "요구"할 때만 가져오는거 (지금 당장 필요한거)

 

 

Main memory의 공간이 부족할 때, P2가 더 많은 page를 요청한다.

이 때, Demand Paging 동작 과정

1. OS가 page replacement policy에 의해 victim page를 선택한다.

2. 해당 page에 있는 내용을 디스크에 있는 swap file에 옮긴다.

3. PTE가 swap out된 page를 가리키도록 갱신한다. (=해당 page는 이제 더이상 메모리에 있지 않고 swap file에 있어.)

4. victim page는 이제 자유롭게 할당 가능하다. -> P2에게 할당해준다.

 

demand paging의 영향력은 지역성을 따른다.

- Temporal locality : 한 번 참조한 메모리 주소를 다시 참조할 가능성이 높다.

- Spatial locality : 참조한 메모리 주소 근처가 조만간 참조될 가능성이 높다.

 

스레싱 (Thrashing)

demand paging을 사용하는 상황에서, 메모리 영역에 접근하게 될 때 page fault 율이 높은 것을 의미하며 CPU 이용률이 급격히 떨어지는 현상 (심각한 성능 저하)

 

Thrashing 발생 방지

- 워킹셋 알고리즘 : page fault가 발생했을 때 디스크로 왔다갔다 하는 시간이 기니까, 여러번 할 걸 한번에 처리하는 개념..?

https://zangzangs.tistory.com/144

[OS] 스레싱(thrashing)

 

페이지 교체 알고리즘  (page replacement policy)

- FIFO (First in First out) : 가장 먼저 들어온(=오래된) 페이지를 교체

  - 간단하고 초기화 코드에 대해 적절한 방법. Belady's Anomaly(FIFO Anomaly) 발생 가능.

- LRU (Least Recently Used) : 가장 오랫동안 사용하지 않은 페이지를 교체

  - 가장 오랫동안 사용하지 않았던 데이터라면 앞으로도 사용할 확률이 적을 것이다. 시간 지역성(temporal locality) 성질 고려.

  - 변형이 많다! 그 중 가장 중요한게 Second Chance Algorithm (=Clock Algorithm)

- LFU (Least Frequently Used) : 참조 횟수가 가장 낮은 페이지를 교체

  - 단점 : 가장 최근에 불러온 페이지가 교체될 수 있음.

- MFU (Most Frequently Used) : 참조 횟수가 가장 많은 페이지 교체

  - 가정 : 가장 많이 사용된 페이지가 앞으로는  사용되지 않을 것이다.

 

https://doh-an.tistory.com/28

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR

 

 

Shared Memory

fork할 때 두 개(parent, child)의 VA가 서로 같은 PA를 가리키도록 PT(Page Table)만 만들어주면, memory copy를 피할 수 있다.

Shared Memory

 

 

근데 문제점!

부모나 자식 중 하나가 write 한다면 다른 하나도 변경된 값을 보게 된다.

그래서 write 할 때 copy하는 copy-on-write 개념이 생긴 것이다.

 

Copy-on-Write

parente process의 이미지를 child에 복사하지 않고 parent process가 가지고 있는 pysical memory의 주소를 공유하는 방식을 통해 child process를 사용하는 방법.

 

copy on write는 기본적으로 fork 기능과 관련이 있다.

fork는 parent process를 이용해서 child process를 만들어내는 것으로 볼 수 있다. 대부분의 자식 프로세스들은 이후에 exec를 해서 새로운 process로 overwrite 하는데, 그러면 부모로부터 복사해온 페이지들은 다 쓸모없는 것이 되고 만다.

 

복사를 하고 바로 exec를 통해 새로운 process를 만들어낼텐데 굳이 복사를 할 필요가 있을까? 라는 의문에 의해 탄생한 것이 copy on write 이다.

 

 

https://hyeo-noo.tistory.com/83

[XV-6 운영체제] Copy-on-Write #1

 

메모리 계층구조

 

메모리 계층은 레지스터, 캐시, 메모리(RAM), 하드디스크(저장장치)로 구성되어 있다.

- 레지스터, 캐시는 CPU 내부에 존재해 빠르게 접근할 수 있다

- 메모리는 CPU 외부에 존재해 느리게 접근한다

- 하드디스크는 CPU가 직접 접근할 수 없다. 하드 디스크의 데이터를 메모리로 이동시키고 메모리에서 접근해야 한다

 

 

Cache Memory란?

- 주기억장치(CPU)에서 자주 사용하는 프로그램과 데이터를 저장해두고 속도를 빠르게 하는 메모리

- 메인 메모리와 CPU 사이에 위치

- 캐시의 적중률을 극대화 시키기 위해서는 CPU가 참조할 정보에 대한 예측이 잘 되어야 함. 이때 나오는 개념이 캐시의 지역성(Locality)

- CPU의 캐시 메모리는 "CPU 안에서 캐시 역할을 하는 저장 장치"라는 뜻이다. '캐시' 자체는 특정한 하드웨어를 가리키지 않는다. 캐시는 더 보편적이고 추상적인 '역할'이다.

 

캐시의 지역성(Locality)이란?

데이터에 대한 접근이 시간적-공간적으로 가깝게 발생하는 것을 뜻함.

- 시간 지역성 : 최근에 참조된 데이터가 곧 다시 참조되는 특성

- 공간 지역성 : 최근에 참조된 데이터와 인접한 데이터가 참조될 가능성이 높은 특성

 

Caching Line이란?

캐시에 데이터가 저장될 때 묶이는 기본적인 단위. 

 

캐싱라인은 CPU가 캐시 메모리에서 목적 데이터에 바로 접근하기 위해 만들어졌다.

캐싱라인은 여러 종류가 있는데, 대표적으로 Full Associative, Set Associative, Direct Map 등이 있다. 

 

+) 캐싱라인이 존재하는 이유?

캐시 메모리는 메인 메모리에 비해 크기가 매우 작기 때문에, 메인 메모리와 1:1 매칭이 불가능하다.

캐시가 아무리 CPU에 가깝게 위치하더라도, 데이터가 캐시 내의 어느곳에 저장되어 있는지 찾기 어렵다면, 비효율적인 시스템이 된다.

 

그래서 캐시에 데이터를 저장할 때는 "캐싱 라인"이라는 단위의 묶음으로 저장하는데, 이 때 빈번하게 사용되는 데이터의 주소들이 일정한 태그들로 묶여있으면 찾기 쉬워질 것이다.

 

https://velog.io/@kangdev/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%BA%90%EC%8B%B1-%EB%9D%BC%EC%9D%B8-Caching-line

[운영체제] 캐싱 라인 (Caching line)

https://coding-zzang.tistory.com/38

[운영체제/OS] 캐시(Cache)와 지역성(Locality) & 캐싱라인(Caching Line)