해당 게시글은 운영체제 스터디를 위해 반효경 교수님 운영체제 강의를 보고 기록한 게시물입니다. 틀린 정보가 있다면 언제든 지적해주세요🙏🏻

데드락

Deadlock Avoidance

• 2가지 경우의 avoidance 알고리즘
  1. Single instance per resource type - Resource Allocation Graph algorithm 사용
  2. Multiple instances per resource types - Banker’s Algorithm 사용

1. Resource allocation graph algorithm
   프로세스가 본인 평생에 사용할 최대한 자원을 알고 있고 안전한 범위 안에서 자원을 할당받는 알고리즘.

2. Banker’s algorithm
   자원의 요청을 받았을 때 자원이 있더라도 그 자원을 내어주었을 때 상황이 불안정해질 가능성이 있으면 그 자원을 내주지 않는 알고리즘.
   

• Deadlock detection and recovery
  데드락이 생기든 말든 요청을 받으면 자원을 주고 데드락이 발생하면 디텍션을 하고 리커버리 하는 방법.
  

-> 뱅커스 알고리즘은 가용자원을 가지고 가능할 때만 주기 때문에 항상 안전하다.
safe sequence는 가용자원만 가지고 처리할 수 있는 프로세스를 찾아서 자원을 주는 방식이다.

• Deadlock Recovery

  1. Process Termination
     연루된 모든 프로세스를 죽이거나 또는 한 프로세스씩 죽여서 데드락이 사라지는지 확인하는 방법
  2. Resource Preemption
     비용이 적게드는 프로세스를 골라서 희생. 비용과 롤백 횟수도 같이 고려함.

• Deadlock ignorance

  • os가 데드락을 무시하는 것. 아무런 조치도취하지 않음. 현대의 범용 os는 이 방법을 채택. 사용자가 직접 프로그램을 종료하거나 컴퓨터 전원을 끄고 키는 방법을 택해서 데드락을 해결하게 함.

메모리관리

• 메모리는 주소를 통해서 접근하는 장치.
• 메모리 주소는 크게 두가지로 나뉜다.

1. Logical Address
   • 프로세스마다 독립적으로 가지는 주소 공간. 각 프로세스마다 0번지 부터 시작.
   • CPU가 보는 주소는 Logical Address
2. Physical Address
   • 메모리에 실제 올라가는 위치.
   • 우리는 메모리주소가 아니라 변수이름이나 함수이름을 사용(int a, b등) 이걸 symbolic address라고 함.
     심

Symbolic Address -> Logical Address -> Physical Address로 변환이 된다.
이 때의 중요한 점은 물리적인 주소로 바뀌는 시점이 언제냐? 그 변환은 누가 해주냐?이고 먼저 주소 변환은 하드웨어가 해준다.

주소 바인딩

• 물리적인 주소로 변환해주는 것.
  
  Load Time Binding은 프로그램이 실행되는 시점에 가상 주소가 물리 주소로 바뀐다.
  
• Run Time Binding은 프로그램이 실행 중일때도 주소가 바뀔 수 있다.
• CPU가 바라보는 주소는 Logical Address이다. 왜 CPU는 논리적인 주소를 볼까?
  -> CPU는 기계어를 실행하는데 이 기계어 하나하나에 보이는 주소는 논리적인 주소가 될 수 밖에 없다.

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터

1. Relocation register (=base register) - 접근 할 수 있는 물리적 메모리 주소의 최소값
2. Limit register - 논리적 주소의 범위

• 이 두가지 레지스터는 왜 필요한가?
  -> 악의적인 프로그램이라면 본인의 주소공간을 넘어 다른 주소 공간을 침범하게 될 수 있음.
  이를 막기 위해서 프로그램의 크기를 Limit register에 넣어놓고 CPU에서 요청한 논리주소가 Limit register에 있는 값보다 크다면 이는 악의적인 시도가 될 수 있다.(Limit register가필요한 이유)이 때는 트랩을 발생시키게 되고 정상적인 상황에서는 주소를 변환해서 내어준다. 트랩이 걸렸을 때는 CPU가 운영체제에게 넘어가고 운영체제는 프로그램을 응징한다. 정상적인 메모리 접근이면 base register 값을 사용하여 주소변환하고 주소 접근을 하게 된다.

