C191-Terms-Chapter-7

Question 1

physical memory (RAM)

Answer 1

is a hardware structure consisting of a linear sequence of words that hold a program during execution.

Question 2

word

Answer 2

A word is a fixed-size unit of data. A typical word size is 1, 2, or 4 bytes.

Question 3

physical address

Answer 3

an integer in the range [0: n-1] that identifies a word in a physical memory of size n. The address comprises a fixed number of bits. A memory of size n requires an address size of k bits, where n = 2^k.

During program development, the starting address of a program in physical memory is unknown.

To facilitate program development and the sharing of physical memory, the concept of a logical address space is employed.

Question 4

logical address space

Answer 4

an abstraction of physical memory, consisting of a sequence of imaginary memory locations in a range [0: m-1], where m is the size of the logical address space.

Question 5

logical address

Answer 5

an integer in the range [0 : m-1] that identifies a word in a logical address space. Prior to execution, a logical address space is mapped to a portion of physical memory and the program is copied into the corresponding locations.

Question 6

source module

Answer 6

a program or a program component written in a symbolic language, like C, or an assembly language, that must be translated by a compiler or assembler into executable machine code.

Question 7

object module

Answer 7

the machine-language output of a compiler or assembler generated from a source module. An object module may be self-contained and executable or multiple object modules may be linked together into a load module by a linker or linkage editor.

Question 8

load module

Answer 8

a program or combination of programs in a form ready to be loaded into main memory and executed.

Question 9

Relocation and address binding

Answer 9

The physical addresses of the program components aren’t known until load time, the compiler/assembler and the linker assume logical address spaces starting with address 0.

During each step of the program transformation, the logical addresses of instructions and data may be changing. Only during the final step of program loading are all logical addresses bound to actual physical addresses in memory.

Question 10

relocation

Answer 10

Program relocation is the act of moving a program component from one address space to another. The relocation may be between two logical address spaces or from a logical address space to a physical address space.

Question 11

Static relocation

Answer 11

binds all logical addresses to physical addresses prior to execution.

Question 12

Dynamic relocation

Answer 12

postpones the binding of a logical address to a physical address until the addressed item is accessed during execution.

Question 13

relocation register

Answer 13

contains the physical starting address of a program or program component in memory.

Most programs consist of 3 main components: code, static data, and dynamic data. A simple memory management scheme treats the 3 components as one unit, which must be moved into one contiguous area of memory.

Question 14

Dynamic relocation

Answer 14

can be implemented using a single relocation register, which is loaded with the program’s starting address.

The register content is then added automatically by the CPU to every logical address of the program to generate the physical address.

A more flexible management scheme treats the 3 components as separate modules, each of which may reside in a different area of memory.

Three relocation registers, each loaded with the starting address of one of the modules, then accomplish dynamic relocation by being added to all logical addresses at runtime.

Question 15

Free space management

Answer 15

As programs are moved into and out of memory at runtime, the memory space becomes a checkerboard of free and occupied areas of different sizes.

The OS keeps track of all free spaces, referred to as holes, using a linked list and must find a hole of appropriate size whenever a new program component is to be loaded into memory.

The OS must also coalesce any neighboring holes resulting from the removal of programs from memory to prevent the memory from becoming a fragmented collection of increasingly smaller holes.

Different search strategies have been explored, they include first-fit, next-fit, best-fit, and worst-fit.

Question 16

First-fit

Answer 16

always starts the search from the beginning of the list and allocates the first hole large enough to accommodate the request.

Question 17

Next-fit

Answer 17

starts each search at the point of the last allocation.

Question 18

Best-fit

Answer 18

searches the entire list and chooses the smallest hole large enough to accommodate the request.

Question 19

Worst-fit

Answer 19

takes the opposite approach from best-fit by always choosing the largest available hole for any request.

Simulation of different strategies have not produced a clear winner. The choice depends on the average request size relative to the memory size, and the variance of request sizes.

Question 20

relocatable object file

Answer 20

The output of a compiler in which the contents can be loaded into any location in physical memory.

Question 21

linker

Answer 21

A system service that combines relocatable object files into a single binary executable file.

During the linking phase, other object files or libraries may be included as well, such as the standard C or math library (specified with the flag -lm).

Question 22

loader

Answer 22

is used to load the binary executable file into memory, where it is eligible to run on a CPU core.

