[운영체제] 군대에서 공부하기 Week3

 

🗓️ 23.10.09

- 추상 자료형 (Semaphores)

• 구체적인 구현을 나타내는 것이 아니다!
P연산자는 값을 가져가는 것.
V연산자는 값을 반납하는 것.

- Block / Wakeup Implementation

Resources Queue에서 대기할 때 계속 while문을 도는 것이 아니고, 아예 block시키는 것이다.
이후 사용이 끝나 차례가 오면 그때 깨워서 사용하는 것

*V연산: 자원을 반납하고 끝나는 것이 아니고, 깨워주고 나온다.

- Which is better?

• Critical section의 길이가 긴 경우 Block/Wakeup이 적당
오랫동안 lock이 걸려있는 걸 풀려고 하면 낭비되는 시간이 많기 때문에.. (일반적으로는 Block/Wakeup이 좋다!)

- Deadlock 과 Starvation

• Deadlock
둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상이다.

• Starvation
특정 프로세스만 자원을 공유하게 하여 다른 프로세스는 자원을 얻지 못하게 하는 현상

🗓️ 23.10.10
- Readers-Writers Problem

현 process가 DB에 write 중일 때 다른 process가 접근하면 안된다. (read는 동시에 여럿이 해도 됨!)

• Shared data
Db 자체와 Read account 가 해당한다.

- Dining-Philosophers Problem

젓가락의 개수는 한정되어 있고 식사를 해야하는 인원도 한정되어있다. 밥을 먹기 위해서는 반드시 젓가락 2개를 사용해야하는데 다른 철학자가 이미 젓가락을 사용중이라면 한명은 젓가락을 사용하지 못하게 되는 것이다.

해결책.
• 4명의 철학자만 테이블에 동시에 앉게 한다
• 젓가락 2개를 모두 잡을 수 있을 때만 젓가락을 사용할 수 있게 한다.

🗓️ 23.10.11

근무가 너무 많아 공부할 시간이 없었다..

🗓️ 23.10.12

- Monitor

모니터에서는 한번에 하나의 프로세스만이 활동할 수 있다.

- Bounded-Buffer Problem

내용이 들어있는 버퍼를 기다리며 잠들어있는 프로세스가 있다면? 깨워줘라!!

- Deadlock: 교착상태

누군가 희생한다면 데드락이 발생하지 않겠지만..
작업을 위해서는 어쩔 수 없기에 교착상태인 데드락이 발생하는 것이다.

정리하자면, Deadlock 란?
일련의 프로세스들이 서로가 가진 자원들을 기다리며 block 된 상태.

자원은 뭘까?
자원은 하드웨어, 소프트웨어들을 포함하는 개념으로 I/O device, CPU cycle, memory space, semaphore 등이 해당한다.

- Deadlock 발생의 4가지 조건

• Mutal exclusion (상호 배제)
자원을 일단 얻었으면 독점적으로 사용한다는 것.
매 순간 하나의 프로세스 만이 사용할 수 있다.

• No preemption (비선점)
빼앗기지 않는다는 것.
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

• Hold and wait
이미 가진 자원을 절대 내어놓지 않음.
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

• Circular wait
필요로 하는 자원들이 꼬리를 물고 결국에는 가진 자원을 기다리며 사이클을 형성하는 것.
자원을 기다리는 프로세스 간에 사이클이 형성되어야 함

* 4가지 조건 중 하나라도 만족하지 않으면 Deadlock는 발생하지 않는다.

아래 박스안의 검은 점은 갖고있는 인스턴스를 의미한다.

프로세스 1은 2번 자원을 갖고 있으며 1번 자원을 기다리는 중이고, 그 1번 자원은 프로세스 2가 갖고 있다. 프로세스 2는 2번 자원을 갖고 있으며 3번 자원을 기다리고 있지만 3번 자원은 3번 프로세스가 갖고 있는 상황이다.

그럼 위 상황은 Deadlock인가??
그래프에 cycle이 없으면 Deadlock이 아니다.
위의 경우 되돌아오는 화살표가 없기에 cycle이 없는 상태이고 결국 Deadlock가 아닌 것이다.

- Deadlock의 처리 방법

*위로 갈수록 강한 방법!

• Deadlock Prevention
자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
(Deadlock 그냥 내버려 두는 것)

• Deadlock Avoidance
자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당.
시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
(Deadlock 그냥 내버려 두는 것)

💡시스템이 safe state에 있으면 no deadlock
시스템이 unsafe state에 있으면 possiblity of deadlock

• Deadlock Detection and recovery
시스템이 느려진 경우, Deadlock의 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

• Deadlock Ignorance
Deadlock을 시스템이 책임지지 않음
UNIX를 포함한 대부분의 OS가 채택
(Deadlock 관련 아무 일도 하지 않음. 요즘 운영체제가 이걸 사용함)

 

- Deadlock Prevention

