Chapter 3

Question 1

Before a job is loaded into memory, it is divided into parts called _____ that will be loaded into memory locations called _____________

Answer 1

pages, page frames.

Question 2

_____________ is based on the concept of dividing each incoming job into pages of equal size.

Answer 2

Paged memory allocation

Question 3

The sections of a disk are called ______ (or sometimes blocks), and the sections of main memory are called __________.

Answer 3

sectors, page frames

Question 4

Before executing a program, the Memory Manager prepares it by:

Answer 4

1. Determining the number of pages in the program
2. Locating enough empty page frames in main memory
3. Loading all of the program’s pages into them

Question 5

Primary advantage of storing programs in noncontiguous location (paged memory allocation):

Answer 5

The main memory is used more efficiently because an empty page frame can be used by any page of any job.

In addition, the compaction scheme used for relocatable partitions is eliminated because there is no external fragmentation between page frames (and no internal fragmentation in most pages).

Question 6

Disadvantage of storing programs in noncontiguous location (paged memory allocation):

Answer 6

A job’s pages can be located anywhere in main memory, the Memory Manager now needs a mechanism to keep track of them—and that means enlarging the size and complexity of the operating system software, which increases overhead.

Question 7

What tables does the Memory Manager use to keep track of jobs, pages, and memory locations in paged memory allocation?

Answer 7

• Job Table
• Page Map Table
• Memory Map Table

Question 8

Job Table contains two values for each active job:

Answer 8

• size of the job
• the memory allocation where its page map table is stored

Question 9

What is displacement or offset?

Answer 9

The factor used to locate that byte within its page frame. It is a relative factor

Question 10

Contains two values for each active job: the size of the job (shown on the left) and the memory location where its Page Map Table is stored (on the right)

Answer 10

Job Table

Question 11

Contains the vital information for each page—the page number and its corresponding page frame memory address.

Answer 11

Page Map Table

Question 12

Has one entry for each page frame listing its location and free/busy status.

Answer 12

Memory Map Table

Question 13

Formula for finding the address of a given program instruction:

Answer 13

The byte number is divided by the page size, keeping the remainder as an integer. The resulting quotient is the page number, and the remainder is the displacement within that page

Question 14

Formula for finding the exact location in memory:

Answer 14

ADDR_PAGE_FRAME = PAGE_FRAME_NUM * PAGE_SIZE

INSTR_ADDR_IN_MEM = ADDR_PAGE_FRAME + DISPL

Question 15

Every time an instruction is executed, or a data value is used, the operating system (or the hardware) must translate the job space address, which is relative, into its physical address, which is absolute.

This is called resolving the address, also called:

Answer 15

address resolution

Question 16

Advantages and disadvantages of paging scheme:

Answer 16

Advantages:
- it allows jobs to be allocated in noncontiguous memory locations so that memory is used more efficiently
- more jobs can fit in the main memory

Disadvantages:
- overhead is increased
- internal fragmentation is still a problem

Question 17

The concept of loading only a part of the program into memory for processing

Answer 17

Demand paging

Question 18

It was the first widely used scheme that removed the restriction of having the entire job in memory from the beginning to the end of its processing

Answer 18

Demand paging

Question 19

One of the most important innovations of demand paging was that it made ____________ feasible

Answer 19

virtual memory

Question 20

The key to the successful implementation of demand paging is the use of a ____________________________

Answer 20

high-speed direct access storage device (such as hard drives or flash memory) that can work directly with the CPU

Question 21

It determines whether there are empty page frames in memory so the requested page can be immediately copied from secondary storage.

If all page frames are busy, the ____________ must decide which page will be swapped out. Then the swap is made

Answer 21

page fault handler

Question 22

When there is an excessive amount of page swapping between main memory and secondary storage, the operation becomes inefficient. This phenomenon
is called ________

Answer 22

thrashing

Question 23

A failure to find a page in memory is often called a __________

Answer 23

page fault

Question 24

the policy that selects the page to be removed

Answer 24

page replacement policy

Question 25

two page replacement policy

Answer 25

- first-in first-out (FIFO) policy - least recently used (LRU) policy

Question 26

based on the theory that the best page to remove is the one that has been in memory the longest

Answer 26

first-in first-out (FIFO) policy

Question 27

chooses the page least recently accessed to be swapped out

Answer 27

least recently used (LRU) policy

Question 28

an unusual circumstance through which adding more page frames causes an increase in page interrupts when using a FIFO page replacement policy

Answer 28

FIFO anomaly

Question 29

A variation of the LRU page replacement algorithm

Answer 29

clock page replacement policy

Question 30

the clock page replacement policy is paced according to the:

Answer 30

computer’s clock cycle

Question 31

A second variation of LRU uses an ________________________ to track the usage of each page currently in memory

Answer 31

8-bit reference byte and a bit-shifting technique

Question 32

Page Map Table for demand paging included three bits:

Answer 32

- status bit - referenced bit - modified bit

Question 33

the set of pages residing in memory that can be accessed directly without incurring a page fault

Answer 33

working set

Question 34

meaning that during any phase of its execution the program references only a small fraction of its pages

Answer 34

locality of reference

Question 35

each job is divided into several segments of different sizes, one for each module that contains pieces that perform related functions

Answer 35

segmented memory allocation

Question 36

segment map table contains:

