메모리는 주소를 통해 접근하는 개체.
주소는 두 가지 종류가 있다. 논리적 주소와 물리적 주소.
프로그램마다 가지고 있는 메모리 주소가 논리적 주소. 다른 말로 가상 주소.
프로그램을 시작하면 0번지부터 시작하는 논리적 주소를 각자 가지고 있음.
물리적인 주소는 실제 물리적인 메모리의 주소를 의미한다. 메모리에 프로그램이 어디로 올라가는가를 나타낸다. 물리적인 메모리는 하나로 0번지부터 통으로 관리 됨.
물리적 메모리 안에 아랫부분에는 운영체제 커널이 올라가있고 상위 주소 부분에는 여러 프로그램들이 섞여서 올라가게 된다.
프로그램마다 논리적 주소가 있지만 실행이 되려면 물리적인 메모리 어딘가로 올라가야 된다. 이를 주소변환이라고 한다. 다른 말로 주소를 결정한다 해서 주소 바인딩이라고도 한다. 즉, 주소 바인딩이란 어떤 프로그램이 물리적인 메모리 어디로 올라갈지 메모리 주소를 결정하는 것.
물리적 메모리 주소가 언제 결정될까? 추후 설명
Symbolic Address는 무엇인가? 우리가 프로그래밍할 때는 변수에다가 값을 저장하는 식으로 코드를 짜지 우리가 일일이 주소를 사용하지 않는다. 프로그래머가 메모리를 사용하지만 프로그래머 입장에서는 숫자가 아닌 Symbol로 된 Address를 사용하게 된다. 이게 컴파일 되면 숫자로 된 주소가 생기게 된다.
- Compile time binding
- 컴파일 시에 주소 할당
- Load time binding
- 프로그램 시작 시에 주소 할당
- Execution time binding
- 프로그램 시작 이후에도 중간에 물리적인 메모리 주소가 바뀔 수 있는 방식.
compile time binding은 컴파일 시에 주소 결정한다. 프로그램을 물리적 메모리에 올릴 때는 이미 결정되어 있는, 컴파일 시에 할당 받은 주소로 올려야 한다. 다른 물리적 메모리가 많이 비어있어도 컴파일 시에 미리 정해진 주소로 올려야 한다. 매우 비효율적. 요즘은 거의 사용되지 않는다.
load time binding은 프로그램이 시작돼서 메모리에 올라갈 때 물리적인 메모리 주소가 결정된다. 컴파일 타임 때는 논리적 주소만 결정이 된다.
Runtime binding은 실행 시 주소가 결정되는 것은 같지만, 중간에 주소가 바뀔 수 있다는 특징이 있다. CPU가 메모리 주소를 요청할 때마다 물리적 주소를 그때그때 체크해야 한다. 하드웨어적인 지원이 필요하다. 그때그때 주소 변환을 해주는 하드웨어 필요하다.
CPU가 바라보는 주소는 Logical address를 바라보고 있다. 프로그램 내부 변수 주소나 주소들은 logical address. 컴파일된 코드 자체에 들어가 있는 주소까지 바꿀 수 없다.
여기서도 20번 주소의 값과 30번 주소의 값을 더하는 연산을 할 때 logical address를 바라본다. 그렇기에 CPU가 매번 메모리 몇 번지에 있는 내용을 달라고 하면, 그때 주소 변환을 해서 물리적인 메모리 위치를 찾은 다음 그 내용을 읽어서 CPU에게 준다.
기본적인 MMU에서는 register 2개로 주소 변환을 하게 된다.
CPU가 메모라 346번 위치의 값을 달라고 요청했다. 이때 346은 논리적 주소여서 주소 변환이 필요하다. 이를 해주는 하드웨어가 MMU. 가장 간단한 형태의 MMU는 레지스터 2개를 사용한다.
주소 변환은 어떻게 할까? 프로그램이 물리적 메모리에 올라가 있는 시작 위치, 14000번에다가 논리적 주소 346를 더해준다. base register는 프로그램의 시작 위치를 저장한다.
한가지 체크해야하는 것, limit register이다. 이 프로그램의 최대 크기가 있을 것이다. 예를 들어 P1은 크기가 3000번지까지 가지고 있는 프로그램이다. limit register는 프로그램의 크기를 담고 있다. 만약 이 프로그램이 악의적인 프로그램이라서 본인의 크기는 3000인데, 메모리 4000번지의 내용을 달라고 요청할 수도 있다. 이렇게 되면 물리 주소는 18000이 되고 다른 프로그램의 물리적 주소를 참조하게 된다. 남의 프로그램 메모리를 보려고 하는 악의적인 의도의 접근이다. CPU가 특정 메모리 주소를 요청했을 때, 이 논리 주소가 프로그램 크기보다 더 큰지 아닌지 확인한다. 만약 더 큰 주소를 요청했다면 trap이 걸린다. trap이 걸리면 CPU 제어권이 프로세스에서 운영체제에게 넘어간다. 그래서 운영체제가 프로그램이 악의적인 시도를 했다는 것을 판단한다.
사용자 프로그램은 logical address만 바라보고 있다. CPU도 마찬가지. 물리적 주소는 CPU가 주소 요청할 때 그때그때 MMU가 변환해서 알 수 있다.
동적으로 메모리에 올린다는 것은 해당 루틴이 불릴 때마다 메모리에 올린다. 통째로 프로그램 전체를 메모리에 올리는 것이 아니다.
프로그램의 경우 메모리가 균일하게 사용되지 않고, 코드 중 상당 부분은 사용되지 않는 코드일 수 있다. 예를 들어 오류 처리 등등. 사용 안되는 루틴도 포함이 되어있다. 이런걸 다 메모리에 올리는 게 아니고 그때그때 올려서 효율성을 챙긴다.
여기서 다이나믹 로딩은 페이징 시스템 관련해서 운영체제가 직접 관리해주는 게 아니다. 운영체제가 지원해주는 게 아니고 프로그래머가 직접 다이나믹 로딩 하도록 하는 것(라이브러리 통해서). 페이징 기법과는 다른 것!
메모리에 실제 필요한 정보만 올려놓는 것. 다른 말로 Manual Overlay. 운영체제 지원 없이 프로그래머가 코딩을 통해 하는 것이다.
프로세스를 메모리에서 통째로 하드디스크로 쫓아내는 것이다.
중기 스케줄러는 swap out 시킬 프로그램을 결정하는 것.
메모리에 너무 많은 프로그램 올라와 있으면 비효율적이다. 중기 스케줄러는 CPU 우선순위가 낮은, 당장 CPU 얻지 않아도 되는 프로세스를 우선 적으로 쫓아낸다.
runtime binding 방식이 효율적이다. 아무 메모리 영역으로 swap in 할 수 있기 때문이다.
Linking이란 프로그램을 작성하고 컴파일 한 다음 link해서 실행파일은 만든다. 즉, 여러군데 존재하던 컴파일된 파일들을 묶어서 하나의 실행파일을 만드는 것이다. 라이브러리 다른 파일 등등..
shared object, shared library, dll 이 다이나믹 linking 하는 파일이다.
물리적인 주소부분은 낮은 주소부분에 운영체제 커널이 있고 높은 주소 부분에는 사용자 프로그램이 올라가 있다. 사용자 프로세스가 영역에 할당될 때 연속할당과 불연속 할당이 있다.
프로그램이 메모리에 통째로 올라가는 방식이 연속 할당이다. 주소변환도 비교적 간단하다. 불연속 할당은 프로그램을 구성하는 주소공간을 잘게 쪼개서 일부는 이쪽에 일부는 저쪽에 올라가 있는 방식이다.
현대 시스템은 불연속 할당을 쓰고 있다. 프로그램 주소공간을 페이지라는 단위로 잘라서 쓴다. 나중에 설명
고정분할 방식은 프로그램이 들어갈 사용자 메모리 영역을 미리 파티션으로 나누어 놓는 것. 크기를 균일하게 나눌 수도 있고 아닐 수도 있다.
가변분할 방식은 미리 나눠놓지 않는 것.
외부조각: 프로그램을 메모리에 올리고 싶은데, 올리려는 프로그램보다 메모리 조각 크기가 작아서 사용이 안된 공간.
내부조각: 프로그램의 크기가 메모리 조각 크기보다 작아서, 할당 시에 사용 안되는 메모리 조각.
이건 상당히 간단한 해석.
홀들이 산발적으로 생기게 된다.
여러 홀 중에 어디다 새로운 프로그램 집어넣을지 문제. 가변 분할 방식에서 생기는 문제.
First-fit은 제일 처음 발견된 홀에다가 프로그램 올림.
Best-fit은 홀을 다 살펴본 뒤에 가장 잘 맞는 홀에다가 프로그램을 올린다. 프로그램 크기와 가장 근접한 홀.
Worst-fit은 가장 큰 hole에다가 할당한다. 좋은 방법은 아님.
홀을 한군데로 몰아서 큰 홀로 만드는 것. 비용이 굉장히 많이 드는 방법이다.
페이징 기법이란 프로그램을 구성하는 논리적인 메모리를 동일한 크기의 페이지로 잘라서 물리적 메모리의 적당한 위치에 올라갈 수 있게 해준다.
page table이란 논리적 페이지들이 물리적으로 어디에 올라가 있는지.
프로그램 메모리들이 어떤 page frame에 올라가 있는지
그럼 page table은 어디에 저장해야 할까? 꽤 큰 용량이다.
메모리를 한번 접근하기 위해 메모리 접근을 2번은 해야한다. 일단, 한번은 페이지 테이블을 통한 주소변환을 위해서 메모리 접근 필요. 그 다음에는 실제 메모리 접근 위해서 접근.
기존에 register 2개가 있었는데, 이 2개가 paging 기법에서는 page-table base register와 page-table length register 라는 용도로 사용이 된다. 메모리 상 페이지 테이블이 어디에 있는지, 페이지 테이블의 길이를 레지스터가 값으로 가지고 있다.
메모리 2번 접근하는데 시간이 2배로 걸리다보니 속도 향상을 위해 별도의 하드웨어를 사용한다. TLB. 일종의 cache
메인 메모리와 CPU 사이에 존재하는 주소변환을 해주는 계층이다.
메인 메모리 윗단에 캐쉬 메모리가 있다. 메인 메모리에서 빈번히 사용되는 데이터를 캐쉬에 저장해서 CPU가 조금 더 빨리 접근할 수 있도록 한다.
TLB는 주소변환을 위한 캐쉬 메모리. 그냥 데이터 메모리와는 차이가 다르다. TLB는 테이블에서 빈번히 참조되는 일부 엔트리를 캐싱하고 있다. 메인 메모리보다 접근 속도 빠르다.
CPU가 논리적 주소의 변환을 요구하면 메모리 상에 있는 page table을 접근하기 전에 TLB를 먼저 확인한다. TLB에 있는 정보만으로 주소변환이 가능한지 확인.
TLB에 있다면 메모리 접근을 한번만 해도 된다. 그렇지 않다면 page table 확인했다가 메모리 접근해야 하기 때문에 2번 메모리 접근해야 한다.
TLB는 페이지 테이블의 일부 정보를 담고 있다. TLB는 <논리적인 페이지 번호 P, P에 대한 주소변환된 프레임 번호 F> 이 두개를 쌍으로 가지고 있어야 한다. 이 점이 page table과 차이점. 즉, 논리적 페이지-물리적 페이지 쌍을 가지고 있어야 한다.
그리고 TLB 전수검사 해야한다. 시간이 오래걸린다. 그래서 TLB는 주로 병렬적 검색이 가능한 Associative Register를 이용해서 구현을 하고 있다.
Page table을 통한 주소변환은 엔트리 전부 서치할 필요 없다. 배열처럼 p라는 인덱스로 주소변환 가능하다.
page table이라는 게 프로세스마다 존재한다. TLB도 프로세스마다 다른 정보가 된다. 따라서 TLB는 context switch될 때 flush를 통해서 모든 내용을 비워야 한다.
그럼 실제로 접근하는 시간은 어떻게 될까? 위 화면
결과적으로 page table만 있을 때보다 빨라진다.
왜 이렇게 할까? 속도는 안 주는데 page table을 올려두는 공간이 작아진다. 그래서 하는 것.
현대의 컴퓨터에서는 메모리 주소 체계가 굉장히 크다. 주소 하나가 32bit. 최근에는 64bit 쓰는 아키텍처도 있다. 메모리의 주소는 바이트 단위로 나타낸다. 0번지는 0번 바이트, 3000번지는 3000바이트째 주소가 된다. 32bit 주소는 2의 32승까지 위치 구분이 가능하다. 즉 32bit 주소를 쓴다면 메모리 주소는 0번지부터 2의 32승-1 번째까지 주소를 메길 수 있다. 따라서 32bit 주소체계를 통해서 표시할 수 있는 메모리 주소는 2의 32승 바이트이고, 각 프로그램이 가질 수 있는 최대 메모리 크기는 4G의 주소공간.
총 4GB의 논리적 주소체계(프로세스 주소체계)를 페이지 단위로 나눈다. 페이지의 크기는 4KB이다. 총 4GB의 공간을 4KB짜리 페이지로 쪼갠다면, 페이지 1M개가 나온다. 그러면 page table의 엔트리도 1M개, 이상의 엔트리가 필요하다. 이 페이지 테이블도 메모리 위에 올라가야 한다. 각 프로그램마다 페이지 테이블이 따로 있는데 이걸 다 메모리에다 넣으면 공간 낭비가 심하다. page table 엔트리 크기 하나가 4바이트 정도는 된다. 그럼 프로그램마다 페이지 테이블을 위해서 4MB의 공간이 필요하다. 즉, 4MB의 페이지 테이블이 프로세스마다 필요하다. 그래서 2단계 페이지 테이블을 쓴다.
그런데 4GB나 되는 주소체계 전체 메모리 주소공간이 매번 필요한 것은 아니다. 맨 위에는 코드, 데이터가 있고 맨 아래가 스택이고 중간에는 거의 사용 안되는 논리적 주소가 위치하고 있다. 반면 페이지 테이블은 엔트리를 중간에 빼고 만들 수는 없다. 순차적으로 만들어야 한다. 따라서, 주소체계 중에 상당히 일부분이 사용되지만 페이지 테이블 엔트리는 다 만들어져야 한다. 공간 낭비가 심한 것!
여기서 안쪽 페이지 테이블의 크기는 메모리의 페이지 크기하고 똑같다. 안쪽 페이지 테이블은 테이블 자체가 페이지화 되어서 페이지 어딘가에 들어가있게 된다. 페이지 하나의 크기가 4KB이기 때문에 안쪽 페이지 테이블 크기는 4KB이다. 페이지 테이블 엔트리 하나는 보통 4바이트. 그래서 안쪽 페이지 테이블에서 엔트리 개수는 1000개, 1K개이다.
page 하나의 크기가 4KB. 4KB 안에서 주소 구분을 하려면 몇 비트가 필요할까? 4KB = 2의 12승 바이트. 이만큼을 구분하기 위해서는 12비트가 필요하다. 그래서 d=12가 되어야함.
나머지 20비트로 어떻게 안쪽 페이지 비트와 바깥쪽 페이지 비트로 나눌 것인가? 아까 안쪽 페이지 테이블이 페이지화 되어서 들어간다고 했다. 그래서 엔트리 수가 1K개가 있었다. 1K개의 엔트리 개수를 구분하기 위해서 P2는 몇자리가 되어야 할까? 1K=2의 10승. 따라서 P2는 10비트가 필요하다. P1은 32-12-10 = 10비트가 된다.
만약 32bit 주소체계가 아니고 64bit 주소체계라고 해보자. 페이지 크기는 똑같이 4KB이고 2단계 페이지 테이블을 쓴다. 생각해보기!
아까 공간을 줄이기 위해 2단계 페이지 테이블을 쓴다고 했다. 하지만 2단계 페이지여도 여전히 안쪽 테이블 엔트리는 100만개 이상이 필요하다. 더불이 바깥쪽 페이지 테이블이 필요해서 공간적으로도 사실 손해다. 시간도 2번 거쳐야 한다.
그런데도 2단계 페이지 테이블 쓰는 이유는 다음과 같다. 주소체계에서 상당 부분은 사용되지 않는다. 사용되는 페이지 수는 몇개 안된다. 그런데 페이지 테이블이라는 것은 사용되지 않는 부분을 빼고 엔트리를 만들 수는 없다.(배열을 생각해보자) 사용이 안돼도 최대 논리적 메모리 크기만큼 페이지 테이블에 엔트리 수가 만들어져야 한다. 하지만 2단계 페이지 테이블을 쓰면, 바깥쪽 페이지 테이블은 전체 논리적 메모리 크기만큼 만들어지지만 사용되지 않는 주소는 안쪽 페이지 테이블이 만들어지지 않는다. 실제 사용되는 메모리 영역에 대해서만 안쪽 페이지 테이블이 만들어져서 주소를 가리키고 있다. 사용 안되는 부분은 바깥쪽 테이블에서 NULL로 값이 비워져있고 안쪽 테이블 없다. 그래서 공간을 더 줄일 수 있는 것! 사용되지 않는 주소에 대해서 안쪽 페이지 테이블이 만들어지지 않기 때문
꼭 2단계가 아니고도 여러 단계의 페이지 테이블 쓸 수 있다. 다만 주소변환을 하려면 페이지를 여러번 거쳐야 한다. 그렇지만 TLB로 대부분의 주소변환이 직접 이뤄지기 때문에 다단계여도 시간이 그렇게 오래 걸리지는 않는다.
valid-invalid bit가 있다. 사용이 되지 않는 page table을 나타내는 비트이다. valid라면 실제 메모리에 해당 페이지가 올라와 있다는 의미이고 invalid라면 페이지가 프로그램에 의해 사용되지 않거나 당장 필요하지 않아서 하드디스크(backing store)에 내려가 있는 경우.
페이지 중에는 프로그램 코드 부분도 있고 데이터나 스택 부분도 있다. 코드 부분은 내용이 바뀌지 않아야 한다. CPU에서 읽어서 명령어 실행하는 용도이다. 그렇기 때문에 코드 영역은 read-only. 데이터나 스택 영역은 데이터를 쓰고 업데이트 하는 게 가능하기 때문에 read/write 권한을 가진다. 따라서 protection bit는 연산에 대한 권한을 표시하기 위한 비트이다.
Page table은 많은 용량을 차지하는 게 문제이다. 이를 막기 위해서 나온 페이지 테이블이 Inverted Page Table 이다.
원래 페이지 테이블의 역발상. 원래 페이지 테이블은 프로세스마다 존재했다. 이건 시스템 안에 페이지 테이블이 하나가 있다. 프로세스마다 있지 않다. 페이지 테이블의 엔트리가 프로세스의 페이지 개수만큼이 아니라 물리적 메모리의 페이지 프레임 개수만큼 존재한다. 그래서 페이지 프레임의 F번째 엔트리를 가면 논리적 페이지 번호가 나오도록 하는 것.
근데 원래는 논리적 주소를 물리적 주소로 바꾸는 건데 이건 반대다. 이를 통해 주소변환 하려면 어떻게 해야하는가? 그냥 페이지 테이블을 전수검사 한다. 처음부터 다 검색해서 위에서 f만큼 떨어진 엔트리가 논리적 주소값 p를 가지고 있다면, 페이지 p는 f번째 프레임에 올라가 있다.
공간을 줄이고자 하지만 시간적 오버헤드가 든다. 프로세스를 나타내는 프로세스 아이디도 같이 가지고 있어야 한다. 특수한 레지스터를 쓰면 탐색에 드는 시간을 줄일 수는 있다.
서로 다른 프로세스들이 같은 코드를 가지고 프로그램을 돌린다면, 프로그램 코드 부분은 3 프로세스가 똑같이 써도 된다. 데이터 부분만 내용이 바뀐다. 공유하는 코드 부분은 물리적 메모리에 한번만 올리고 이를 공유해서 쓴다.
shared code는 두가지 조건을 만족해야 한다. 첫번째는 read-only 페이지여야 한다. 두번째는 shared code는 동일한 logical address에 위치해야 한다. physical address 같은 것은 당연하다. 왜냐면 코드 안에는 logical address가 존재한다.
segmentation은 프로세스를 구성하는 주소공간을 의미 단위로 쪼개는 것. 예를 들어 코드, 데이터, 스택 이런 것들은 주소공간 중에 의미를 가지는 단위들이다. 이 각각이 segment가 되는 것이다.
CPU가 논리주소를 주게 되면 이 주소를 세그먼트 번호 s, 세그먼트 내에서 떨어진 offset d로 나눈다. 세그먼트 번호를 통해서, 세그먼트가 물리적 메모리에서 어떤 번지에 올라가 있는지를 가지고 있다. 세그멘테이션 기법은 페이징과 다르게 엔트리에 두 가지 정보를 가지고 있다. 물리적 메모리 상의 시작 위치인 base 말고도, limit이라는 세그먼트 길이를 나타내는 값을 가지고 있어야 한다. 페이지는 페이지 프레임 크기가 다 동일했지만 세그먼트는 의미 단위로 자르는 거라 세그먼트의 길이가 균일하지 않을 수 있다.
주소변환 시, 세그먼트 번호가 유효한지 확인한다. 예를 들어서 세그먼트 3개로 구성된 프로그램에서 세그먼트 번호가 5인 주소가 들어온다면 잘못된 요청이다. 따라서 s < STLR(이 프로그램을 구성하는 세그먼트 개수)
그리고 만약 세그먼트의 길이가 1000바이트인데 세그먼트 안에서 떨어진 위치를 2000바이트를 요청했다면 이것도 문제이다. 세그먼트의 길이보다 세그먼트 안에서 떨어진 오프셋이 크지 않은지 확인한다. 정상적인 주소라면 변환을 하고 아니면 트랩 발생.
이 기법에서는 세그먼트의 길이는 offset d로 표현할 수 있는 비트수 이상은 안된다.
세그먼트 방식은 세그먼트 크기가 균일하지 않아서 문제가 발생할 수 있다. 외부조각 발생 가능. first fit/best fit 써야 한다.
장점은 의미단위로 쪼갰기 때문에 의미단위로 일할 때 효과적이다. 예를 들어 protection 할 때, 페이징보다 의미단위로 read-only 권한을 주거나 write 권한을 주는 게 더 자연스럽다. sharing도 의미단위로 하는거지 동일한 크기로 잘라서 하는 게 의미가 없다.
세그먼트의 경우 세그먼트 테이블의 엔트리 개수가 프로그램이 사용하는 세그먼트 개수가 된다.
페이지는 개수가 1M 이런 식으로 굉장히 많다. 테이블을 위한 공간 낭비도 굉장히 심하다. 세그먼트 방식은 의미 단위로 무언가를 할 때, 공유나 보안에 목적이 있을 때는 유리하다. 페이지 방식이 더 유리할 때도 있는데, 페이징은 물리적 메모리 조각이 발생하는 일이 없었다. 크기가 균일하기 때문이다. 세그먼트 방식은 allocation 문제가 발생한다.
페이지는 개수가 굉장히 많고 세그먼트는 개수가 많이 없다. 테이블을 위한 메모리 낭비는 페이징이 더 심하다.
세그먼트 하나가 여러 페이지로 구성이 된다. 메모리에 올라갈 때는 페이지 단위로 쪼개져서 올라가게 된다. allocation 문제가 안 생긴다는 장점이 있다. 어차피 물리적 메모리에는 페이지 단위로 올라가기 때문이다. 세그먼트라는 건 페이지 개수의 배수로 구성이 된다. 공유나 보호 목적은 세그먼트 차원에서 해준다. 두 방식의 장점을 모두 갖추고 있다.
세그멘테이션에 대한 주소변환 하면 페이지 테이블의 시작 위치가 나온다. 세그먼트 하나가 여러 페이지로 구성된다. 따라서 세그먼트당 페이지 테이블이 존재한다.
d을 다시 잘라서 앞 부분을 페이지 번호로 쓰고, 뒷 부분을 페이지 안에서 얼마나 떨어져 있는지 offset으로 쓴다.
주소변환에 있어서 운영체제의 역할은 없다. 하드웨어가 해줘야 하는 역할이다. 어떤 프로세스가 CPU를 잡고 실행하고 있으면서 메모리 접근을 할 때 운영체제의 도움을 전혀 받지 않는다. 주소변환을 할 때마다 운영체제의 개입이 필요하다면 CPU가 프로세스에서 운영체제로 넘어가야 한다. 이건 말이 안된다.
프로세스가 CPU를 가지고 있으면 매 CPU clock cycle마다 메모리에서 어떤 instruction을 읽어와서 CPU에서 실행을 하고 이 모든 과정은 주소변환을 통해서 메모리 접근을 이뤄지는데 이럴 때마다 CPU가 운영체제에게 넘어갔다 다시 넘어오고 할 수가 없다.
IO 장치 접근은 운영체제가 끼어들어야 한다. 사용자 프로세스가 직접 IO 접근 못하기 때문이다.