A system service that loads a binary executable file into memory, where it is eligible to run on a CPU core.

Question 23

relocation

Answer 23

An activity associated with linking and loading is relocation, which assigns final addresses to the program parts and adjusts code and data in the program to match those addresses so that, for example, the code can call library functions and access its variables as it executes.

Question 24

executable file

Answer 24

A file containing a program that is ready to be loaded into memory and executed.

Question 25

dynamically linked libraries (DLLs)

Answer 25

System libraries that are linked to user programs when the processes are run, with linking postponed until execution time.

Question 26

executable and linkable format (ELF)

Answer 26

The UNIX standard format for relocatable and executable files.

Question 27

portable executable (PE)

Answer 27

The Windows format for executable files.

Question 28

Mach-O

Answer 28

The macOS format of executable files.

Question 29

External memory fragmentation

Answer 29

the loss of usable memory space due to holes between allocated blocks of variable sizes.

In a stable state, where on average every release of a block is followed by an allocation of a new block, the ratio between the number of holes and the number of occupied blocks is fixed and cannot be reduced by different allocation strategies.

Question 30

50% rule

Answer 30

states that, if the probability of finding an exact match for a request approaches 0, one third of all memory partitions are holes and two thirds are occupied blocks. Formally, n = 0.5 m, where n is the number of holes and m is the number of occupied blocks.

The 50% rule only refers to the number of holes but not the amount of space occupied by the holes.

If the average hole size is equal to the average occupied block size then 1/3 of memory space is wasted. But a smaller average hole size implies better memory utilization since less memory is wasted on holes.

Question 31

Swapping

Answer 31

the temporary removal of a module from memory. The module is saved on a disk and later moved back to memory. Dynamic relocation is necessary so that the module can be placed into a different location without modification.

Question 32

Memory compaction

Answer 32

the systematic shifting of modules in memory, generally in one direction, to consolidate multiple disjoint holes into one larger hole.

Question 33

Linking

Answer 33

the act of resolving external references among object modules and can be done statically, before loading, or dynamically, while the program is already executing.

Question 34

Static Linking

Answer 34

A program typically comprises many modules, not all of which are needed during every run. Most programs also link to systems libraries, many of which are rarely invoked. When modules are linked statically, all have to be in memory during execution.

Question 35

Dynamic linking

Answer 35

improves memory utilization by postponing the linking and loading of any module until the module is actually needed during execution. The loading of modules that are not called during execution is avoided entirely.

Question 36

Sharing

Answer 36

the act of linking the same copy of a module to multiple other modules. Sharing improves memory utilization by allowing multiple processes to share common routines or services (Ex: compilers, editors, word processors), or common data (Ex: dictionaries). Sharing is possible under both static and dynamic linking.

Question 37

Principles of paging

Answer 37

The main disadvantage of dividing memory into variable partitions is external fragmentation, which requires the searching of memory for holes large enough to satisfy each request.

In addition, swapping or compaction is necessary when no hole large enough is available.

Paging divides both the logical address space of a process and the physical memory (RAM) into contiguous, equal-sized partitions such that any logical partition can be mapped into any physical partition. Searching variable-sized holes becomes unnecessary.

Question 38

page

Answer 38

a fixed-size contiguous block of a logical address space identified by a single number, the page number.

Question 39

page frame

Answer 39

a fixed-size contiguous block of physical memory identified by a single number, the page frame number.

A page frame is the smallest unit of data for memory management and may contain a copy of any page.

Question 40

page table

Answer 40

an array that keeps track of which pages of a given logical address space reside in which page frames. Each page table entry corresponds to one page and contains the number or the starting address of the frame containing the page.

Question 41

Address translation

Answer 41

With paging, a logical address is broken into two components: a page number p and an offset w within the page. Similarly, a physical address is broken into two components: a frame number f and an offset w within the frame. The notations (p, w) and (f, w) denote the concatenation of the two address components.

The OS must translate logical addresses of the form (p, w) into corresponding physical addresses (f, w):

Given a logical address (p, w), access the page table entry corresponding to page p.
Read the frame number, f, of the frame containing p.

Combine f with the offset w to find the physical address (f, w) corresponding to the logical address (p, w).

Question 42

Paging as a solution to external fragmentation.

Answer 42

