[운영체제/OS] Memory

Memory

Basics : Storage (write) and Retrieval (read) of information in Memory

 

DRAM  : Dynamic Random Access Memory

Programs are usually stored in the hard disk 

-> progams are executed (= process), it is loaded on the main memory - faster than disk

= 프로그램은 주로 hard disk에 저장되고, 이 프로그램이 실행된다면 (프로세스가 된다면), 좀 더 빠른 main memory에 올라간다.

 ex) file을 열면, main memory에 올라간다.

 

hard disk에 main memory가 byte code 형태로 저장되고, process 형태로 load하여 main memory에 저장된다.

 

이때, DRAM의 속도는 Disk 보다 10만 배 빠르기 때문에 프로그램을 memory에 load 한다.

속도 : DRAM > SSD > Disk

 

SRAM 

DRAM은 CPU 보다 더 느리다 (DRAM에 접근하려면 100-400 CPU cycle이 걸린다)

-> 작지만 매우 빠른 메모리인 캐시(cache)를 사용

 

hardware system은 cache에 해당 데이터의 존재 유무, 데이터 관리 등 모든 cache에 대한 것들을 다루게 되는데 

OS 관점에서는 main memory와 cache를 하난의 memory로 생각하기 때문에 , main memory만 있다고 생각하고, 명령만 내리게 된다.  

 

 

 

A typical CPU instruction-execution cycle

1. The CPU fetches an instruction from memory (CPU는 메모리로부터 명령을 가지고 온다)
2. The instruction is then decoded and may cause operands (data) to be fectched from memory (명령은 해독되고, 이는 메모리로부터 피연산자인 데이터를 가지고 오도록 한다.)
3. The result may be stored back in memory (그 결과는 다시 메모리로 저장된다.)

 

 

각 process는 논리적 (가상의) 주소를 실제 메모리 주소 대신 사용한다.

Logical address (= Virtual address)

• Each user process has individual virtual address (An address generated by CPU)
• Always starts from address 0
• Logical Address space (Stack, heap 등을 저장하는 공간)
  • Set of all logical addresses generated by process
• When a process accesses a virtual address, the virtual address must be translated into a physical address (=Address binding)

Logical address는 모든 process가 각각 가지고 있는 주소이며, 항상 0부터 주소값이 시작되고, 실제 물리적 주소가 아니기 때문에 실제로는 0번째부터 시작하지 않는다.

process가 논리적 주소에 접근할 때, 논리적 주소는 실제 물리적 주소로 변환되어야 하는데, 이때 이 과정을 Address binding이라고 한다. 

 

Physical address

• Address seen by physical memory unit
• Physical Address space
  • Set of all physical address

 

 

• A pair of relocation (= base) register and limit register define the logical address space of each process
• Each process has separate memory space
  • User process only sees logical address , not physical address
  • User process cannot access other process's memory space = provide protection

 

---

Address Binding

1. Compile time binding  - Compiler : If memory location known at compile time, absolute code can be generated  - If starting physical adress changes must recompile code  소스코드가 binary 코드로 변환될 때 주소값을 할당해주는 방식  이러한 방식을 사용하면, 실제 시작 주소 (물리적 주소)는 다시 컴파일 해줘야한다 

2. Load time binding

  - Loader  : If memory location is not known at compile time, compiler must generate relocatable code

  - Address binding is delayed until load time

  - If starting address changes, need to reload user code

    loader가 loading하는 과정에서 binding이 이루어며, 이때의 주소는 relocatable code로 이루어져있는데, 이는 나중에 메모리 주소        가 바뀔 수 있다는 특징을 갖고 있다. 그리고 이또한 시작하는 주소가 바뀌면 다시 load 해줘야 한다. 뿐만 아니라, load 해줄 때까지            address binding이 지연된다.

 

3. Run time binding

  - process memory location can be moved during execution

  - Adress binding delayed until run time

  - Need hardware support for address maps (ex MMU such as base and limit registers)

  - Most OS's uses this method

   이는 CPU가 실행될 때 binding을 시켜주는 것인데, 빠른 속도로 binding을 해줘야하기 때문에 반드시 MMU와 같은 하드웨어의 지원       이 필요하다. 이 방법 또한 실행될 때까지 address binding이 지연된다는 특징을 갖고 있다. 주소를 참조할 때마다 binding을 점검해줘     야한다.

MMU 의 하드웨어 지원을 통해 binding해준다.

 