• Mutal Exclusion
공유해서는 안 되는 자원의 경우 반드시 성립해야 함

• Hold and Wait
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
방법 2) 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청

• No Preemption
1) process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선정됨.
2) 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
3) State를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용(CPU, memory)

• Circular Wait
1) 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
2) 예를 들어 순서가 3인 자원 R을 보유 중인 프로세스가 순서가 1인 자원 R2를 할당받기 위해서는 우선 R을 release 해야 한다.

➡️ Utilization 저하, throughput 감소, starvation 문제

🗓️ 23.10.13

근무 이슈로 공부를 못했다.

🗓️ 23.10.14

- Banker's Algorithm

은행원 알고리즘은 교착상태를 피하기 위한 방법 중 하나로, 다중 프로세스 환경에서 사용된다. 교착상태란 프로세스들이 서로를 기다리며 무한 대기에 빠지는 상황을 의미하는데, 은행원 알고리즘은 은행이라는 개념을 사용하면 안전한 자원 할당을 보장할 수 있다.

은행은 각 자원의 수량을 파악하고, 각 프로세스가 얼마나 많은 자원을 요청하고 보유하고 있는지를 추적한다.
프로세스가 자원을 요청할 때, 은행은 이 요청이 안전한지 확인하는 것! 즉, 요청된 자원을 할당하더라도 시스템이 여전히 교착상태에 빠지지 않는지를 검사하는데. 안전한 할당인 경우에만 자원을 할당하고, 그렇지 않은 경우에는 대기시키는 것이다.

이러한 방식으로 안전을 추구함으로써 Deadlock이 발생할 일은 없지만, 그리 효율적이지는 않다..

- Deadlock Dection and Recovery

Process termination
Deadlock과 연루된 모든 프로세스를 중지시키는 것.

🗓️ 23.10.15

- Logical address

프로세스마다 독립적으로 가지는 주소 공간
각 프로세스마다 0번지부터 시작 / CPU가 바라보는 주소는 Logical address이다.

- Physical afdress

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

- 주소 바인딩이란?

주소를 결정하는 것이다.
Symbolic Address -> Logical Address -> Physical address

• Compile time binding
컴파일과 동시에 물리적 메모리 주소가 결정되는 것.
시작 위치 변경 시 다시 컴파일된다.

• Load time binding
프로그램이 시작되어 메모리에 올라갈 때 물리적인 주소가 정해지는 것.

• Execution time binding (Run time binding)
실행 시에 주소가 결정되지만, 실행 중에 메모리 주소가 바뀔 수도 있다. (하드웨어의 지원이 필요)

Run time binding의 경우 하드웨어의 지원이 필요하다고 하는데 구체적으로 살펴보자면,

- Memory Management Unit (MMU)

logical adress를 physical adress로 매핑해주는 Hardware device이다.

MMU의 register을 통해 logical address가 physical address로 바뀌는 것을 알 수 있다.

• MMU scheme
사용자 프로세스가 CPU에서 수행되며 생성해 내는 모든 주소값에 대해 base register (=relocation register)의 값을 더한다.

• User program
logical adress만 다루며 실제 physical adress를 볼 수 없으며 알 필요가 없다.

- Dynamic Loading

• 프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모에 load 하는 것.
• 가끔씩 사용되는 많은 양의 코드의 경우 유용하다.
• 운영체제의 특별한 지원 없이 프로그램 자체에서 구현이 가능하다. (OS는 라이브러리를 통해 지원이 가능함)

*Loading: 메모리로 올리는 것

- Overlay

• 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올
림
• 프로세스의 크기가 메모리보다 클 때 유용
• 운영체제의 지원 없이 사용자에 의해 구현
• 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현

- Swapping

프로세스를 메모리에서 아예 쫒아내는 것(하드디스크로)

- Dynamic Linking

Linking을 실행시간(execution)까지 미루는 기법.

• Static linking
라이브러리가 프로그램의 실행 파일 코드에 포함된다.
동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비가 발생한다. (print 함수의 라이브러리 코드)

• Dynamic linking
라이브러리가 실행되면 연결(link)된다.
라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어온다.

이해가 잘 가지 않아 gpt의 힘을 빌렸다.
"Static Linking"은 프로그램과 모든 필요한 라이브러리를 한데 묶어 실행 파일을 만드는 방식이며, "Dynamic Linking"은 실행 파일과 라이브러리가 별도로 존재하며 실행 시에 필요한 라이브러리를 불러와 사용하는 방식입니다. Static Linking은 실행 파일이 독립적이지만 크기가 크고, Dynamic Linking은 공유 라이브러리를 활용하여 용량을 절약하지만 라이브러리 업데이트나 관리가 필요합니다.

- Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘는데.
OS 상주 영역과 사용자 프로세스 영역으로 나뉜다.
OS 상주 영역의 경우 낮은 주소 영역을 사용하고, 사용자 프로세스 영역의 경우 높은 주소 영역을 사용한다.

