LECTURE is here

KOCW 온라인에서 제공되는 이화여대 반효경 교수님의 OS 강의에 대한 정리 요약

• 노션에 기록했듯 CSAPP과 함께 천천히 병행
• 연관 게시글은 강의 진행 순서대로 정렬되어 있지 않고, 내 필요에 따라 강의의 주제를 선택해 듣는다.
• 온라인 상의 타인들이 올려놓은 연관 자료 역시 함께 참고한다.

메모리는 CPU가 직접 접근할 수 있는 컴퓨터 내부의 기억 장치이며, 프로그램이 CPU에서 실행되려면 해당 부분이 메모리에 올라가 있어야 한다. 이때 한정된 메모리 공간에 여러 프로그램을 수용하려면 메모리에 대한 효율적인 관리 메커니즘이 필요하다. 따라서 메모리 관리를 위해 운영 체제는 메모리의 어느 부분이 어떤 프로그램에 의해 사용되고 있는지를 파악하여 이를 유지하게 되는데, 이러한 정보는 주소를 통해 관리된다.

물리적 메모리는 관리하는 방식은 고정 분할 방식, 가변 분할 방식, 가상 메모리 방식 등이 있다.

Logical address vs. Physical Address

Logical(=virtual) address

📌 프로세스마다 독립적으로 가지는 주소 공간

각 프로세스마다 0번지부터 시작한다.
cpu가 보는 주소는 logical address!
컴파일되며 주소는 바뀌지만 그 안에 코드 상의 주소는 logical address로 남아 있다.

Physical address

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

실제로 사용하려면 논리적 주소는 물리적 메모리 어딘가에 올라가야 하는데, 이는 MMU를 거쳐 논리 주소는 물리주소로 바인딩 되어 메모리에 담긴다. ( (BASE_ADRESS + LOGICAL_ADRESS)번지)
물리적인 메모리 하단에는 OS가 올라가 있고, 그 위에 프로세스들이 올라가는 형태이다.

심볼로된 어드레스 사용 -> 컴파일, 숫자로된 주소 -> 주소변환해서 물리적 메모리로

주소 바인딩 (Address Binding)

주소 바인딩에 대한 기법은 아래의 3가지 종류로 구분할 수 있다.

Compile time binding

컴파일할때, 물리적 메모리 주소를 결정한다.
시작 위치 변경 시 컴파일을 다시해야 한다.
이미 결정된 상태이므로, 물리적 주소로 갈 때 논리적 주소를 그대로 가져다 써야한다.
미리 결정되어야 하기 떄문에 비효율적. 이전에 컴퓨터 안에서 하나의 프로그램만 실행되는 환경에서 사용하곤 했다.
컴파일러가 만드는 해당 코드를 절대 코드(absolute code)라고 한다.

Load time binding

프로그램이 시작되어 메모리에 올라갈때 결정
컴파일러가 재배치가능코드(relocatable code)를 만들었을 때. 비어있는 위치는 어디든 갈 수 있는 코드
ex) 500번대가 비어있는걸 보고, 해당 주소에 올린다.

Execution time binding (=Run time binding)

실행 시 주소가 결정되는 것은 load time binding과 같지만 주소가 실행 도중에 바뀔수가 있다.
300번째에서 700번째로 이동
지금의 컴퓨터 시스템에서 지원
cpu가 메모리 주소를 요청할 때 마다 바인딩을 체크해야 한다.(address mapping table) ;물리적인 메모리가 어디 올라가 있는지 체크
하드웨어적인 지원이 필요

MMU

주소변환을 해주는 하드웨어 장치
두 개의 레지스터 이용해서 주소 변환(limit register, relocation register)

두 가지 레지스터에 의해 동적 재할당이 이뤄진다. 요청된 프로세스에 대해 relocation register에서 최솟값을 가지고 있다가, 요청한 논리적 주소에 더해서 물리 메모리의 위치를 찾는다.

limit register가 없으면, 악의적인 프로그램에서 해당 프로세스의 limit을 넘은 부분까지 침범하여 다른 프로세스에 접근할 가능성이 있다.

📌 Dynamic Loading ?

해당 루틴이 불려질 때 메모리에 load
memory utilization 향상
가끔씩 사용되는 양 많은 코드 유용
보통 프로그래머가 운영체제 지원없이 구현하는 것을 말하지만, 운영체제가 자체적으로 올리고 쫒는 것을 지칭하기도 한다. (OS는 라이브러리를 통해 지원 가능)
loading : 메모리로 올리는 것

📌 Overlays ?

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림 -> 차이가 없음?
프로세스의 크기가 메모리보다 큰 경우
프로세스를 한 번에 올릴 수 없는 작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현하던 것이 시초이다. 매우 복잡. Manual Overlay

스왑 (Swapping)