MMU (Memory Management Unit)

: Hardware supported unit that maps from logical (virtual) address to physical address in Run-time binding

 

만약 이때 relocation address가 1800으로 바뀐다면, 오직 relocation register의 값만 1800으로 바꿔주면 된다.

 

 

Memory Protection : Relocation-register scheme

• A relocation register and a limit register define a logical address space
• Address protection with relocation and limit registers

• relocation register값을 더해주고, limit register를 넘으면 남의 영역을 침범한 것으로 간주 -> ERROR

 

 

 

 

 

---

Memory Allocation

: Allocate memory to OS and user processes in an efficient way possible

 

Main memory의 구조

• Resident operating system usually held in low memory with interrupt vector
• User processes held in high memory

 

1. Load time binding
2. Run time binding

Contiguous Memory Allocation

• Allocate available memory to processes
• Each process is contained in a single section of contiguous memory

각 process는 오직 하나의 연속된 메모리 공간을 할당

• When a process arrives, it is allocated memory from a hole large enough to accommodate it
• Process exiting frees its partition, adjacent free partitions combined
• Operating system maintains information about allocated partitions and free partitions (hole)

process가 실행되면 해당 process를 할당받을 수 있을 만큼의 크기의 메모리를 할당 받는다. 이후, 프로세스가 종료되면, 해당 process 만큼의 메모리 크기가 free 되고, 인접한 free partitions 즉, hole들과 결합하게 된다. 

Hole: block of available memory, holes of various size are scattered throughout memory

 

 

Pros

• Cheap in terms of hardware : only two registers
• Cheap in terms of cycles : do add and compare in parallel

= 오직 두 register (limit register, relocation register) 사용 -> 속도 빠르고, 비용이 적음

= 더하고 비교하기만 하면 됨 -> cycle이 적음

 

Cons

• Growing a process is expensive or impossible
• No way to share code or data (ex.. two processes both running pintos)
• External Fragmentation problem
  • Total memory space exists to satisfy a request, but it is not contiguous

= process가 커지면 더 비싸지거나, 불가능해지고, code나 data를 공유할 수 없음

= 수용가능한 빈 공간이 불연속적이기 때문에 빈 공간들을 합치면 들어갈 수 있는 크기이지만, 그럼에도 합칠 수 없기 때문에 process를       할당할 수 없는 문제인 External Fragmentation이 발생 

 

Solution for External Fragmentation

1.  Compaction -> execution time binding일 때만 가능
   • 모든 free한 memory 공간을 합쳐 process를 합친 free memory 공간에 넣어 할당 받도록 하는 방법
   • relocation이 동적으로 진행되고, execution time에서 이를 마쳤을 때, 즉 execution time binding일 때만 가능
     • load time이나 compile time 때 binding이 되었다면 메모리 공간을 선점할 수 없으므로 불가능
2. Noncontiguous allocation
   
   • process들의 logical address space가 가능한 모든 곳 (hole)에 나눠서 process를 할당받을 수 있도록 하는 방법
     • ex) Paging

 

 

 

 

 

---

Paging

• process의 physical address space가 noncontiguous라면
  • external fragmentation을 피할 수 있음
  • 다양한 사이즈의 memory chunk 문제를 피할 수 있음
• Frame : physical memory를 고정된 블록 단위로 분리한 공간
  
  • page가 할당되는 공간
• Page : logical memory를 같은 크기인 블록단위로 분리한 공간
  • process가 분리되는 단위
• size of one frame = size of one page (일반적으로 4KB)
• N page 크기 만큼의 프로그램을 실행하기 위해서 N 만큼의 free frame을 찾은 뒤 program을 load 해야한다.
• logical address를 physical address로 번역해주기 위해 page table (MMU와 같은 역할) 을 설정해야함

• 실제 physical memory space는 불연속적이지만, process에게 보이는 logical memory는 연속적인 memory공간으로 보인다. 따라서, 메모리 사용이 간편해진다는 장점이 있다.
• process가 실행되면, page들은 가능한 memory frame들로 load된다.  

 

• page table : binding 해주는 데 필요한 정보들을 contain. MMU와 같은 역할
• page number (p) : page table에서의 index
• page offset (d) : physical memory address에서 몇번째 page를 나타내는지

 

 

 

 

 

 

Free-frame management

n개의 page를 필요로하는 process를 실행하려면 최소 n개의 free frame이 필요하다

free-frame list 이용 -> free frame이 몇번째 frame인지 찾아줌 (OS가 제공해줌)

 

 

