여행 사진

Memory Management

Memory Management

2016년 5월 26일 목요일

오후 9:07

1.   모든 프로세스는 실행되기 위해 반드시 메모리 위에 있어야 한다.

·       CPU가 알고 있는 주소는 메모리 주소밖에 없기 때문.

·       멀티태스킹을 해야하므로 management 필요.

2.   프로그램은 원래 이진 실행파일 형태로 디스크에 저장되어 있다.

실행되기 위해서는 메모리로 올라와서 프로세스가 되어야 한다. 이를 위해서는 여러 단계를 거쳐야 한다.

·       Source - (Compile) - object module - (linking - 다른 object module과 ) - load module

- (loader) - 동적 링킹(exe 파일에서 호출이 있을때 linking)

·       Address Binding(주소 할당)은  할당이 이루어지는 시점에 따라 3가지로 구분된다.

a.   Compile time binding

·       컴파일 시에 메모리에 올라갈 주소를 미리 알 수 있으면, absolute code 생성 가능.

·       시작주소가 변경된다면 recompile 해야 한다. ( ex. DOS)

·       Logical 주소와 physical 주소가 동일

b.   Load time binding

·       컴파일러는 코드를 relocatable code로 만들고, 이후 프로그램이 메모리로 실제 적재되는 시간에 주소 할당.

(단순히 논리 주소에 실제 시작주소를 더하는 방식)

·       시작주소가 변경된다면 재 적재하면 된다.

·       한번 메모리에 올라오면 주소를 바꿀 수 없다.

·       Logical 주소와 physical 주소가 동일

·       Execution time binding

·    프로세스가 실행하는 중간에도 계속해서 할당이 이루어 지는 방식.

·    프로세스 실행 도중에도 메모리상의 위치를 변화시킬 수 있다.

·    CPU는 오직 상대주소로만 메모리에 접근할 수 있다.

·    CPU가 프로세스에 접근할 때마다 binding이 이루어져야 한다.(별도의 자료구조 - address mapping table 필요)

·    하드웨어 지원 필요(base, limit 레지스터, MMU(memory management unit)- 논리주소를 실제주소로 변환 역할)

·    Logical 주소와 physical 주소가 다르다.

·    유저 프로그램은 physical address를 알 수 없다. 유저 프로그램이 발생시킨 모든 주소는 MMU가 relocation register(base register)를 더하여 실제 주소로 변환한다.

+) address mapping table : logical address(CPU가 제시한 주소)에 해당하는 physical address(실제 메모리 내

   주소) 값을 유지하는 테이블

+) Base and limit register : logical address space를 정의하는 레지스터 값, base(시작), limit(크기)

Q] 왜 끝번지 말고 길이를 저장?

A] 접근 요청시 address가 합법적인지 검사 후 실제 메모리주소 반환한다. 길이는 최대의 Offset.

CPU가 발생시킨 Offset을 길이와 비교하여 합법적인 접근인지 판단하기 아주 용이하기 때문이다.

Q] 배열은 연속적인 주소공간을 가진다?

A] 이 주소공간은 logical address이다. 실제 메모리 상의 physical address 주소의 연속을 의미하지 않는다.

MMU가 이를 관리하므로 배열은 실제 메모리 상에서는 흩어져서 저장될 수 있다.

·       Dynamic Loading

·       각 루틴은 실제 호출되기 전까지는 디스크에서 대기, 루틴 호출 시 먼저 이미 메모리에 있는지 조사하고, 없다면 적재한다.

·       장점 두 가지 1) 메모리의 효율적 사용(아주 드물게 발생하지만 많은 코드를 갖는 경우, 미리 적재되지 않는다.)

 2) 공유될 수 있다(dll 파일같이 읽기 전용 파일은 공유가 되어도 된다.

                        Address space에 포함시켜 미리 올려주면 중복해서 계속 올라갈 수 있다.)

·       Dynamic Linking

·       Linking이 실행 때 까지 미루어진다.(주로 시스템 라이브러리에 사용, 라이브러리를 실제로 사용할 때 link 한다.)

·       Swapping

·       프로세스가 실행도중에 일시적으로 디스크로 보내졌다가 나중에 다시 메모리로 돌아오는 것

·       Contiguous Allocation

·       주 메모리 : OS가 상주하는 부분(low memory with interrupt vector), 유저 프로세스가 상주하는 부분(high memory)

o   single-partition allocation(MMU가 Logical 주소를 base에 더해서 physical 주소로 변환, protection 담당.)

·       Logical address > limit register : trap// else relocation register(base) + logical address -> physical address