• 사용자 프로그램은 논리적인 주소만을 다룬다. (Logical address) 실제 physical address를 알 수 없고 알 필요도 없다.

Dynamic Loading

• 여기서 로딩은 메모리로 올리는 것을 말한다
• 프로그램을 구성하는 주소 공간 메모리 중에서 그 부분이 불려질때만 메모리에 로딩 하는 것.(이렇게 하면 Memory utilization이 좋아진다.)
  -> 당장 필요한 부분, 프로그램에서 실행되는 부분만 올려서 사용한다.
  Dynamic Loading 의 책임은? 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능. 현대 운영체제에서는 라이브러리 통해서 Dynamic Loading 구현.

Overlays

• 필요한 부분만 올리는 것. 다이나믹 로딩과 의미가 같다.
• 역사적으로 용어 의미의 차이가 있다.
  -> 초창기에는 메모리의 크기가 작아서 모든 것을 올리기가 어려웠는데 그래서 프로그래머가 수작업으로 메모리에 올리고 내리고 하는 것(manual overlay)를 했었다. 메모리가 아주 작을 때의 이야기.

Swapping

• 프로세스를 일시적으로 메모리에서 쫓아내는 것.
• 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스가 선정된다. 이때 선정된 프로세스는 Suspended 상태
• Swapping에서는 메모리에 주소공간을 디스크에 쫓아내고 불려오기 때문에 I/O의 양이 많아서 데이터를 transfer time이 Swapping의 상당부분을 차지한다.
• Swapping은 통째로 쫓겨나는 것을 의미한다.

Dynamic Linking

• 라이브러리를 연결하는 작업.
• 작업이 이루어지는 시점에 따라 (언제 이루어지느냐에 따라)
  static linking(static 라이브러리)과 dynamic linking(shared 라이브러리)이 있다.
  1. Static Linking - 내가 만들지 않은 라이브러리인데 컴파일하면서 포함되는 것
  2. Dynamic Linking - 라이브러리가 별도로 존재하다가 라이브러리를 호출하는 지점에서 라이브러리가 어디있는지 파일 형태로 찾아서 연결해 실행시키는 것. 라이브러리를 찾기 위해 둔 것을 stub이라고 부름

물리적인 메모리 관리 기법

• 메모리는 일반적으로 두영역으로 나뉘어 사용한다 - 커널이 존재하는 영역, 사용자 프로세스 영역
• 관리하는 방법은 크게 Contiguous allocation, nonContiguous allocation가 있다.

1. Contiguous allocation

• 프로그램이 쪼개지지 않고 통째로 메모리에 올라가는 방법
• 고정분할 방식과 가변분할 방식으로 또 나뉨
• 현대 운영체제에서는 쓰이지 않는다.
  1. 고정분할 방식 - 물리적 메모리를 여러개의 파티션으로 나누는 것. 내부조각 문제 발생.
  2. 가변분할 방식 - 미리 나눠놓지 않고 실행 순서에 따라서 메모리에 올라감. 프로그램이 종료되면 외부 조각 문제 발생
     
• 가변분할 방식에서 가장 적절한 hole을 찾는 문제
  1. First-fit: 제일 처음 찾는 홀에다가 그 프로그램을 배치하는 것
  2. Best-fit: 사이즈가 가장 적합한 홀에다가 그 프로그램을 배치하는 것. 탐색의 오버헤드가 있음. 아주 작은 홀들이 생성 될 수 있음
  3. Worst-fit: 가장 큰 홀에 할당. 모든 리스트를 탐색해야 함.