Chapter 9: Main Memory

Question 1

What is the only general-purpose storage device that the CPU can access directly?

Answer 1

Main memory is the only general-purpose storage device that the CPU can access directly.

Question 2

Where are programs usually stored before being loaded into memory?

Answer 2

Programs are usually stored on hard drives.

Question 3

Why must programs be loaded into memory to be executed?

Answer 3

The CPU cannot access hard drives directly, so programs need to be loaded into memory to be executed.

Question 4

What memory must be protected from access by user processes for correct execution?

Answer 4

The memory allocated to the operating system should not be accessed by user processes.

Question 5

What principle must be upheld regarding the memory spaces of different user processes?

Answer 5

The memory allocated to one user process should not be accessed by another user process.

Question 6

What is one possible solution to prevent processes from accessing each other’s memory?

Answer 6

One possible solution is to ensure that each process has a separate memory space.

Question 7

What two hardware registers can be used to separate the memory space of processes?

Answer 7

We can provide this protection using two registers, usually a base register and a limit register.

Question 8

What value does the ‘base register’ hold in memory management?

Answer 8

The base register holds the smallest legal physical memory address for a process.

Question 9

What does the ‘limit register’ specify in memory management?

Answer 9

The limit register specifies the size of the legal memory range for a process.

Question 10

In the example where the base register is 300040 and the limit register is 120900, what is the range of legally accessible addresses?

Answer 10

The process can legally access all addresses from 300040 through 420939 (inclusive).

Question 11

What entity is exclusively permitted to modify the contents of the base and limit registers?

Answer 11

Only the OS can modify the content of these two registers in kernel mode.

Question 12

How is memory space protection accomplished using base and limit registers?

Answer 12

The CPU hardware compares every address generated in user mode with the values in these registers.

Question 13

What happens when a process in user mode attempts to access operating-system memory or another user’s memory?

Answer 13

The attempt results in a trap to the operating system, which treats it as an error.

Question 14

What is a ‘logical address’ also known as?

Answer 14

A logical address is also known as a virtual address.

Question 15

What is the term for the memory space corresponding to logical addresses?

Answer 15

The corresponding memory space is called logical memory space (or virtual memory space).

Question 16

What kind of addresses does a user program exclusively use?

Answer 16

A user program only uses logical addresses.

Question 17

What is the term for the real address for each storage unit in main memory?

Answer 17

A physical address is the real address for each storage unit in main memory.

Question 18

Before data in main memory can be accessed, what must happen to logical addresses?

Answer 18

The logical addresses must be mapped to physical addresses.

Question 19

What type of register, equivalent to a base register, is used to map logical to physical addresses?

Answer 19

A relocation register is used to accomplish the mapping from logical to physical addresses.

Question 20

How is a logical address mapped to a physical address using a relocation register?

Answer 20

The value in the relocation register is added to every logical address used by a user process.

Question 21

If the relocation register has a value of 14000, to what physical address is the logical address 346 mapped?

Answer 21

The logical address 346 is mapped to the physical address 14346.

Question 22

What two entities must the main memory accommodate simultaneously?

Answer 22

The main memory must accommodate both the operating system and various user processes.

Question 23

In contiguous memory allocation, memory is usually divided into how many partitions?

Answer 23

The memory is usually divided into two partitions: one for the operating system and one for user processes.

Question 24

Where do many operating systems, like Linux and Windows, place the OS in memory?

Answer 24

Many operating systems place the operating system in the high memory address section.

Question 25

In contiguous memory allocation, where is each process contained?

Answer 25

Each process is contained in a single section of memory, typically next to the section containing the next process.

Question 26

In the variable-section scheme of contiguous memory allocation, how many processes can each section contain?

Answer 26

Each section may contain exactly one process.

Question 27

What data structure does the OS maintain in a variable-section contiguous allocation scheme?

Answer 27

The operating system keeps a table indicating which parts of memory are available and which are occupied.

Question 28

