Memory management - 1

Question 1

• What is the Hard-Disk for?*
• Synonym: secondary storage*

Answer 1

It is used to store a large amount of data, which are not currently in use.

Question 2

• What is the RAM(random access memory)?*
• Synonyms: physical memory, main memory, primary storage, or just, memory.*

Answer 2

Main memory holds the programs and data loaded into the computer from even slower storage, like disk or network, in order for it to be prepared for CPU usage.(relatively close to the CPU)

Question 3

What is a cache for?

Answer 3

Cache is a temporary storage which resides within the processor chip(nearer to CPU than RAM), thus smaller and faster.

Question 4

What is a register for?

Answer 4

Nearest to the CPU, smallest memory units - used for computations of the CPU and help follow the instructions pipeline

Question 5

What is a virtual memory, and what is it for?

Answer 5

1. It is a simulated memory that is written to a file on the hard-drive.

that file is also called: page-file or swap file

2. It is used by the OS to simulate physical RAM by using hard disk space. It allows us to run more applications on the system.

Question 6

What is a volatile memory?

Answer 6

volatile means that it can be changed rapidly. That is, it can easily lose the data. For instance, RAM is considered volatile because once power is cut-off, data is lost.

Question 7

who’s responsible for transferring memory from the secondary storage(disk) to the main storage(RAM)?

Answer 7

The memory manager

Question 8

n proceses, each spending a fraction p of their time waiting for I/O(for instance , p = 0.7 means the process spends 70% of its time waiting for I/O). what is the probabilty of all processes waiting for I/O simultaneously?

Answer 8

p^n

Question 9

Assume each process takes 200k(of the RAM) and so does the OS.

Assume there is 1MB in the RAM, and that p=0.

1. What would be the CPU utilization for the max number of processes we can run simultaneously?
2. What if we add another 1MB?

Answer 9

Including the OS, we can add 4 more processes. (200*5 =1000)

1. The probability of all 4 processes waiting simultaneously for I/O, which is the worst case scenario of CPU utilization, is 0.8^4 = 0.4096. that also means that in the worst case, the CPU utilization stand on about 60%(because 40% is taken by I/O)
2. If we add another 1MB, we have space for additional 5 processes. that means worst case scenario 0.8^9≈0.13% of the time the CPU has no work to do. CPU utilization is thus around 0.87%.

Question 10

What is an External fragmentation?

What is an Internal fragmentation?

Answer 10

External: When a process cannot allocate required memory space because memory is non-contiguous.

It occurs due to dynamic partitioning.

This can be cured using: compaction, segmentation and paging

Internal: When the RAM is divided into fixed-sized partitions, each for a loaded process, and we meet the case in which we don’t have space for process to be loaded even though the other processes in RAM don’t use all the fixed-sized memory they’ve been given.

Question 11

What is compaction?

Answer 11

Eliminating unnecessary redundancy in order to reduce the amount of data stored without loss of information. In addition, it shuffles memory contents to place all free memory together in one large block.

It is only possible if reallocation is dynamic.

This process helps to cure fragmentation.

Question 12

What is segmentation?

Answer 12

• Dividing the memory into segments:*
• 1. The code.*
• 2. Uninitialized - bss*
• 2. The global variables*
• 3. The heap*
• 4. the stack*
• 5. the standard C library.*
• This memory management scheme helps to estimate the amount of memory needed for any part mentioned above. This is another tool to cure fragmentation.*
• In addition, the segments don’t interfere one with the other due to the help of the segmentation table, which using the base address and the limit of each segment, knows to tell if an address, which is given by: {segment number, offset} can be addressed or it exceeds the limit of the segment. If the latter, it may result with a segmentation fault.*

Question 13

What is paging?

Answer 13

Paging allows the physical address space of a process to be noncontiguous. (fixing external fragmentation).

Paging** is implemented by breaking the **main memory** into fix-sized blocks that are called **frames.

• The virtual memory of a process is broken into the same fixed-sized blocks called pages.*
• When a program is to be executed, the pages of the program are loaded from disk into any available frames in main memory.*
• The CPU generates the virtual address space of the process. Each virtual address consists of two parts: {page number;page offset}.*
• Each process has its own page table, which contains the base address of each page that was loaded in main memory. Combined with the page offset it generates the address of the required data in memory.*

Question 14

What is daemon?

Answer 14

A daemon is a process(program) that runs in the background on a multi-tasking OS.

That means, it is detached from a terminal and runs continuously in a non-interactive mode.

A way to create a deamon is by forking a child process and then exiting the parent.

Question 15

How Memory Allocation is tracked?

Answer 15

Using a map of bit - bitmap.

Using a linked list

Question 16

When is Swapping done?

(Ask yourself when is memory needed..)

Answer 16

• 1. Kernel runs out of memory - memory needed for the maintanance of the kernel operations.*
• 2. Fork system call - no space for child process.*
• 3. Expanding user virtual address using sbrk.*
• 4. Stack becomes to large.*
• 5. A swapped-out process becomes ready.*