Paging avoids external fragmentation by having all pages and page frames the same size so that any page fits into any frame without creating holes between frames.

However, the size of a program is generally not an exact multiple of the page size and thus some space remains unused at the end of the last page.

Question 43

Internal fragmentation

Answer 43

the loss of usable memory space due to the mismatch between the page size and the size of a program, which creates a hole at the end of the program’s last page.

Most programs also do not need all pages of the entire logical address space and must be prevented from accessing any page not belonging to the program.

Some systems implement a valid-bit in each page table entry and prevent access to pages not belonging to the program. But the valid bit does not protect the unused fragment on the last partially filled page.

A better approach is to compare every logical address to the program size to prevent access to any memory locations not belonging to the program.

Question 44

Principles of segmentation

Answer 44

With paging, all components of a program, including code, static data, the stack, and other data structures, are combined into one contiguous address space divided into fixed-size pages.

Since the components are of variable sizes, the boundaries between the logical components do not coincide with page boundaries. The misalignment makes the sharing and the protection of logical components difficult.

Segmentation addresses the problem by providing multiple logical address spaces for each process, where each segment can have a different size.

Question 45

segment

Answer 45

a variable-size block of a logical address space identified by a single number, the segment number.

With pure segmentation (no paging), a segment occupies a contiguous area of physical memory and is the smallest unit of data for memory management.

Question 46

segment table

Answer 46

an array that keeps track of which segment resides in which area of physical memory. Each entry corresponds to one segment and contains the starting address of the segment.

Question 47

Address translation with segmentation

Answer 47

Similar to paging, segmentation breaks each logical address into two components: a segment number s and an offset w within the segment. With an n-bit physical address, 2^n addresses can be formed. If k bits are used for the offset w, then 2^n-k segment numbers can be formed.

A segment table is analogous to a page table but with two important differences:

• With paging, all pages have the same size, 2^k. Since segments have variable sizes, 2^k can’t be the actual segment size but only the max possible segment size.

To prevent access to locations beyond the segment, the segment size must be kept in the segment table entry and checked during address translation.

• With paging, the starting address of a frame can be determined from the frame number f, since all frames have a fixed size and thus all start with the address (f, 0). With segmentation, no frames exist and thus a segment table entry must contain the complete starting address of the segment, rather than just the segment number s.

Question 48

Segmentation with paging

Answer 48

The main advantage of segmentation is the ability to create multiple variable-size address spaces. The main advantage of paging is the ability to place any page into any frame in memory. To gain the advantages of both, segmentation can be combined with paging.

The logical address space consists of multiple variable-size segments but each segment is divided into fixed-size pages. A logical address is then divided into 3 components: a segment number s, a page number p, and an offset w within the page. A physical address is divided into 2 components as before: a frame number f and an offset w within the frame.

Every process has one segment table where each entry points to a page table corresponding to one of the segments and each page table entry points to a page frame.

Question 49

Mapping the logical address space to physical memory

Answer 49

Each page of the logical address space is mapped to one page frame. Segment and page tables are also mapped to page frames. Depending on the size of each table entry, a table can occupy one or more frames.

The number of entries in the segment table determines how many segments can be represented. The number of entries in a page table determines how many pages a segment can consist of.

If all tables occupy a single frame and all table entries occupy one word, then the size of the 3 address components (s, p, w) is identical. If a table entry is larger than one word or if a table occupies more than one frame, then the size of the corresponding address component (s or p) is larger.

Question 50

The translation lookaside buffer

Answer 50

Paging and segmentation both double the number of memory accesses because the address translation must first access the segment or page table.

When segmentation is combined with paging, the number of memory accesses triples: First the segment table is accessed, then a page table, and finally the page holding the addressed word.

A translation lookaside buffer (TLB) is a fast associative memory buffer that maintains recent translations of logical addresses to frames in physical memory for faster retrieval.

The TLB can store only a small number of translations. When all entries are full, a new translation must replace an existing one.

Question 51

principle of locality

Answer 51

states that locations accessed recently are more likely to be accessed again than locations accessed in the distant past. The TLB uses the principle of locality to always replace the least recently accessed entry.

Question 52

hit ratio

Answer 52

The TLB’s hit ratio is the fraction of memory accesses that find a match in the TLB. The higher the TLB hit ratio, the lower the overhead of address translation.