In contiguous allocation, a large block of available memory is considered a ____.

Answer 28

hole

Question 29

What is the result of processes arriving and leaving in contiguous memory allocation?

Answer 29

Eventually, memory contains a set of holes of various sizes.

Question 30

In the contiguous allocation example, after process 8 leaves, what is created in memory?

Answer 30

After process 8 leaves, there is one contiguous hole.

Question 31

In the contiguous allocation example, after process 5 departs, what is the state of the free memory?

Answer 31

After process 5 departs, there are two noncontiguous holes.

Question 32

What problem is concerned with satisfying a memory request of size n from a list of free holes?

Answer 32

The Dynamic Storage Allocation problem.

Question 33

Define the 'First fit' dynamic storage allocation method.

Answer 33

First fit allocates the first hole that is big enough.

Question 34

Define the 'Best fit' dynamic storage allocation method.

Answer 34

Best fit allocates the smallest hole that is big enough.

Question 35

Define the 'Worst fit' dynamic storage allocation method.

Answer 35

Worst fit allocates the largest hole.

Question 36

According to simulations, how do first fit and best fit compare to worst fit in memory utilization?

Answer 36

Both first fit and best fit are better than worst fit in terms of memory utilization.

Question 37

Which is generally faster: first fit or best fit?

Answer 37

First fit is generally faster.

Question 38

For exponential and hyperexponential distributions of memory requests, which strategy outperforms the other?

Answer 38

First-fit outperforms best-fit.

Question 39

For normal and uniform distributions of memory requests, which strategy outperforms the other?

Answer 39

Best-fit outperforms first-fit.

Question 40

Both first-fit and best-fit strategies for memory allocation suffer from what problem?

Answer 40

They both suffer from external fragmentation.

Question 41

What is 'external fragmentation'?

Answer 41

It exists when there is enough total memory space to satisfy a request, but the available spaces are not contiguous.

Question 42

According to statistical analysis of first fit, what fraction of memory may be unusable due to fragmentation?

Answer 42

1/3 of memory may be unusable due to fragmentation.

Question 43

When does 'internal fragmentation' occur?

Answer 43

It occurs when allocated memory is slightly larger than the requested memory, leaving unused space internal to a section.

Question 44

In the example of a 18,464 byte hole and a 18,462 byte request, what is the size of the resulting hole?

Answer 44

The resulting hole would be 2 bytes.

Question 45

What is the general approach to solving the problem of tiny, unusable holes from contiguous allocation?

Answer 45

Break physical memory into fixed-sized blocks and allocate one or more blocks to each process.

Question 46

The memory management scheme called _____ permits a process's physical address space to be noncontiguous.

Answer 46

paging

Question 47

What problem does the paging memory-management scheme avoid?

Answer 47

Paging avoids the external fragmentation problem.

Question 48

The basic method for paging involves breaking physical memory into fixed-sized blocks called _____.

Answer 48

frames

Question 49

The basic method for paging involves breaking logical memory into blocks of the same size called _____.

Answer 49

pages

Question 50

When a process is to be executed using paging, where are its pages loaded?

Answer 50

Its pages are loaded into available memory frames.

Question 51

In paging, every logical address is divided into what two parts?

Answer 51

A page number (p) and a page offset (d).

Question 52

In address translation via paging, what is the page number used for?

Answer 52

The page number is used as an index into the page table.

Question 53

After using the page number to index the page table, what corresponding information is extracted?

Answer 53

The corresponding frame number (f) is extracted from the page table.

Question 54

To form a physical address in paging, the page number (p) in the logical address is replaced by what?

Answer 54

The page number (p) is replaced with the frame number (f).

Question 55

What determines the page size in a paging scheme?

Answer 55

The page size is defined by the hardware and is usually determined by the processor architecture.

Question 56

The size of a page is typically a power of what number?

Answer 56

The size of a page is a power of 2.

Question 57

If logical address space size is $2^m$ bytes and page size is $2^n$ bytes, how many bits represent the page number?