o   Multiple -partition allocation

·       Single partition보다 오버헤드 적다. (주소가 아닌 파티션 번호로 관리 가능)

·       Hole 발생(C.A의 특징), 다양한 크기의 Hole들이 메모리 전역에 생긴다. 이 공간들을 어떻게 할당할 것인가

o   Dynamic storage allocation problem

·       First fit    : 첫 번째로 충분히 큰 가용 공간 할당

·       Best fit    : 사용 가능한 공간들 중 가장 작은 것 선택, 전체 리스트를 탐색해야 함. 많은 small hole을 만들어 낸다.

·       Worst fit  : 가장 큰 hole 선택. 전체 리스트를 탐색해야 함.

·       Fragmentation(단편화, 메모리공간을 낭비하게 됨)

o   External fragmentation : 할당되지는 않았지만, 너무 작아서 쓸 수 없는 공간.

(compaction 하면 쓸 수 있지만 오버헤드(메모리 카피)가 너무 커서 구현 힘들다. 또한, 프로세스의 재배치가 실행시간에 동적으로 이루어 지는 경우에만 가능)

o   Internal fragmentation : 할당은 되었지만 실제로 쓰이지 않는 공간. 단위 규격으로 할당 시 발생한다.

·       Partition으로 나누어 관리 시 주소관리 오버헤드 없어지고, 메모리 관리속도 상승. But, internal fragmentation 발생.

Internal 을 줄이려면, partition을 작게 만들면 되고, external을 없애려면 프로세스도 partition화 하면 된다.  

·       Paging

·       Address space를 page 단위로 쪼개고, physical memory를 frame 단위로 쪼개서 사용한다.

·       External fragmentation은 발생 x, Internal fragmentation만 존재.

·       Frame의 size는 반드시 2의 제곱( 4KB = 2^12)

·       Free frame에 관한 정보, page table(logical address -> physical address) 필요.

·       Address transition (1)

o   ┗Logical address/Page size┛ = page number(이를 page table 사용해 frame의 시작주소로 변환)

o   Logical address - ┗Logical address/Page size┛*Page size = offset(frame 내의 offset과 동일)

·       Address transition (2)

o  

o   Logical address의 하위 n비트는 page offset, 상위 m-n비트는 page number 의미.

o   Logical address p+d일 때, page table에서 p만큼 내려가서 해당 frame의 시작주소 f 얻고, f+d로 변환.

o   Page table 에는 frame 시작주소만 저장하면 된다.(page number 저장 불 필요)

o   메모리(page table)에 한번 접근하는 것이 유일한 오버헤드.

·       Page table은 주 메모리에 위치하며, 위의 방식은 프로세스마다 1개의 page table을 가진다.

·       PTBR(page table을 가리키는 레지스터), PTLR(page table의 size를 나타내는 레지스터 - protection 위해)

·       위 방식은 데이터에 접근하기 위해 총 두 번의 메모리 접근 필요 -> 속도 향상 위해 TLB 사용.

·       TLB(Transition look-aside buffer)

o   Page table을 위한 캐시, 매우 빠른 associative memory로 구성.

o   Protection 위해 ASIDs 사용 하기도 함.(각 entry가 어느 프로세스에 속해있는지 저장.)

·       ASIDs가 있으면, 1개의 TLB내에 여러 프로세스들의 정보를 동시에 보관할 수 있다.

·       없으면, context switch가 발생할 때마다 TLB는 flush 되어야 한다.

o   TLB는 page table의 일부만 저장, 전부 다 탐색해야 함. Parallel search 지원.(한 번의 search로 탐색 완료.)

·       Address transition with TLB

o   CPU에서 logical address(p+d) 발생. P(m-n 비트)가 TLB내에 존재하는지 search.

·       존재 시(TLB hit) f+d

·       존재 안하면(TLB miss), page table에서 p만큼 내려가서 frame 시작주소 얻음. F+d

o   Effective access time(실제 기억장치 접근 시간)

·       Associative lookup a, memory access b, hit ratio c.

·       EAT = c*(a+b) + (1-c)*(a+2b) = a + (2-c)b

·       OS는 각 프로세스에게 가능한 최대 크기의 address space를 제공한다. 주어진 공간을 다 사용하지 않을 때 protection 필요.

o   Valid, invalid bit를 page table의 각 page 항목별로 두어 해당 page가 프로세스의 합법적인 page인지 나타낸다.

o   PTLR 사용하여 검사할 수도 있다.

·       Shared pages