메모리의 공간이 부족한 경우, priority가 맞은 프로세스를 일시적으로 통째로 메모리에서 backing store로 쫓아내는 것을 말한다.

• swap out : 메모리에서 쫓아냄
• swap in : 쫓겨났던 게 메모리로 도로 올라옴

Backing store(=swap area)

디스크이다.
많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간이다.

Swap in/Swap out

일반적으로 중기 스케줄러(swapper라고도 함)에 의해 swap out 시킬 프로세스 선정한다.

기준은 priority-based CPU scheduling algorithm (priority가 낮은 프로세스를 swapped out 시키고, 높은 프로세스 메모리에 올려 놓음).

Compile time 혹은 load time binding에서는 원래 메모리 위치로 swap in 해야 한다. 그러나 Execution time binding에서는 추후 빈 메모리 영역 아무곳에나 올릴 수 있고, 효율적 swap in을 위해 지원되면 좋다.

파일 입출력과 다르게 프로세스를 통째로 옮겨서 그 양이 많다. swap time은 대부분 transfer time(swap되는 양에 비례하는 시간)임. -> 원래는 하드디스크에서 접근 시간은 seek time이 가장 큰 부분을 차지하고, transfer time은 상대적으로 매우 미미하다. 하지만 양이 방대한 swapping 시스템에서는 양이 워낙 많기때문에 transfer time도 상당부분을 차지한다.

원칙적인 swap은 프로그램을 구성하는 주소공간이 통째로 이동하는 것을 말한다. 하지만 최근에는 프로그램의 일부, 예로들면 페이징할때 일부 페이지만 쫓겨나는 것 마저도 이 페이지가 swap out 되었다라고 말하기도 한다. (이후 Paging 기법 참고)

Linking

프로그램 작성 -> 컴파일 -> 링크(여러 군데 존재하는 컴파일된 파일들을 묶어 하나의 실행파일 만드는 것)

Dynamic Linking

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

1. Static linking

   라이브러리가 프로그램의 실행 파일 코드에 포함된
   실행 파일의 크기가 커짐
   동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 eg.같은 기능을 하는 printf 함수 100개 코딩하면 100카피가 메모리에 올라감

2. Dynamic Linking

   라이브러리 실행 시 연결됨
   라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
   라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
   운영체제의 도움이 필요
   이것을 해주는 라이브러리를 shared library, shared object(linux), dnl(windows)

Allocation of Physical Memory

메모리 일반적인 두 영역은 OS 상주 영역과 사용자 프로세스 영역으로 나뉜다.

이는 각각 커널 영역, 유저 영역이라고 부르며 전자는 interrupt vector와 함께 낮은 주소 영역 사용, 후자는 높은 주소 영역을 사용한다.

이 중 사용자 프로세스 영역의 할당 방법은 연속할당(Contiguous)과 불연속할당(Noncontiguous)으로 구분할 수 있다.

🚩 연속할당 (Contiguous allocation)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 기법을 말한다. 즉, 하나의 프로세스가 시작 주소와 끝 주소가 연속적인 메모리 공간에 할당되는 것이다.

이 방식은 메모리 접근이 빠르고 효율적이며, 프로세스가 실행 중에 메모리 접근이 필요한 경우에도 쉽게 처리할 수 있다. 그러나 프로세스 크기가 고정되어 있고, 메모리 공간이 분할되어 있을 경우에는 메모리 낭비가 발생할 수 있다.

아래와 같이 세부 분류가 가능하다.

• Fixed Partition Allocation
• Variable Partition Allocation

🚩 불연속할당 (Noncontiguous allocation)

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있는 기법이다.

이 방식은 메모리 공간을 최대한 활용할 수 있어 메모리 낭비를 줄일 수 있다. 그러나 프로세스가 실행 중에 다른 메모리 공간으로 이동해야 하는 경우 메모리 접근이 복잡해지고 처리 속도가 느려질 수 있다. 또한 메모리 공간을 찾는 과정에서 오버헤드가 발생할 수 있다.

아래와 같이 세부 분류가 가능하다.

• Paging
• Segmentation
• Paged Segmentation

여기서 잠깐!
📌 연속할당Contiguous allocation이 정적 할당Static Allocation과 동일하고, 불연속할당Noncontiguous allocation과 동적 할당Dynamic Allocation이 동일한 개념?

아니다.

연속할당Contiguous allocation은 하나의 프로세스가 연속된 메모리 공간에 할당되는 것을 의미한다.
이 방식에서 정적할당Static Allocation과 동적할당Dynamic Allocation 둘 다 사용될 수 있습니다. 정적할당의 경우 프로세스가 생성될 때 미리 할당된 메모리 공간이 있어야 하며, 동적할의 경우에는 프로세스 실행 중에 동적으로 할당된다.