Answer 57

The high-order $(m-n)$ bits of a logical address correspond to the page number.

Question 58

If logical address space size is $2^m$ bytes and page size is $2^n$ bytes, how many bits represent the page offset?

Answer 58

The n low-order bits of the logical address designate the page offset.

Question 59

In the example given, the logical address $7_{10}$ is what in binary?

Answer 59

The logical address $7_{10}$ is $0111_2$.

Question 60

For the logical address $0111_2$ with $m=4$ and $n=2$, what is the page number and page offset in binary?

Answer 60

The Page Number is $01_2$ and the Page Offset is $11_2$.

Question 61

Following the example, if page number $01_2$ maps to frame number $110_2$, what is the final physical address for logical address $7_{10}$?

Answer 61

The final physical address is $11011_2 = 27_{10}$.

Question 62

Using the example page table, what physical address corresponds to the logical address $4_{10}$?

Answer 62

The logical address $4_{10}$ ($0100_2$) corresponds to the physical address $24_{10}$ ($11000_2$).

Question 63

Using the example page table, what physical address corresponds to the logical address $13_{10}$?

Answer 63

The logical address $13_{10}$ ($1101_2$) corresponds to the physical address $9_{10}$ ($01001_2$).

Question 64

What kind of fragmentation is eliminated when using a paging scheme?

Answer 64

When we use a paging scheme, we have no external fragmentation.

Question 65

Although paging eliminates external fragmentation, what type of fragmentation can still occur?

Answer 65

We may have some internal fragmentation.

Question 66

Why does internal fragmentation occur with paging?

Answer 66

If the memory requirement of a process does not coincide with page boundaries, the last allocated frame is not completely full.

Question 67

In the worst case of internal fragmentation, a process needing n pages plus 1 byte results in a waste of almost how much memory?

Answer 67

It results in a waste of almost an entire frame.

Question 68

If process size is independent of page size, what is the expected average internal fragmentation waste per process?

Answer 68

We expect internal fragmentation to lead to a half-page per process waste on average.

Question 69

What characteristic of page size is desirable to minimize internal fragmentation?

Answer 69

Small page size is desirable.

Question 70

What is the trade-off of using smaller page sizes?

Answer 70

Overhead is involved in each page-table entry, and this overhead is reduced as the page size increases.

Question 71

What are typical page sizes in modern computer systems?

Answer 71

Today, a page is typically either 4 KB or 8 KB in size.

Question 72

When a new process requiring n pages arrives, what is the minimum number of frames that must be available?

Answer 72

If the process requires n pages, at least n frames must be available in memory.

Question 73

What system-wide data structure does the OS use to keep track of physical memory allocation?

Answer 73

The allocation information is generally kept in a single, system-wide data structure called a frame table.

Question 74

What information does an entry in the frame table contain?

Answer 74

It has one entry for each physical frame, indicating if it's free or allocated, and if allocated, to which page of which process.

Question 75

What problem arises with page tables in modern systems that support a large logical address space (e.g., $2^{32}$ to $2^{64}$)?

Answer 75

The page table itself becomes very large.

Question 76

For a system with a 32-bit logical address space and a 4 KB page size, how many entries might a page table have?

Answer 76

A page table may consist of over 1 million entries ($2^{20}$).

Question 77

Assuming 4 bytes per entry, how much physical memory might a single page table require in a 32-bit system?

Answer 77

Each process may need up to 4 MB of physical address space for the page table alone.

Question 78

Why is it undesirable to allocate a large page table contiguously in main memory?

Answer 78

Page tables may come and go, resulting in fragmentation.

Question 79

What is a simple solution to the problem of large, contiguous page tables?

Answer 79

A simple solution is to divide the page table into smaller pieces.

Question 80

What is one way to divide a page table into smaller pieces?

Answer 80

One way is to use a two-level paging algorithm.

Question 81

In a two-level paging algorithm, what is done to the page table itself?

Answer 81

The page table itself is also paged.