o   여러 프로세스 간에 read only code는 공유되어도 된다.  Code는 공유되어도 그 코드를 위한 데이터는 각자 가짐.

o   단, 반드시 프로세스들의 address space에서 공유되는 page들이 같은 위치에 존재해야 한다.

·       Structure of the page table

·       Hierarchical paging(2 level)

o   32bit 중, 앞의 20bit(page number), 뒤의 12bit(page offset).

o   앞의 20bit 중, 앞의 10bit(page number - page가 1K개 있으므로), 뒤의 10bit는 offset(각 페이지에 1K개의 entry)

o   Logical address = p1+p2+d, p1 = outer-page table의 index, p2 = inner-page table의 페이지 내의 displacement.

o   outer-page table에서 p1만큼 내려와서, inner-page table의 page에서 p2만큼 내려가서, 해당 frame의 시작주소에서 d만큼 내려가서 physical memory address를 얻는다.

o   메모리 접근 3번. 그러나, TLB 사용하면 꽤 효율적.

·       Hashed page tables

o   Page table을 해시로 구현. P+d에서 p를 해시하여 해당 위치에 저장. Collision 발생시 search해야 한다.

o   각 element에 page number, frame number, next element pointer 저장.

·       Inverted page tables

o   각 frame 별로 그 frame에 올라와 있는 page의 주소, 프로세스의 ID 저장.

o   시스템에 단 하나의 페이지 테이블만 존재. 메모리 절약 가능.

o   단점: Page sharing 불가능. 전체 table을 탐색해야 함.(DRAM access 너무 많이 발생. 비효율적)

-> hash, TLB 사용하여 단축 가능.

·       Segmentation

·       사용자의 관점 반영, logical address space를 segment들의 집합으로 정의.(서브루틴, 전역 변수, 지역변수….)

·       Logical address = segment name + offset

·       Segment table의 각 entry에는 base(각 segment 들의 시작주소 저장), limit( 해당 segment의 길이) 값 저장.

·       Segment table은 결국 base, limit register 쌍들의 배열.

·       STBR - segment table의 위치 저장, STLR - 해당 프로세스에서 사용하는 Segment의 수 저장.

·       Dynamic allocation problem 발생

o   각 segment별 로 크기 다양함. First fit, best fit 등 사용, Internal fragmentation x, external fragmentation o

·       Address transition

o   Logical address = s + d, segment table에서 해당 segment의 limit 값 가져와서 d와 비교.

·       Limit >= d - base + d

·       Limit < d - trap

·       장점

o   protection - limit 레지스터를 활용한 illegal access 판단 이외에도, 추가 비트를 사용해 R,W,X등 권한 설정도 가능.

o   Sharing - 간단히 두 프로세스의 segment table이 같은 주소를 가리키는 것만으로 공유 가능. 의미 단위 공유 가능.

(단, 공유하는 프로세스가 모두 이 segment에 대해 같은 번호를 가져야 함. Self reference시 문제 발생 가능.)

·       Segmentation with paging

·       각 segment를 paging!

·       기존 segment table의 segment base를 각 segment의 page table base로 대체.

·       Logical address = s+ d = s+p+d' (s : segment number, p : page number, d' : frame 내의 displacement, offset)

o   S + STBR을 통해 해당 segment table entry에 접근. D와 segment length 비교.

·       segment length >= d -  page table base + p를 통해 frame 번호 f 얻고, f + d'

·       Segment length < d - trap.

·       Segment 간 page table 공유가 가능.

·       실제 사용은 TLB와 결합하여 쓴다.

·       Logical address : s + p + d

o   S + p를 TLB에서 먼저 찾는다.

·       TLB hit -  f + d

·       TLB miss - s + STBR, length >= p+d, page-table base + p, f+d

Deadlock

Deadlock

1.   System model

·       Resource R1,R2,R3….(CPU 주기, 메모리 공간, I/O 장치…)

·       각 Ri는 instances Wi를 가진다.(각 instance들은 서로 동등한 관계, 프로세스는 이를 구분하지 않는다.)

·       프로세스가 자원을 사용하는 순서

o   Request  -> use -> release

2.   Deadlock(교착 상태의 특징)

·       교착상태는 다음 4가지 조건이 모두 만족될 때 발생한다.

o   Mutual exclusion : 한 resource는 한 순간에 한 프로세스만 사용한다.

o   No preemption : 한 프로세스가 자발적으로 방출해야만 다른 프로세스가 사용할 수 있다.

o   Hold and wait : 최소한 하나의 자원을 점유한 채, 다른 프로세스에게 점유된 자원을 위해 대기하는 프로세스가

                      반드시 존재해야 한다.