사용자 프로세스 영역의 할당 방법

• Contiguous allocation

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
방법이 2개로 나뉘는데!

고정 분할의 경우 프로그램의 크기와 분할된 것의 크기가 달라 내부조각이 생기는 문제가 발생한 것이다.

가변 분할의 경우 차곡차곡 올려두는데 프로그램의 크기보다 남은 공간의 크기가 작은 경우 조각이 남는 문제가 발생하는 것이다. 가용 메모리 공간인 Hole이 계속해서 발생하게 된다. 그래서! 추후 프로그램을 Hole에 넣는 방식으로 문제를 해결한다.

• First-fit
그냥 처음 발견된 것에 프로그램을 넣어주는 것
• Best-fit
가장 잘 맞는 프로그램을 넣어주는 것
• Worst-fit
가장 큰 홀에 그냥 프로그램 넣어주는 것

compaction이란?
작은 여러 개의 홀들을 하나의 큰 홀로 만드는 것

• Noncontigious allocation (현대에 주로 사용)

하나의 프로세스가 메모리의 여러영역에 분산되어 올라갈 수 있음

 

- Paging

물리 메모리(실제 컴퓨터 메모리)와 프로그램이 사용하는 가상 메모리(프로그램이 갖고 있는 메모리 공간)를 효과적으로 관리하기 위한 방법으로 "페이징"을 사용한다.메모리를 작은 조각들로 나누어서 사용하는 것과 같은데!
이러한 작은 조각들을 "페이지"라고 부르며, 프로그램은 이 페이지 단위로 메모리를 사용한다.

페이징 테이블이란?
페이징 테이블은 가상 메모리 주소를 실제 물리 메모리 주소로 변환하기 위한 목록 또는 맵핑 정보를 포함하는 표이다. 각 항목은 가상 메모리 페이지 번호와 해당 페이지가 물리 메모리 어디에 위치하는지를 나타낸다.

메모리에 접근하기 위해서는
pge table을 한번 걸치고 접근해야 메모리에 접근할 수 있다.

모든 메모리 접근 연산에는 2번의 memory access가 필요하기에 불편하다.. 이때 쓰이는 게 Paging Hardware이다.

- Paging Hardware with TLB

페이징 테이블(TLB, Translation Lookaside Buffer)은 컴퓨터 메모리 관리에서 사용되는 캐시 메모리 유형 중 하나로, 가상 메모리 주소와 실제 물리 메모리 주소 간의 매핑 정보를 빠르게 조회하기 위한 특수한 메모리이다.

1) 가상 메모리 주소 접근
프로세스가 가상 메모리 주소로 메모리에 접근하려고 할 때, CPU는 이 주소를 확인한다.

2) TLB 조회
CPU는 먼저 TLB를 확인한다.  

3) TLB에 주소가 있는지 확인
CPU는 TLB에 가상 메모리 주소가 이미 저장되어 있는지 확인한다. 만약 TLB에 해당 주소와 관련된 정보가 있다면, 바로 물리 메모리 주소를 얻을 수 있는 것이다.

4) TLB 미스(Miss) 처리
TLB에 해당 주소가 없는 경우, 이를 TLB 미스라고 부른다.  CPU는 이때 메인 메모리의 페이징 테이블에 가서 가상 메모리 주소를 물리 메모리 주소로 변환한다. 이 정보를 TLB에 저장하고, 물리 메모리 주소를 얻는다

5) 물리 메모리 접근
최종적으로 CPU는 물리 메모리에 실제로 접근하여 데이터를 가져오거나 저장하게 된다

- Two Level Page Table(2단계 페이지 테이블)

현대의 컴퓨터는 address space가 매우 큰 프로그램을 지원한다. Two Level Page Table의 경우 아래의 사진처럼 계층적으로 나뉘는것을 알 수 있다.

2단계 페이지 테이블의 경우 1단계 페이지 테이블에 비해 연산 시간은 더 걸리겠지만.. 공간도 더 손해이지만..
그래도! 사용하는 이유는..
전체 주소 공간을 다 사용하는 게 아니라 빈 공간으로 두기 때문에 공간을 비워둔다는 점에서 더 효율적이라고 할 수 있다.

---

너무 일정을 타이트하게 잡은 걸까? 일이 많아 일정에 치이는 걸까. 일정은 계획대로 진행 중이지만 책 없이 하는 공부라 그런지, 실습의 부재? 때문인지 왠지 100% 소화를 못하고 있는 느낌이 들어 아쉽다. 대환이형이 운영체제 책도 선물해 줬는데.. 다음 달에는 17년도 교수님의 강의를 보며 책과 함께 공부하는 방향도 고려하고 있다.
쉽지 않은 한 주였고, 일이 넘칠 다가올 한 주일지라도.. 최대한 짬을 내어서 공부를 해야겠다. 운영체제 자체를 처음 배우다 보니 아직은 신기하고 재밌다. 이 재미 오래 느껴보자😀