Answer 36

- segment numbers - their lengths - access rights - status - its location in memory

Question 37

The Memory Manager needs to keep track of the segments in memory. This is done with three tables combining aspects of both dynamic partitions and demand paging memory management:

Answer 37

* The Job Table lists every job being processed (one for the whole system). * The Segment Map Table lists details about each segment (one for each job). * The Memory Map Table monitors the allocation of main memory (one for the whole system).

Question 38

The Segment Map Table functions the same way as a Page Map Table but manages _________ instead of pages.

Answer 38

segments

Question 39

It is a combination of segmentation and demand paging, and it offers the logical benefits of segmentation, as well as the physical benefits of paging.

Answer 39

segmented/demand paged memory allocation

Question 40

segmented/demand paged memory allocation requires four tables:

Answer 40

* The Job Table lists every job in process (one for the whole system). * The Segment Map Table lists details about each segment (one for each job). * The Page Map Table lists details about every page (one for each segment). * The Memory Map Table monitors the allocation of the page frames in main memory (one for the whole system)

Question 41

major disadvantages of segmented/demand paged memory allocation

Answer 41

the overhead required for the extra tables and the time required to reference the segment table and the page table

Question 42

a name given to several registers that are allocated to each job that is active

Answer 42

Associative memory

Question 43

programmers started dividing their programs into sections that resembled working sets, really segments, originally called roll in/roll out and now called ________

Answer 43

overlays

Question 44

based on the idea that the system can use a small amount of expensive high speed memory to make a large amount of slower, less-expensive memory work faster than main memory.

Answer 44

Caching

Question 45

intermediate memory unit

Answer 45

cache memory

Question 46

A typical microprocessor has two levels of caches:

Answer 46

Level 1 (L1) and Level 2 (L2)

Question 47

When designing cache memory, one must take into consideration the following four factors:

Answer 47

- cache size - block size - block replacement algorithm - rewrite policy

Question 48

used to determine the performance of cache memory and represents the percentage of total memory requests that are found in the cache

Answer 48

hit ratio (h)

Question 49

hit ratio formula:

Answer 49

HitRatio = (number of requests found in the cache / total number of requests) * 100

Question 50

Another way to measure the efficiency of a system with cache memory, assuming that the system always checks the cache first, is to compute the:

Answer 50

average memory access time

Question 51

Difference of paging and segmentation

Answer 51

pages are physical units that are invisible to the user’s program and consist of fixed sizes; segments are logical units that are visible to the user’s program and consist of variable sizes.

Question 52

Segmented/Demand Paged Memory Allocation Three-dimensional addressing scheme:

Answer 52

SEGMENT_NUMBER & PAGE_NUMBER & DISPLACEMENT

Question 53

Segmented Memory Allocation two-dimensional addressing scheme:

Answer 53

SEGMENT_NUMBER & DISPLACEMENT

Question 54

demand paging tables are basically the same as for paged memory allocation but with the addition of three new fields for each page in the PMT:

Answer 54

- to determine if the page being requested is already in memory (status bit) - to determine if the page contents have been modified (modified bit) - to determine if the page has been referenced recently (referenced bit)

Question 55

Advantage and disadvantage of demand paging:

Answer 55

Advantage: - job is no longer constrained by the size of physical memory and it introduced the concept of virtual memory - utilized memory more efficiently because the sections of a job that were used seldom or not at all weren’t loaded into memory unless they were specifically requested Disadvantage: - increased overhead caused by the tables and the page interrupts

Question 56

To access a location in memory, when using either paged or segmented memory management, the address is composed of two values:

Answer 56

- The page or segment number - Displacement

Question 57

The use of virtual memory requires cooperation between the:

Answer 57

memory manager and the processor hardware

Question 58

Describe how the function of the Page Map Table differs in paged vs. segmented/demand paging memory allocation.

Answer 58

In paged memory allocation, the Page Map Table (PMT) is always present in memory and directly maps each logical page of a job to its corresponding page frame in main memory. Every memory reference uses the PMT for address translation. In segmented/demand paging, the PMT is tied to individual segments and is loaded into memory only when pages from that segment are needed. The Segment Map Table (SMT) is first used to locate the segment’s PMT, and then the PMT maps the requested page to its frame. Or The PMT in paged memory allocation correlates each of the job’s pages with its page frame number. The PMT in segmented/demand paged memory allocation is similar to paged memory allocation, but also includes the status (whether in memory or not), modified (whether been modified or not), and reference bits (whether been recently referenced)

Question 59

Describe how the OS detects thrashing. Once thrashing is detected, explain what the OS can do to stop it

Answer 59

It detects thrashing when the operation becomes inefficient, by an excessive amount of page swapping between main memory and secondary storage. To stop it, the page replacement policy comes into play. FIFO and LRU

Question 60

Compare and contrast internal fragmentation and external fragmentation. Explain the circumstances where one might be preferred over the other.

Answer 60

Internal fragmentation occurs within allocated memory blocks and is common in fixed-sized allocation systems, while external fragmentation occurs between allocated memory blocks and is common in variable-sized allocation systems. Internal fragmentation is preferred in predictable environments, while external fragmentation is preferred in environments with unpredictable memory usage patterns.

Question 61

One innovation that improved the performance of demand paging schemes was the concept of the _________

Answer 61

working set