불연속할당Noncontiguous allocation은 하나의 프로세스가 연속된 메모리 공간이 아닌 분산된 메모리 공간에 할당되는 방식을 의미한다.
이 방식은 오직 동적할당Dynamic Allocation에 해당하는 개념이다. 불연속할당은 메모리 공간을 최대한 활용할 수 있어 메모리 낭비를 줄일 수 있으나 메모리 접근이 복잡해지고 처리 속도가 느려질 수 있기 때문에 특정 상황에서만 사용된다. 불연속할당에는 Paging 기법과 Segmentation 기법이 있다.

• 정적 할당 (Static Allocation)

  사용자 프로세스가 생성될 때에 필요한 메모리 공간을 미리 할당

• 동적 할당 (Dynamic Allocation)

  사용자 프로세스가 실행 중에 필요한 메모리 공간을 그때그때 동적으로 할당

🚩 Contiguous allocation (연속할당)

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 함(이전의 예시들).

1. 고정 분할 방식 (Fixed Partition allocation)

프로그램이 들어갈 사용자 메모리 영역을 미리 영구적 분할(partition)으로 나누어 놓은 것.
균일하게, 가변적으로 모두 나눌 수 있음.

• 외부조각 : 올리려는 프로그램보다 메모리 조각이 더 작아서 사용이 안 된 공간.
• 내부조각 : 올리려는 프로그램이 메모리 조각보다 작아서 프로그램이 할당되고 남은, 사용 안 되는 공간

2. 가변 분할 방식 (Variable Partition alloction)

들어갈 메모리 영역을 미리 나누어 놓지 않는 것.

프로그램이 실행될 때마다 순서대로 쌓음. 프로그램 B가 끝나면 빈 공간, D는 빈공간보다 커서 아래쪽에 들어간다. 빈 공간보다 커서 못 들어갔으니 외부 조각이며, 남은 공간도 외부 조각이 된다.

종료가 되면 중간에 hole들이 생긴다.

✅ 여기서, hole들 적당한 위치에 프로그램을 넣어야하는데 어디에?

Dynamic Storage-Allocation Problem

📍 First-fit
최초발견 hole에 넣기
📍 Best-fit
Size n 이상인 가장 작은 hole 찾아서 할당
Hole들의 리스트가 크기순 정렬되지 않은 경우 모두 탐색해야 한다.
많은 수의 아주 작은 hole들이 생성

Compaction

external fragmentation 문제를 해결하는 한 가지 방법
사용 중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
매우 비용이 많이 듦
Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다. runtime binding이 애초에 지원되어야 한다.
최소한의 메모리 이동으로 compaction하는 방법(매우 복잡한 문제)

🚩 Noncontiguous allocation(불연속할당)

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

1. Paging

하나의 프로그램을 구성하는 주소공간을 일정히 같은 크기의 단위(페이지)로 자른다. 페이지 단위로 올려놓거나, backing store에 내려놓는다.

가상메모리를 자르는 것처럼 물리적 메모리도 페이지 크기로 잘라 놓는다. 그 공간을 페이지 프레임이라고 부른다. 프레임 하나하나에는 페이지가 올라갈 수 있다.

주소변환을 페이지별로 해야하기 때문에 address binding이 더 복잡해진다.

page table: 각각의 페이지의 물리적 주소 정보를 저장한다. 주소변환 위치 값을 저장하는 일종의 배열.

2. Segmentation

하나의 프로그램을 구성하는 주소공간을 function등의 의미 단위로 자른다.

주소공간이 code, data, stack 으로 크게 나뉘는데, 해당 방식과 같이 자름. 더 잘게 자를 수도 있다. 함수단위 등. 대신 세그먼트별로 주소 변환을 해야 한다.

Segment table: 각각의 세그먼트의 기본 주소와 길이 정보를 저장한다. 일종의 배열.

3. Paged Segmentation

Paging과 Segmentation을 결합한 방식. Segmentation에서 각 세그먼트를 페이지로 나누어 할당하는 것.

Paged Segmentation은 메모리 공간을 필요한 크기로 자르기 위해 세그먼테이션을 사용하고, 각각의 세그먼트를 페이지로 분할하여 물리 메모리에 할당한다. 이 방식은 세그먼테이션의 장점인 프로그램의 논리적 구조를 유지하면서 메모리 공간을 효율적으로 사용할 수 있는 장점과, 페이지 할당 방식의 장점인 메모리 공간을 유연하게 확보할 수 있는 장점을 결합한다.

Paged Segmentation의 구현 방식은 세그먼트 테이블과 페이지 테이블을 모두 사용한다.

Paged Segmentation은 메모리 공간의 효율성과 프로그램의 논리적 구조를 모두 고려한 메모리 할당 방법으로, 현대 운영체제에서 많이 사용된다.