o   Circular wait : 원형 대기.

3.   Resource-allocation graph

·       그래프는 vertex set과 edge set의 pair.

o   Vertex set : 각 프로세스들 P1, P2, P3… + Resource type R1, R2, R3…

o   Edge set : request edge(Pi -> Ri) + assignment edge(Wi -> Pi)

·       각 프로세스는 원, 자원은 사각형, 인스턴스는 점으로 표시.

·       프로세스가 자원을 요청하면, request edge 추가. 할당 가능하면 즉시 assignment edge 생성.

·       그래프에 cycle이 없다면, deadlock x.

·       그래프에 cycle이 있다면, 각 자원 타입마다 오직 1개의 instance만 있다면, deadlock.

·       각 자원 타입마다 여러 개의 instance가 있다면, deadlock 일수도 아닐 수도.

4.   Deadlock handling 방법에는 3가지가 있다.

a.   Deadlock이 발생하지 않도록 보장.(prevention, avoidance)

b.   Deadlock이 발생하지만, 탐지, 회복할 수 있도록 함.(detection, recover)

c.    Deadlock이 발생하지 않는 것처럼 행동.(대부분의 운영체제가 채택)

                       i.        Deadlock을 예방, 처리 하는 과정이 너무 큰 오버헤드

                      ii.        Deadlock 발생 빈도가 아주 낮다.

5.   Deadlock prevention

·       Deadlock 의 조건 성립을 막아서, deadlock이 발생하지 않도록 보장.

o   Mutual exclusion : 공유가 불가능한 자원들이 존재하므로 방지 불가.

o   Hold and wait : all or nothing

·       1) 각 프로세스가 실행되기 전에 필요한 자원을 모두 요청하고, 모두 할당 받은 후에 실행되게 한다.

·       2) 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있다.

-> 자원 이용도 저하, starvation 가능.

o   No preemption : 만일, 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 자원을 요청하여 대기해야 하면, 그 프로세스가 점유하고 있는 모든 자원이 선점된다. 선점된 자원들은 이 프로세스가 기다리는 자원들의 리스트에 추가되며, 이 자원들을 모두 획득할 수 있을 때에 재 시작 된다.

o   Circular wait : 모든 자원 타입에 순서를 부여하여, 오름차순으로만 요청할 수 있도록 한다.

                   (상위 자원을 점유하고 있으면, 하위 자원 요청 불가.-> 그래프에서 back edge가 만들어지지 않는다.)

6.   Deadlock avoidance

·       Deadlock 발생 가능성이 존재하면, 자원 할당 요청을 받아 들이지 않는다.

·       Unsafe state로는 절대 진입하지 않는다.

·       자원 할당 요청을 들어주었을 때, 발생할 수 있는 worst case를 찾아서 safe한지(circular wait 발생하지 않는지) 검사한다.

 (각 자원 타입 별 최대 자원 요구량 정보 필요)

·       Resource allocation state는 현재 남아있는 자원, 할당된 자원, 최대 자원 요구량에 의해 결정된다.

o   Safe state : 프로세스들이 모두 자원의 최대치를 요구하더라도, deadlock을 야기하지 않고 할당해 줄 수 있는 safe sequence가 존재한다면 safe. 비록 당장 할당이 불가해도, 다른 프로세스의 수행이 끝나고 할당하여 모든 프로세스를 마칠 수 있는 sequence가 존재해야 한다.

o   Unsafe state : deadlock 의 가능성이 존재하는 상태. 반드시 deadlock이 발생하는 것은 아님.

·       Avoidance algorithm

o   Resource allocation graph (각 자원 별 instance가 1개씩 있을 때)

·       Claim edge(Pi -> Rj) : Pi가 미래에 Rj를 요청할 가능성이 있음을 의미

·       프로세스가 실행되기 전에 모든 Claim edge들이 추가되어야 한다.

·       판단 방법: 자원 할당을 가정했을 때 , claim edge를 포함하여 cycle이 만들어 진다면 unsafe 하므로 할당 x.

(해당 request edge -> assignment edge가 cycle을 형성하지 않는다면 할당.)

o   Banker's algorithm(각 자원 별 여러 개의 instance가 있을 때)

·   프로세스 별 필요한 자원의 최대 개수 정보 필요.

