[운영체제] Operating System 정리 7

8. Main Memory

 

 

각 프로세스는 독립된 메모리 -> 메모리 내 주소 : physical address

-> 특정 프로세스가 가질 수 있는 legal address를 정하고, legal한 영역만 접근할 수 있도록 보호가 필요.

base (relocatable) register : 가장 작은 legal address

limit register : 주어진 legal 범위의 size.

이 두 register는 process 별로 가지고 있는 값이고 서로 겹치면 안 된다.

basic hardware : base <= n < base + limit 이 한 process의 범위이고, 이 조건을 만족해야 접근이 가능하다.

(CPU에서 address를 보내면 이거를 먼저 체크한다. -> logical address)

프로그램이 실행되려면 memory로 와서 process가 되야 한다.

-> user program은 실행되기 전 다양한 단계를 거친다.

-> 주소는 이 step 별로 다른 형태로 보여질 수 있다.

1. symbolic (상대 주소)

2. compiler가 symbolic 주소를 relocatable 주소로 bind.

3. linkage editor 또는 loader가 relocatable 주소를 진짜 주소와 bind.

1. compile time : process가 memory에 어디에 존재할지 이 시간에 알게되면 absolute 코드가 만들어질 수 있다.

2. load time : compile time에서 process의 위치를 모를 때 relocatable code를 compiler가 반드시 생성해야 한다.

3. execution time : process가 실행 도중 메모리의 segment로 다른 segment로 이동이 가능하면 binding도 지연된다.

 

 

logical address : CPU(program)가 생성한다.

physical address : 메모리가 취급한다.

compile time과 load time의 bind method는 identical한 logical, physical address를 생성한다.

execution time에서 bind method는 서로 다른 logical, physical address를 생성한다. (logical = virtual)

MMU가 run-time에 logical address와 physical address를 연결한다.

relocation register의 값이 user process에서 생성 된 address(logical)이 memory로 이동할 때 항상 더해진다.

=> user program은 real physical address를 알 수 없다.

 

relocation : 계속 바뀌다가 absolute가 되면 절대 주소로 변한다.

process는 일시적으로 memory에서 방출되어 store되다가 다시 memory로 와서 실행이 될 수도 있다. -> swapping

-> 이거 multiprogramming 환경의 Round-robin CPU scheduling이랑 선점형 생각하면 된다.

CPU가 프로세스를 실행하려고 마음 먹으면 -> dispatcher를 부르고 dispatcher는 queue의 process가 memory에 있는지 확인한 후, 없고 메모리에도 공간이 없으면 메모리의 한 프로세스와 원하는 프로세스를 swap 시킨다.

-> transfer time이 중요하다. (memory swap 횟수와 비례)

=> user process가 얼마의 memory를 사용할지 정확이 알면 좋다. -> 필요한 부분만 swap하여 소요 시간을 줄인다.

process를 swap하려면 CPU 상황이 idle해야 하는데, I/O가 user memory에 접근 중이면 swap이 불가능하고, system에 많은 프로세스가 사용 중이고, 거의 메모리의 한계까지 사용 중이면 swap을 진행한다.

모바일 기기는 flash memory를 사용하는데 용량이 작고 write cycle 수의 한계와 main memory와 flash memory의 성능이 나쁜 이유로 swap이 불가능하다. 그래서 iOS나 안드로이드나 그냥 종료 후 재시동하는데 안드로이드는 빠른 재시작을 위해서 application state를 flash memory에 작성해 둔다.

 

memory : resident OS, user processes => memory에 많은 프로세스를 넣고자 한다.

degree of multiprogramming = partition의 수 (한 partition 당 한 프로세스)

partition에 자리가 비면 input queue에서 프로세스를 빼서 넣는다. -> process가 종료되면 그 partition은 free(hole)가 된다.

=> table을 통해 볼 수 있다.

requested size를 hold에서 할당하는 방법 3가지

1. first fit : 첫번째 사용 가능한 공간을 할당한다.

2. best fit : 남은 것 중 가장 작은 공간을 (request size보단 크고) 선택한다. size대로 정렬되어 있어야 하고, 작은 size의 남겨진 hole이 많아진다.

3. worst fit : 가장 큰 공간을 할당한다. 이것도 정렬이 필요하고, 남은 부분은 또 다른 프로세스가 사용할 수 있다.

1, 2가 storage utilization, decrease time 측면에서 3보다 좋다.

 

Fragmentation : 단편화. 공간 중 일부가 사용하지 못하게 되는 것.

external : 모두 합치면 큰데 연속적이지 않고 부분 부분이라 너무 크기가 작아서 사용이 불가능한 것.

internal : 할당 공간이 요구 공간보다 큰 경우

-> external은 compaction(압축)을 통해서 해결한다.

=> 모든 memory의 내용을 몰고, hole도 몰아서 큰 블록을 생성한다. (process 재배치가 실행시간에 동적으로 이뤄져야 가능)

segmentation : <s, d> = segment number, offset

limit, base -> offset이 limit보다 작은지 확인해야 한다.

paging : 비연속이 가능하고, external fragment는 없지만 internal fragment가능. paging size가 작아야 한다.

physical memory는 frame으로 나누고 logical memory는 page로 나눔. (page끼리 같은 size, frame끼리 같은 size)

page number = p, page offset = d / paging size = page 크기. 작아야 좋지만 관리할 것이 많아진다.

page number = index of page table : base address of each page

page table의 frame number가 physical address가 된다.

paging size는 2^n이 일반적이고, logical address의 space가 2^m이고, page size가 2^n 이면, page offset = n bit를 사용하고 paging number는 m-n bit를 사용하게 된다.

-> overhead는 page마다 붙게 되는데, page size가 클수록 overhead도 작아지고 I/O도 더 효율적임. 그래도 page size는 작아야.

frame table은 그 frame이 free인지 특정 정보로 차있는지 알려준다. (page frame에 대해 each entry를 가진다.)

hit ratio : percentage of times that particular page number is found in TLB

TLB에 저장해서 access time을 줄여준다.

TLB 소요 시간 : search TLB + access memory

TLB에 없을 때 소요 시간 : search TLB + access memory for page/frame number + access desired byte in memory

한 추가 bit로 valid인지 아닌지 나타낸다. -> logical address space에 있다/없다.

 

reentrant(pure) code이면 share가 가능하다.

-> 수행하는 동안 절대로 프로그램의 내용이 변하지 않아서 두 개 이상의 프로세스가 동시에 같은 코드를 실행 가능한 것.

(예를 들면 읽기전용 파일)

 

Hierachical paging : page table이 과도하게 커질 때.

32bit logical address space일 때 page size가 4MB면 page offset = 12 bit이고, page table은 20 bit를 가진다. each entry가 4B만 가져가도 4MB만큼 physical address space가 page table만을 위해 필요해 진다.

=> 효율성을 위해 나눠서 관리하자.

2level paging table : outer page table -> page table -> memory

 

VAX architecture : 이것도 2level인데 s, p, d로 구성되어 있고, s가 각 page table의 number를 나타낸다.

근데 64bit이면 2level이라도 사이즈가 커서 3level이 되어 2nd outer page가 등장한다.

 

Hash page table : access의 속도는 증가했지만, collision이 가능해서 연결리스트로 구성되어 있다.

p가 hash에 들어가서 frame번호를 가져온다.

 

Inverted page table : 메모리 frame마다 하나씩 할당하여 logical에서 physical이 대응하는 부분만 저장한다. -> 훨씬 적은 공간

 

intel 32 64 architecture도 hierachical paging 기법을 사용하고, 64bit는 unused bit부분이 있다.