Question 17

What is address binding?

Answer 17

• The process of mapping the program’s virtual addresses to corresponding physical address(RAM).*
• steps:*

CPU generates** the **virtual address** for an **instruction/data** to be fetched from **RAM.

The virtual address undergoes translation by the MMU.

Run-time binding - a binding is resolved only when a reference to a physical memory is made.

Question 18

What is Linking?

Answer 18

Compilation phase translate source code(.c files) into machine language instruction in the form of .o files.

Linker creates single executable file out of many .o files. It searches multiple files for the main() function definition and links them.

Question 19

Describe the differences: Static & Dynamic linking

Answer 19

static linking** **-

• All library modules are copied to the executable image.*
• Done by the linkers in the last compilation step.*
• time is fixed.*

Dynamic linking -

• Only the names of external/shared libraries is placed in RAM.*
• Actual linking with the library routines does not occur until the image is run, when both the executable and the library are placed in memory.*
• It is done by the OS at run-time.*
• time - vary*

Who’s better:

• Dynamic requires less disk space and memory*
• because several programs might share the same library
• Static is faster and more portable*
• Linking step is done once, thus faster

Question 20

What is the Buddy System?

Answer 20

• It is a memory allocation and management algorithm.*
• This algorithm manages memory in power of two increments.*
• If a memory M is asked and the total memory is S, it recursively divides the block of memory and checks whether S/2*<m> and get out of the loop.</m>
• Freed blocks can only be merged with neighbors of their own size. This is done recursively as in the image attached.*

Question 21

How the MMU works?

Answer 21

• when the MMU is given a virtual address of the form: {pde_num;pte_num;page_offset}.*
• The first is used to search within the page directory the desired page table.*
• Then, using the pte_num we find the relevant pte which holds the physical memory of the page(base address).*
• Combined with the page offset we reach to the exact address in physical memory.*

Question 22

What is a page fault? and what can the kernel do in such a case?

Answer 22

A fault that raises when the MMU tries to access a page which is not currently loaded in RAM.

This allows the kernel to handle swapping.

The kernel maintains copies of the pages on disk

Question 23

What does a PTE(Page Table Entry) contain?

Answer 23

base address of the page

Present bit - is it located on RAM

Dirty bit - has the page been modified.

Referenced bit- has the page been accessed.

Protection - read, write, etc..

Caching disable/enable - can we use cache for the page frame

Question 24

How much is: KB, MB, GB and TB

Answer 24

KB = 2^10 bytes

MB = 2^20 bytes

GB = 2^30 bytes

TB = 2^40 bytes

Question 25

How does multi-level page table save memory space?

Answer 25

• First, let’s makes some sense:*
• What is the size of a page? 4KB*
• How much virtual memory space is available for us? 4GB*
• Assume it is divided into: 1KB page tables with 1MB entries*
• What is the size of a page table entry? 4B*
• What is the size of a page-table? 1MB * 4B = 4MB*
• Does that make sense?*

1KB**(page tables)***4MB**(size of a page table) = **4GB

Now,** why is it called **Paging?

• The MMU uses the 20 upper bits as an index to the PTE. From the PTE it recieves the base address, which when combined with the 12 lower bits of the virtual address form the exact physical address. Now, if we have 12 bits that denotes an offset - how many address are there in this chunk of memory? 2^12. which is 4KB, which is the size of a page.*
• In other words, each PTE refers to the beginning of a chunk of memory in RAM which has a fixed-size - a page-frame size.*

one-level page table -** i need to find a pte. In order to do that, i need to hold the proccess’ page table. That is, to keep in memory 2^20*4 bytes **= 4MB .

two-level page table - Page directory holds 2^10 PTEs where each one refers to some page table with 2^10 PTEs(in total 2^20 PTEs).

• So, we need in total - 2^10*4 bytes + 2*10*4 bytes = 4KB+4KB = 8KB.*
• In total: 8KB vs 4MB. A big difference.*
• NOTE: we keep the page directory in memory and use cache to save the most recently used translations.*

Question 26

What is TLB(Translation Lookaside Buffer)?

What can be wastful about it?

Answer 26

A special cache used to keep track of recently used page table entries.

With multi-processing, TLB must be cleared on context switch - wasteful.

Question 27

What is Inverted page table?

Answer 27

It is a global page table which serves all processes.

This table is divided into entries {pid | p} , identified by index i.

i - the base address of a page frame in RAM. (the number of entries in the page tables = number of page frames in RAM)

pid - process id.

p - virtual page number

When the CPU generates a virtual address, it has the form:

{pid | p | offset}. using hash table we can find the index in which {pid | p} resides in the page table, and combined with the offset we get the physical address.

How much space do we save this way?

4GB(RAM)/4KB(PAGE SIZE) = 2^32/2^12 = 2^20.

Each entry in the page table, {pid|p}, is one byte.

We need to save 2^20*4 = 4MB for the entire system.

That is of course an advantage, disadvantages are its look up time and the difficulty to implement a shared memory implementation.