·   추가 자료구조 필요.( # of process : n, # of resource : m)

• Available : m 1차원 배열, 각 종류의 자원이 현재 몇 개가 남아있나. Available[j] = k.
• Max : n*m 2차원 배열, 각 프로세스가 최대로 필요로 하는 각 자원의 개수. Max[i][j] = k.
• Allocation : n*m 2차원 배열, 각 프로세스에게 현재 할당된 각 자원의 개수. Allocation[i][j] = k.
• Need : n*m 2차원 배열, 각 프로세스가 추가적으로 필요한 자원의 수. Need[i][j] = Max[i][j] - allocation[i][j]

·   Safety algorithm.

• 시스템이 safety 한지 판단하는 방법.
• work : m 1차원 배열, finish : n 1차원 배열.

·       Work = available, finish[i] = false로 초기화.

·        a) finish[i] == false ,b) need[i] <= work 를 모두 만족하는 i 찾는다.

 (아직 끝나지 않은 프로세스 들 중, 현재 자원을 몰빵하면 끝날 애들을 찾는다. 끝나면 전부 회수.)

·        i를 찾았다면, work = work + allocation[i], finish[i] = true 후 다시 위 조건을 만족하는 i를 찾는다.

·        i가 없다면, 모든 i값에 대해 finish[i] == true 라면 safe. 단 하나라도 false라면 unsafe 이다.

·       Resource-request algorithm.

§  Pi가 자원을 요청했을 때, 줄지 말지 결정하는 방법.

§  Request-i : n 1차원 배열, Pi의 자원 요구량 의미.

·       Request-i <= need-i 이 아니라면 error

·       Request-i <=  available-I 이 아니라면 Pi는 wait.

·       제대로 요청했고, 할당해줄 수 있는 자원이 있다면, 자원을 할당해 준 것처럼 자료구조만 변경해본다.

·       Available = available - request-I, allocation-I = allocation + request-I, need-I = need-I - request-I

·       이 상태에서 safety 알고리즘을 적용하여, safe하다면 자원을 실제로 할당한다. Unsafe하다면 자료구조를 복구 후 Pi는 wait한다.

6.   Deadlock detection

·       Deadlock에 들어갔을 때, 탐지 및 회복하기 위한 방법 필요.

·       Detection algorithm.

o   Wait-for graph(각 자원 별 1개의 instance 존재 시)

·       노드는 process Pi만 존재, Pi -> Pj (Pi는 Pj가 현재 점유중인 자원을 기다리는 상태.)

(노드의 개수를 줄여 complexity 줄이기 위함.)

·       Cycle의 존재 여부를 검사, 존재한다면 deadlock.

§  Reduction of resource graph(cycle 탐지에 사용)

·       각 프로세스가 dormant state에 있다고 가정.(추가적인 자원 요청을 하지 않는다.)

·       각 프로세스는 자원을 얻고, 작업 완료 후, 전부 반납한다고 가정.

·       자원을 요청하지 않는 프로세스와 edge를 같이 지우고, 연쇄적으로 reduce한다. Irreducible == deadlock!

·       Reduction order는 무관하다.

o   Deadlock detection algorithm.

·       Work = available // allocation[i] = 0 이면 finish[i] = true, 아니면 false.

·       a)  finish[i] == false && b) request[i] <= work (안 끝난 애들 중, 요청 량이 현재 남은 것으로 해결 가능하다면)

·       Work = work + allocation, finish[i] = true 후 위 조건 만족하는 프로세스 계속 탐색.

·       만족하는 프로세스가 없다면, finish[i] 가 모두 true라면 deadlock x, 하나라도 false라면 deadlock o.

-> banker's algorithm과 다르게 프로세스들이 dormant state라고 가정 + 현재 상태만 고려.

8.   Recovery from deadlock.

·       Process termination(둘 중 하나)

o   Deadlock에 빠진 프로세스를 모두 중지. -> 모든 프로세스의 연산 결과들이 모두 소실되므로 비용이 크다.

o   Deadlock이 제거될 때까지 하나씩 중지. -> 계속해서 detection 수행해야 하므로 오버헤드가 크다.

·       Resource preemption(세가지를 모두 고려)

o   Selecting of a victim - victim process를 선정해서, 자원을 선점하는 방식.

o   Rollback - 그 process를 safe state로 후퇴시키고, 그 상태부터 재 시작. -> 이전 정보를 갖고 있어야 함.

o   Starvation - 같은 process가 반복적으로 victim이 되지 않도록 보장해야 함.(# of rollback을 카운트)

9.   Avoidance : worst case( 모든 프로세스가 동시에 maximum 자원 요구) 시에도 safe sequence가 존재할 때만 할당.

Detection : best case(모든 프로세스가 추가 자원 요구 x), 현재 자원 요구량 만 고려.