Paging을 사용하는 이유

1) Provide Transparency 

• Programmer는 물리적 주소는 보이지 않고, 오직 logical address만 보인다.
• Binding 하는 과정은 programmer에게 가려지고, OS가 알아서 control 한다.

2) No external fragmentation

• 불연속적인 메모리 할당 - 어떠한 free frame도 process가 필요한 만큼 할당 받을 수 있다.
• internal fragmentation 발생
  
  • Memory는 정해진 크기의 page 만큼 할당 받으므로 할당 받는 page의 크기와 요청받는 memory의 크기의 차이만큼 낭비되기 때문에 page size를 작게 설정할수록 문제는 줄어든다.

3) Provide Protection to memory / Shared memory

• Programmer은 PTLR 에 정의되어있는 마지막 page 를 넘으면 trap이 일어난다.
• Use shared pages

 

Implementation of Page Table

1. Keep in registers and make it fast
   • page table을 register 안에 구현 : binding이 매우 빠르게 진행, but expensive - 넘 비싸서 register안에 넣어둘 수 없음
   • But page table은 클 수도 있음 !!
2. Keep in memory with register help
   • page table을 main memory 안에 구현
   • CPU register을  page table의 크기와 위치를 저장하기 위해 사용한다 - hardware support (MMU)
     • Page-table base register (PTBR) : points to the page table for its process
     • Page-table length register (PTLR) : size of the page table (for the process)

 

Problem of Page Table in Main Memory 

• Every data/instruction memory access 는 실제로 메모리에 두번 접근해야한다
  1. page table - to look for physical frame number of page
  2. data/instruction - read frame number
• To solve the problem of page table in main memory using TLB / associative memory 
  • TLB is like a cache to the page table
  • Store recently referenced page table entries in the TLB

 

 

TLB

• small, dedicated, super-fast hardware cache in MMU
  • High speed memory technology, approaching register speeds
    • Parallel search
  • TLB는 page number과 일치하는 page-table 항목을 포함한다
• Using TLB entries are much faster to resolve
  • high speed, but Expensive hardware

TLB hit : TLB에 메모리 존재

TLB miss : TLB 안에 메모리 존재하지 않음

• page number/frame number 를 다음 페이지를 참조하기 위해 TLB에 저장해둔다
• 이 경우 main memory에 가서 data를 가지고 와야한다.

 

Hit ratio : percentage of times that a page number is found in TLB / TLB에 data가 있을 확률

Effective Access Time

• Hit ratio 가 높을수록 EAT time 은 줄어든다.

 

Memory access order

1. View logical (virtual) address
2. Check TLB
   • TLB hit : get address from TLB
   • TLB miss : check page table in memory
3. Acquire physical address
4. Check Cache
   • cache hit : get data from cache
   • cache miss : get data from main memoru
5. Acquire data

 

 

 

 

 

---

Structure of the Page Table

1. Hierarchical paging
   
   • contiguous physical memory space per each page table -> 하나의 큰 page table 생성된다는 문제를 해결하기 위해  사용
   • page table을 여러 page. table로 나눠서 저장
   • Multi-level paging in which the page table is also paged
   • ex) Two - Level Paging 
     • a 10-bit outer-page number, a 10-bit inner-page number, a 12-bit page offset
2. Hashed Page Table
   • 32 bit보다 큰 주소 공간일 때 흔하게 사용
   • Hash function을 적용한 값을 바탕으로 hash table의 entry를 참조한다
   • 이때 hash table에는 virtual page number, value of the mapped page frame, pointer to the next element이 존재
   • hash function 적용한 entry값이 동일하면 충돌이 일어나기 때문에 linked list로 나타낸다.
3. Inverted Page Table
   • 모든 process가 오직 하나의 page table을 참조하고 있어야 한다.
   • page table의 entry 개수 = physical address (frame) 의 수와 동일하며 고정되어 있음
   • 0 번째 entry부터 순차적으로 pid 와 page number을 탐색하며 일치하는 page table entry 를 찾으면 해당 index가 page frame number이 된다.
   • (장점) page를 고정 크기로 관리하며 memory size를 줄일 수 있다
   • (단점) 검색하는 데 걸리는 시간이 증가하고 - hash table로 해결 가능, share memory 구현이 어렵다

 

 

 

 

지금까지 Memory에 대해서, Paging에 대해서 좀 더 깊게 알아보았다.