OS_4W_13,15,16,17
가상화된 메모리를 물리적인 메모리에 어떻게 배치-allocation할 것인가, 주소공간
가상화된 공간에서 서로 같은 주소 가지는 경우, 가상 주소가 물리 주소로 변환될 때의 규칙
필요한 정보 등
베..이스앤마운드 큰 덩어리 하나로 보겠다.
같은 성질 스택, 힙, 데이터, 텍스트 등 끼리 모아서 보겠다.
일정한 크기로 나눠서 메모리에 넣자, 페이징
17 Free-space
링크드 리스트로 사용중인 것과 아닌 것 관리
heap 공간 관리도 같은 알고리즘 사용, 사용중/반납
등
...
13 The Abstraction: Address Space
멀티프로그래밍을 하면서 여러 프로세스가 실행 준비 상태에 있고
운영체제가 이들을 전환하면서 실행함.
IO출력 등 반영, 이를 통해 CPU 이용률(Utilizaion) 증가, efficiency 증가
많은 사용자가 동시에 컴퓨터를 사용하고 현재 실행 중인 작업으로부터 즉시 응답을 원하기에
대화식(interactivity)의 개념 중요시
time-sharing의 시작
초기에는 프로세스의 중단 시점의 모든 상태를 저장하는 방식이라 매우 느림
목표는 프로세스 전환시 프로세스를 메모리에 그대로 유지하면서 운영체제가 효율적으로 타임셰어링 구현하는것
그러면서 생긴 중요한 문제는
## Protection 보호의 문제
한 프로세스가 다른 프로세스의 메모리를 읽거나 안 좋게 사용하지 못해야함
# 13.3 주소 공간
위처럼 위험한 행동을 하는 사용자에 대비해 운영체제는 easy to use 메모리 개념 만든게 주소 공간.
*운영체제의 메모리 개념을 이해하는 것이 메모리를 어떻게 가상화할지를 이해하는 핵심이다.*
주소 공간은 실행 프로그램의 모든 메모리 상태를 갖고 있다.
프로그램의 코드는 반드시 메모리에 존재해야 함, 따라서 주소 공간에 존재함
스택은 함수 호출 체인 상의 현재 위치, 지역 변수, 함수 인자와 반환 값 등을 저장
힙은 동적으로 할당되는 메모리를 위해 사용
코드는 정적이기에 메모리에 저장하기 쉬움, 따라서 주소 공간의 상단에 배치
프로그램이 실행되면서 추가 메모리 필요 xxx
스택과 힙은 프로그램 실행하면서 확장되거나 축소됨
힙은 주소 공간의 상단에, 스택은 하단에 위치함(변경 가능, 일반적인 기준)
## 메모리를 어떻게 가상화하는가
운영체제는 물리 메모리를 공유하는 다수의 프로세스에게 어떻게 프로세스 전용의 커다란 주소 공간이라는 개념 제공이 가능한가
# 13.4 목표
운영체제가 가상화를 멋지게 하기
가상 메모리 시스템의 주요 목표
1. trasnparency 투명성
운영체제는 실행 중인 프로그램이 __가상 메모리의 존재를 인지하지 못하도록__ 가상 메모리 시스템을 구현해야 한다.
프로그램은 메모리가 가상화되었다는 사실을 인지해서는 안된다.
프로그램은 자신이 전용 물리 메모리를 소유한 것처럼 행동해야 함.
2. efficiency 효율성
운영체제는 가상화가 시간과 공간 측면에서 효율적이도록 해야함.
너무 느리게 실행되서도, 너무 많은 메모리를 사용해서도 안된다.
이 때 TLB 등의 하드웨어 지원 받음. 추후 배움
3. Protection 보호
운영체제는 프로세스를 다른 프로세스로부터 보호해야 하고 운영체제 자신도 프로세스로부터 보호해야함.
프로세스가 탑재, 저장, 등을 실행할 때 어떤 방법으로든
다른 프로세스나 운영체제의 메모리 내용에 접근하거나 영향을 주면 안된다.
즉 자신의 주소 공간 밖의 어느 것도 접근할 수 없어야 함.
보호 성질을 이용해 우리는 프로세스들을 서로 isolate, 격리시킬 수 있음.
+
코드를 이용해 출력된 모든 주소는 가상주소, VA이다.
사용자 프로그램이 볼 수 있는 주소는 모두 가상주소임.
메모리 가상화의 기술 때문에 명령어와 데이터가 탑재된 물리 메모리 주소를 알 수 있는 것은 운영체제뿐이다!!!
운영체제와 하드웨어만 진짜?물리 주소 알고 있고 우리가 보는건 다 가상주소임15 Mechanism: Address Translation(1/3)
# 주소 변환의 원리
CPU 가상화에서 LDE(제한적 직접 실행) 주로 다뤗는데 요약하면 대부분 프로그램은 하드웨어에서 직접 실행되나 프로세스가 시스템 콜을 호출하거나 타이머 인터럽트가 발생할 때 등 특정 순간에는 운영체제가 개입하여 문제가 발생하지 않도록한다. 운영체제는 약간의 하드웨어 지원을 받아 효율적인 가상화를 제공하기 위해 실행 프로그램에게 방해가 되지 않도록 최선을 다함. 중요한 순간에 운영체제가 관여하여 하드웨어를 직접 제어함. 효율성과 제어가 현대 운영체제의 목표임
메모리 가상화에서도 efficiency와 control을 추구함.
1. 효율성
효율성을 높이려면 하드웨어 지원을 활용해야 함.
(단계별로 점점 복잡한 하드웨어 사용할것, 처음에는 몇개의 레지스터 > TLB, 페이지 테이블 등...)
2. 제어
제어는 응용 프로그램이 자기자신의 메모리 이외에는 다른 메모리에 접근하지 못한다는 것을 운영체제가 보장하는 것을 의미함
프로그램을 다른 프로그램으로부터 보호하고 운영체제를 프로그램으로부터 보호하기 위해 하드웨어 도움이 필요함
+ .Flexibility측면에서 프로그래머가 원하는 대로 주소 공간을 사용하고 프로그래밍하기 쉬운 시스템 만들기
# 어떻게 효율적이고 유연하게 제어를 유지하면서 메모리를 가상화하는가!가 질문임
하드웨어 기반 주소 변환 == 주소 변환
이 기술은 제한적 직접 실행 방식에 부가적으로 사용되는 기능이라고 생각 가능
- 주소 변환을 통해 하드웨어는 명령어 반입, 탑재, 저장 등의 가상 주소를 정보가 실제 존재하는 물리주소로 변환
- 프로그램의 모든 메모리 참조를 실제 메모리 위치로 재지정하기 위해 하드웨어가 주소를 변환함
- 하드웨어에 의해 제공되는 로우 레벨의 기능들은 변환을 가속화하는데 도움이 되지만 하드웨어만으로는 메모리 가상화 구현 불가능, 정확한 변환을 위해서는 하드웨어를 셋업하기 위해 운영체제 관여가 필수적임
- 운영체제는 메모리의 빈 공간과 사용 중인 공간을 항상 알고 있어야 하고 메모리 사용을 제어하고 관리함
- 이 모든 작업의 목표는 프로그램이 착각하도록 하는 것 자신의 전용 메모리가 있고 거기에 자신의 코드와 데이터가 있다는 환상을 가지도록!
# 15.1 가정
일단 나중에 어려운 거하고 이해하도록 쉬운 가정들을 하자 나중에 점자 가성들 완화할것임
- 사용자 주소 공간은 물리 메모리에 __연속적으로__(contiguously) 배치되도록 가정
- 주소 공간은 물리 메모리 크기보다 작다.
- 각 주소 공간의 크기는 같다.
# 15.2 사례
- 프로그램 관점에서 주소 공간은 주소 0 부터 시작한다. 프로그램이 생성하는 모든 메모리 참조는 해당 범위 내에 있어야 함
- 메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소 0이 아닌 다른 곳에 위치시키고 싶오
- 어떻게 프로세스 모르게 메모리를 다른 위치에 재배치 relocation 시킬 것인가15 Mechanism: Address Translation(2/3)
# 15.3 Dynamic(hardware-based) Relocation
동적 재배치 == 베이스 앤 바운드
- 각 cpu마다 2개의 하드웨어 레지스터 필요, base, bound/limit
- 이 쌍은 우리가 원하는 위치에 주소 공간을 배치가능하게 함
- 배치와 동시에 프로세스가 오직 자신의 주소 공간에만 접근한다는 것 보장함
- 이 설정에서 각 프로그램은 주소 0에 탑재되는 것처럼 작성되고 컴파일된다.
## base 레지스터
- 프로그램 시작시 운영체제가 프로그램이 탑재될 물리 메모리 위치를 결정하고 베이스 레지스터를 그 주소로 지정함
- 프로세스가 실행되면서 프로세스에 의해 생성되는 모든 주소가 다음 공긴으로 프로세서에 의해 변환됨
<< 물리 주소 = 가상 주소 + base >>
- 프로세스가 생성하는 메모리 참조는 가상 주소임. 하드웨어는 베이스 레지스터의 내용을 가상 주소에 더해 물리 주소 생성함
- 주소 변환하는 주소 재배치는 실행 시에 일어나고 프로세스가 실행을 시작한 이후에도 주소 공간을 이동할 수 있기 때문에 동적 재배치라고도 불림
## bound 레지스터
- 보호를 지원함
- 프로세서는 메모리 참조가 합법적인지 확인하기 위해 가상 주소가 바운드 안에 있는지 확인함
- 바운드는 프로세스가 생성한 모든 주소가 합법적이고 프로세스의 범위에 있다는 것을 확인함
- 베이스와 바우드 레지스터는 cpu 칩 상에 존재하는 하드웨어 구조이다.
- 주소 변환에 도움을 주는 프로세서의 일부를 메모리 관리 참지, MMU라고 함
+
동적 재배치 구현을 위해서는 작은 하드웨어면 충분함. 베이스 레지스터는 가상 주소가 주소 공간의 범위 내에 있다는 것을 보장함. 두 레지스터는 함께 간단하고 효율적인 메모리 가상화 제공
# 15.4 하드웨어 지원 : 요약
- 운영체제는 커널모드(특권)에서 실행하며 컴퓨터 전체에 대한 접근 권한 가짐
- 응용 프로그램은 유저모드에서 실행되며 실행 가능한 일에 제한 있음
- __프로세서 상태 워드, PSW 레지스터의 한 비트나 CPU의 현재 실행 모드 나타냄!__
- 하드웨어는 베이스와 바운드 레지스터 자체적으로 제공
- CPU는 MMU의 일부인 추가 레지스터 쌍 가짐 >>> 베이스 바운드 레지스터는 CPU 당 한쌍 필요
- 프로그램이 실행 중인 경우 하드웨어는 프로그램이 생성한 가상 주소에 베이스 값을 더해 주소 변환함
- 하드웨어는 주소가 유효한 검사 가능해야 함
> 바운드 레지스터와 CPU 내 일부 회로 이용해 검사함
- 하드웨어는 베이스와 바운드 레지스터 값 변경하는 명령어 제공해야 함
> 다른 프로세스를 실행시킬 때 운영체제가 이 명령어를 사용해 베이스와 바운드 레지스터 값 변경가능
> 이 명령어들은 특권 명령어, 커널모드에서만 레지스터 변경 가능
- CPU는 유저 프로그램이 바운드를 벗어난 주소로 불법적인 메모리 접근 시도하려는 상황 등에서 예외 발생시켜야함
> 이 경우 CPU는 유저 프로그램 실행 중지하고 운영체제의 예외 핸들러 실행되도록 조치15 Mechanism: Address Translation(3/3)
# 15.5 Operating System Issues
위에서 동적 재배치 지원을 위해 하드웨어가 새로운 기능 제공함
이처럼 운영체제도 기능 추가 필요함
1. 프로세스가 생성될 때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아줘야 함
새로운 프로세스가 생성되면 운영체제는 새로운 주소 공간 할당을 위해
free list라고 불리는 빈공간 자료구조를 검색해야 함
검색을 통해 선택된 공간을 사용중이라고 표시함
2. 프로세스가 종료될 때(정상/비정상 종료 포함) 프로세스가 사용하던 메모리를 회수
프로세스가 종료되면 운영체제는 종료한 프로세스의 메모리를 다시 프리리스트에 넣고 연관된 자료구조 정리함
3. 문맥 교환이 일어날 때 추가 조치 필요
프로세스 전환시 베이스와 바운드 쌍을 저장하고 복원해야 함. 여기서 젤 중요!!!!!
커널에서 switch할때 PCB에 레지스터 보존하고 복원할때 베이스와 바운드 레지스터도 포함해야함
4. 예외 핸들러 또는 호출 함수 제공, 예외 처리
+ 15.4를 보면 4의 트랩만 하드웨어적으로 처리하는 거고 나머지는 OS의 소프트웨어적으로 처리하는 것
+ 메모리 변환은 운영체제의 개입 없이 하드웨어에서 처리된다!!!16 Segmentation(1/3)
# 16.1 Segmentation : base/bounds의 일반화
베이스바운드의 문제는 스택과 힙 사이의 빈 공간까지도 물리메모리에 재배치할 경우 메모리 낭비가 발생한다는 것인다. 이러한 빈공간 처리와 관련해 생긴 것이 세그멘테이션이다.
__세그멘테이션은 MMU에 한쌍의 베이스 바운드 값이 존재하는 것이 아니라 세그멘트마다 베이스와 바운드 값이 존재한다.__
세그멘테이션을 사용하면
1. 운영체제는 각 세그멘트를 물리 메모리의 서로 다른 위치에 배치 가능
2. 사용되지 않는 가상 주소 공간이 물리메모리 차지하는 것 방지 가능
__Sparse address space, 드문드문 사용되는 주소 공간, 빽빽하지 않고 사이에 빈공간 널널
예제의 경우 3쌍의 베이스 바운드 쌍이 필요, 각 바운드 레지스터는 세그멘트의 크기 저장
# 16.5 Fine-grained vs Coarse-grained Segmentation
소수의 세그멘트, 코드-스택-힙만을 지원하는 세그멘테이션은
coarse-grained > 주소 공간을 큰 단위의 공간으로 분할함
fine-grained > 주소공간을 작은 크기의 공간으로 잘게 분할
많은 수의 세그멘트를 지원하기 위해 여러 세그멘트의 정보를 메모리에 저장할 수 있는
__세그멘트 테이블__ 같은 하드웨어 필요
# 16.6 Os support
세그멘트의 기본 동작은 시스템이 각 주소공간, 가상주소공간을 세그멘트 단위로 물리 메모리에 재배치함
이전의 주소 공간이 하나의 베이스바운드 값을 가지는 방식에 비해 물리 메모리 절약 가능(빈공간 물리메모리 할당x가능)
세그멘테이션의 도입을 위해서는 운영체제의 문제 해결이 먼저 필요함
1. context switch
세그멘테이션을 사용할 경우 문맥 교환시 세그멘트 레지스터의 저장과 복원 필요.
2. 세그먼트 크기 변경
만약 malloc를 통해 빈공간을 요청할 때 빈공간이 없다면
힙 세그먼트의 크기 증가 필요! 시스템콜 sbrk() 호출!
세그먼트의 크기 레지스터를 더 크게 갱신함. 상황이 안된다면 운영체제는 메모리 할당요청 거절도 함
3. free-space 공간 관리
사용하지 않는 물리 메모리 공간의 관리.
새로운 주소 공간이 생성되면 운영체제는 이 공간의 세그멘트를 위한 빈 물리 메모리 영역 찾음
프로세스는 n개의 세그멘트 가질 수 있고 세그멘트마다 크기 다를 수 있음
__exteranl fragmentation 외부 단편화 문제__
물리메모리가 작은 크기의 빈 공간들로 채워짐. 애매하거나 작아서 새롭게 생기는 세그멘트에 할당도 안되는 작은 조각들! 문제다.
해결은 __compact__ 기존의 세그멘트를 정리하여 물리 메모리를 압축하는 것이다.
운영체제는 현재 실행 중인 프로세스를 중단하고 그들의 데이터를 하나의 연속된 공간에 복사하고
세그멘트 레지스터가 새로운 물리메모리 위치를 가리키게 함. 합쳐진 큰 빈공간 확보 성공!
16 Segmentation(2/3)
프로세스마다 세그멘트 테이블 존재
세그멘트 테이블에는 각 세그먼트마다 base/size/growsPositive/Protection 존재함
만약 같은 프로그램이 2번 로딩될 경우
code는 세그먼트는 공유 가능하므로 이전의 코드세그먼트 베이스 주소 그대로 사용가능함
protection의 경우
코드 세그먼트는 read-execute 가능하고 write는 안됨
힙이나 스택은 read-write 가능하고 exectue는 안됨.17 Free-Space Management
메모리 관리할 때 빈공간을 어떻게 관리하는가!
# 17.1 가정
malloc()은 __void* malloc(size_t size)__ 형태로 프로그램이 요청한 바이트 수를 나타내는 size 변수를 인자로 받음. 그리고 void 포인터 리턴함
free()는 __void free(void *ptr)__ 형태로 포인터를 인자로 받고 그 영역을 해제, free함
이 때 사용자는 크기 정보 전달하지 않음.!!! 포인터만으로 해제하고자 하는 메모리 영역의 크기를 파악함. 이 방법은 추후 논의함
- 힙의 빈 공간은 일반적인 링크드리스트 자료구조 사용
- 영역 내의 모든 빈 공간에 대한 주소 가짐
- __내부 단편화__ 는 빈공간을 할당해 줄 때 요청한 사이즈보다 더 큰 공간을 할당해서 사용하지 않는 공간이 생겼을 때를 말함.
# 17.2 Low-level 매카니즘
## splitting (분할)
요청을 만족하는 빈 공간을 찾아 분할해서 전달
남은 빈공간은 free-list에 다시 연결됨, 시작 주소와 길이가 변경됨
## coalescing (병합)
메모리 덩어리(청크)가 반환될 때 해제되는 청크의 주소와 인접한 빈청크의 주소를 검사해 연결될 경우 더 큰 빈 공간으로 병합함
## 할당된 공간의 크기 파악
free(void *ptr)할 때 크기를 매개변수로 받지 않기에 포인터가 인자로 전달되면 malloc는 해제되는 메모리 영역의 크기를 빠르게 파악해 그 공간을 free-list에 추가시킬 수 있다고 가정
그러기 위해 __headr 블럭__에 필요한 정보를 저장함
- 헤더는 메모리에 유지되며 해제된 청크 바로 위에 위치함
- 헤더에 할당된 공간의 크기 정보는 반드시 필요함
- 그 밖에도 매직 넘버나 기타 정보 추가 가능
(+ int는 4바이트 필요)
## 빈 공간 리스트 구현
malloc(size_t size)
- 해당 청크를 두 개로 분할 후, 헤더 아래의 ptr, 포인터를 반환한다.
- 이후 free()했을 때를 대비해 다시 헤더를 남기고 분할됨
free(void *ptr)
- 해당 포인터의 청크를 반환한다.
- 헤더 크기나 남은 size 계산해 빈 청크를 free-list에 삽입함
__기억할것!!!
- free할 때 포인터의 위치는 헤더 아래임
- next 위치는 헤더의 시작(위)부분이다!!!__
## 힙의 확장
힙공간이 부족한 경우 실패를 반환하거나 sbrk를 호출함
# 17.3 기본 전략
빈공간 할당을 위한 기본 전략과 각각의 장단점
## Best fit - 최적 적합
- free-list 중 요청한 크기 이상의 가장 적합한(작은) 메모리 청크 찾음
- 장점 : 공간의 낭비를 최소화함
- 단점 : 해당하는 청크를 찾기 위해 전체를 검색하는 비용 소요, 성능 저하
수많은 작은 청크 생성
## Worst fit - 최악 적합
- 가장 큰 빈 청크를 찾아 요청된 크기 만큼 반환하고 남은 부분은 free-list에 유지
- 장점 : 최적 적합에서 발생가능한 작은 청크 방지
- 단점 : 베스트처럼 free-list 전체를 탐색하는 오버헤드 발생
큰 빈공간 남기기 시도
## First fit - 최소 적합
- 요청보다 큰 첫번째 청크를 요청만큼 반환함
- 장점 : 속도가 빠름
- 단점 : free-list의 시작에 작은 청크 다량 생성
address-based ordering 주소 기반 정렬로 리스트를 주소로 정렬해
병합을 쉽게하고 단편화 감소시키기
## Next fit - 다음 적합
- 마지막으로 찾았던 청크 포인터를 기억함, 그 다음부터 탐색 시작
- 장점 : 탐색은 리스트 전체에 균등하게 분산, 작은 청크 전체에 분산 가능
- 전체 탐색을 하지 않아 최소 적합과 성능 유사
+
## 버디 할당
- 2^n승으로 메모리 분할함
- 내부 단편화-internal fragmentation 문제 발생가능
- free할 때, 해제할 때 옆의 같은 사이즈 청크가 비어있는지 확인해 비어있으면 두 청크 병합하고 작업을 반복함. 트리를 따라 올라가는 방식
퀴즈
Address Space
제시된 심볼의 값이 주소이면 주소 공간 중 어디에 속하는가
1. foo > 5 code
2. &y > 1 Data 실행화일에 포함
3. &k > 2 Data(BSS)
4. &p > 3 스택
5. *p > 6 not address
6. p > 4 힙
7. x > 6 not address
8. &x > 3 스택
9. a > 6 not address
10. &a > 3 스택
11. main > 5 code
- 심볼의 값을 기준
- *p는 값, x,a 심볼도 값임
- 변수는 다 값임. 함수 이름은 함수의 시작 주소를 나타냄# alignment 여부의 차이
4바이트마다 어쩌구
시뮬레이터 사용해보기
- 강의 중 Offset이 Bound를 넘을 때 발생하는 Exception을 segment fault, segment violation이라고 한 것을 알고리즘 Line6에 있는대로 PROTECTION_FAULT로 정정 합니다.퀴즈
세그멘테이션 - grows negative는 세그먼트의 끝!에서부터 음수방향임
free space - __기억할것!!!
- free할 때 포인터의 위치는 헤더 아래임
- next 위치는 헤더의 시작(위)부분이다!!!__
khj