CISC 324 Quiz 2

bytes, address, primary, slowest, clock cycles

Memory:

• Massive array of circuitry (e.g. transistors)

• Organized in _______, each having its own unique ___________

• Part of __________ storage:

  • Direct contact with the CPU

  • Program’s instructions and data must move to memory before execution

• Memory is the ________ primary storage element

  • Accessing instructions/data in the main memory can take many _____________ (stalls CPU)

clock cycle  

A __________ is the time period during which a single pulse or cycle of the CPU’s clock is completed

• Each pulse or cycle of the clock allows the CPU to perform a basic operation

• Ex. a CPU with a speed of 2.5 GHz can execute up to 2.5 billion basic operations in a single second, assuming one operation per cycle. 

memory, memory parts, user processes, user processes, hardware

In memory management, the responsibilities of the OS are:

• Managing programs’ instruction/data movement in and out of _________

• Allocating and deallocating memory space as needed

• Keeping track of ___________ being used by each program

• Ensures processes operate within their allocated memory spaces for protection

  • Protect the operating system from access by ____________

  • Protect ____________ from one another

  • Protection via ___________

legal addresses, base registers, limit registers, kernel

Separate memory space for process:

• Range of _______________ that the process may access

• Implemented using ____________ and ____________

• Loaded by the OS in _______ mode

base register

Type of register used to implement process memory space:

• Holds the smallest legal physical memory address

limit register

Type of register used to implement process memory space:

• Specifies the size of the range

operating system, process, process, process, base and limit, base

A base and limit register define a logical address space

CPU, address, base, base and limit, memory

Hardware address protection with base and limit registers

logical, physical, symbolic, relocatable

The four types of addresses are…

logical address, virtual

Type of address ________________:

• Aka _______ address

• Addresses used by CPU, software, and the operating system

• Used to point to instructions, variables, and data

• E.g. Mov Ax, [0xF23E] 

logical address space, virtual address space

_______________ is the set of all logical addresses generated by a program during its execution, also referred to as _________________

memory management unit

The mapping from logical to physical address space is done by a unit called __________________ or MMU

physical address, RAM

Type of address _______________:

• Actual location on ______

• It is a unique identifier for a memory cell or a group of cells where program/data is stored physically

• Where processes physically reside when brought from disk

physical address space

_________________ is a range of unique memory addresses that correspond to the physical locations in a computer’s RAM

logical

Analogy for __________ addresses:

• The building’s management (the OS) has a directory (page table) that maps each mailing address to an apartment number

• When mail (data) arrives, the building’s manager (MMU) checks the directory to find out where to deliver the mail within the building.

• This system allows the residents to receive mail without knowing exactly where in the building their apartment is located, and they can even move apartments (data can move between physical memory locations) without changing their mailing address (logical address)

physical

Analogy for _________ addresses:

• A large apartment building (the computer’s memory) where each apartment (memory cell) has a unique apartment number (physical address)

• The residents of the apartment building use a mailing address (logical address) that includes a post box number at the building’s entrance, which in-turn refer to individual apartment numbers

process

When a __________ is loaded into memory, different parts go to different places (e.g. stack memory address, registers, etc.)

physical address

For any program, we need the ________________ to run it

symbolic address

Type of address ______________:

• Address in the source program, when the programmer writes the code and assigns names to variables and functions

• Ex. in age; // ‘age’ is a symbolic address or identifier

symbolic

_________ addresses are names that represent the memory location of the variable or function

symbolic

_________ addresses are not yet associated with any specific memory location

relocatable address

Type of address _________________:

• Memory addresses that are relative to the start of the program or library

compiler

A ___________ typically binds the symbolic addresses to relocatable addresses (such as “14 bytes from the beginning of this module”)

source program, compiler, object file, other project files, linker, executable files, loader, dynamically linked libraries, program in memory, compile time, load time, execution time (run time)

Multistep processing of a user program

compile time, load time, execution time

Mapping between logical and physical addresses can occur at different stages: ___________, ____________, _______________

compile time

Stage where mapping between logical and physical addresses occurs _____________:

• If address binding occurs at this stage, the physical addresses known → absolute binary code generated with static addresses identical to physical address

load time, relocatable address

Stage where mapping between logical and physical addresses occurs _____________:

• Compiled program is loaded into memory to be executed

• The operating system allocates memory for the program’s code, data, and stack segments

• Compiler generates ________________ (relative to base register), the OS/loader binds these addresses to physical addresses at load time

execution time 

Stage where mapping between logical and physical addresses occurs _____________:

• When process can move its occupied memory space during execution

• Used in most operating systems

• Addresses mapped at run-time using memory management unit (MMU)

0, physical, logical, R

Simple MMU operation:

• Logical addresses defined as offsets from address ___

  • Logical address space: from 0 to max_addr (for each process)

• Physical address translation:

  • _________ address = _________ address + Value ____ in relocation register

base address

______________ (value in relocation register): is the starting physical memory address where a program segment resides in RAM (separate base addresses for each process)

CPU, logical address, relocation register, MMU, physical address, memory

Dynamic relocation using a relocation register

dynamic loading

________________:

• For better memory-space utilization, only main program loaded at start

• Other routines (libraries, binaries, Java classes, plugins) kept on disk

• Loaded only when called by loader, which also updates address space

dynamic linking 

____________________:

• When linking is postponed until execution

• Linker does not include the library code in the program executable, but instead creates a reference to the library’s code

• At runtime, when the program is loaded into memory, the OS’s dynamic linker resolves these references by locating the necessary library functions and linking them to the program

• Allows multiple programs to share a single copy of a library in memory

MMU protection

_________________ is preventing a process from accessing memory of other processes

relocation register, limit register, logical address

MMU protection:

• When a process is dispatched by scheduler:

  • _______________ = Starting (smallest) physical address

  • ______________ = max_addr (for individual process) + 1

• Check made by comparing _____________ to limit register

  • If check not passed = Trap

  • If passed = address is translated by adding the value in the relocation register

CPU, logical address, limit register, relocation register, trap: addressing error, physical address, memory

MMU protection process

dynamic, routines/functions

Concern: Guaranteeing instructions and data needed by CPU in memory

• Solution: _____________ allocation/deallocation in memory to __________________

hardware

Concern: Protection of memory spaces of OS and processes from illegal access

• Solution: Mainly the role of the ___________; OS supports this role by maintaining and loading process address information in base and limit registers

address space

Two processes can have same or different logical address, since each process has a unique _______________

absolute address, relocatable address, symbolic address

main memory, contiguous, non-contiguous, hybrid (e.g. virtual memory), fixed partitioning, variable/dynamic partitioning, paging, segmentation

degree of multiprogramming

The _______________________ is the number of programs that can be loaded into memory at once

number of partitions

The ____________________ is the number of processes that can be loaded into memory

contiguous memory allocation, non-contiguous memory allocation

The two types of memory allocation are…

contiguous memory allocation

Type of memory allocation:

• OS assigns on partition in the memory for each process

  • Most OSs usually assigned the higher range in the memory

• Each process is contained in a single common section of memory

• We can’t split the memory for a process 

• Keep a table of available and occupied partitions

• Process not finding enough space either rejected or wait

fixed partitioning, dynamic/variable partitioning

The two types of contiguous memory allocation are…

fixed partitioning, degree of multiprogramming

Type of contiguous memory allocation ___________________:

• Memory is divided into fixed-size partitions

• ______________________ is bound by the number of partitions

internal fragmentation

With fixed partitioning, we have the problem of __________________

dynamic/variable partitioning

Type of contiguous memory allocation:

• Memory is allocated based on the size of the process (dynamic)

non-contiguous memory allocation

Type of memory allocation:

• Different parts of a program are allocated into non-adjacent memory locations

• Pages/segments loaded into different physical spaces in the memory

• We can split the process in the memory

internal fragmentation

Problem in fixed partitioning:

• Let’s assume the number of partitions is 5, each 5MB

• The degree of multiprogramming is 5

• Even though we have remaining memory, we can’t allocate other process in the free space

dynamic/variable partitioning

__________________ is a more efficient type of contiguous memory allocation because it is sized to a given process’s needs

external fragmentation, holes

Problem with dynamic/variable partitioning _____________________:

• All memory is initially available as one block then gradually occupied

• Releases and unequal allocations create _______ (blocks of available memory various small-size free slots scattered throughout memory)

  • When a process arrives, it is allocated memory from a hole large enough to accommodate it

  • Process exiting frees its partition

  • Gradually creates holes

first-fit, best-fit, worst-fit

In dynamic/variable partitioning, the three solutions to the problem of selecting a hole for a process of size n are…

first-fit

A solution to selecting a hole for a process of size n in dynamic/variable partitioning:

• Search from beginning or from last for the first appropriate hole

best-fit

A solution to selecting a hole for a process of size n in dynamic/variable partitioning:

• Must search entire list, unless ordered by size

• Results in the smallest leftover holes

worst-fit

A solution to selecting a hole for a process of size n in dynamic/variable partitioning:

• Full list must be searched

• Consumes largest holes first

first-fit, best-fit, first-fit

Comparison of the solutions for selecting a hole for a process of size n in dynamic/variable partitioning:

• _______ and ________ are better than worse-fit

• First-fit and best-fit perform similarly, but ________ is faster

external fragmentation

Type of fragmentation in contiguous allocation:

• Subset or all holes satisfy process by are not contiguous

• If N blocks are allocated, 0.5 N wasted → 50-percent rule

internal fragmentation

Type of fragmentation in contiguous allocation:

• If memory is divided into fixed-size partitions

• Only one process per partition

• Unused memory internal to partition

compaction, non-contiguous memory allocation

The two types of solutions to fragmentation in contiguous memory allocation are…

compaction, execution time, opposite

A solution to fragmentation in contiguous memory allocation ______________:

• Relocate processes in memory to group fragments into larger blocks

• Not possible for static address relocations done at compile or load times

• Only possible in dynamic relocation done at ________________

  • Move program and data

  • Change base/relocation register

• Simplest version of this solution can be expensive (e.g. when moving all assigned blocks and holes in __________ directions)

paging

___________ is a non-contiguous allocation approach

• Allows a part of the program to load in non-adjacent locations in memory

paging

_________ resolves external fragmentation by allows program parts to fill varying-sized memory holes (fragments)

pages

________ are fixed and equal-sized blocks of logical address space

• Size typically in powers of 2; e.g. 4 KB (2^10 bytes) to 4 MB (2^22) per page

• In Linux: type getconf PAGESIZE

frames

_________ are fixed-sized blocks of the physical memory

paging

Steps of _________:

• Loads pages of programs into any available frames in the memory

• Program of size N pages are loaded in N free frames

• Page size is equal to frame size

contiguous

Logical address division is always _______________

logical, page number, offset

___________ address division:

• 2^m addresses (total) divided into pages of size 2^n

• Number of pages → 2^m / 2^n

• m-n is the most significant bits of any address, also called ______________ (p)

• n is the least significant bits of any address, also called ________ (d) inside this page

page number

______________ or p is the pages in logical address space represented by the number of bits

page offset

_____________ or d is the number of bits to refer to a word within a page

logical address space, page size, number of pages, page number bits, m, n

Page number and offset example:

• ________________ = 64kB = 2^6 × 2^10 = 2^16

• __________ = 1 kB = 2^10

• __________________ = 2^16/2^10 = 2^(16-10) = 2^6 = 64 pages (pages 0 to 63)

• _________________ = 16-10 = 6

• ___ = 16 (bits required for logical address space), ___ = 10 (to address within each page)

page tables

_____________ map virtual addresses as seen by the CPU into physical address

process, RAM, process creation

One page table per _________, stored into _____, filled at ______________

page table base register, context switch

A ______________________ or PTBR stores the starting address of the page table for the currently running process

• On ____________, PTBR is updated with the newly loaded process

MMU

The _______ uses a process’s page table for address translation

offset, base

In a page table, the ________ of the logical points to the physical address in the frame starting from the _____ address

frame number, present/absent, protection, reference, caching, dirty, optional

CPU, logical address, p, d, physical address, f, d, p, f, page table, physical memory, f

address translation

______________ in paging steps:

1. Extract p and d

2. Get p’s frame base address (f) from table

3. Append/add d to f to obtain address in memory

logical memory, page table, frame number, physical memory

logical memory, page table, physical memory

paging

There is no external fragmentation in _________, but internal fragmentation may still occur (last frame not filled with information in last page of program)

• Example:

  • Page/frame size = 2048 bytes

  • Process size = 72766 bytes

  • 72766/2048 = 35 pages + 1086 bytes

  • Internal fragmentation of 2048 - 1086 = 962 bytes

  • Allocation: 36 frames - one having 962 unused bytes

n+1, 1/2, smaller

With internal fragmentation in paging:

• Worst case: process that is split into n pages plus 1 byte would be allocated _____ frames

• Average case: ____ page/frame size

• Solution: ________ page/frame sizes

  • Larger overhead in keeping and searching larger page tables

high-speed registers, address translation, context switching, 2^8

Implementation of page table via dedicated ________________:

• Each register storing one entry in the page table

• Pro: Very fast in __________________

• Con: Very slow ________________ (content of each register must be exchanged by the page table entry of the next process)

• Fact: Satisfactory for small page tables up to ____ entries

memory, larger, PCB, page-table base register, context switching time, memory access time, page table, physical address

Implementation of page table via ___________:

• Suitable for _______ (most common) tables (e.g. 2^20 entries)

• Pointer to page table base address (where page table is located) in memory is stored in ______

• The pointer is loaded from PCB into a ___________________ or PTBR at context switching

• Pro: Much faster _____________________ (changing processes requires only a change in this register)

• Con: Slower __________________ (two memory accesses to reach physical address: one to locate the __________ and the other to access the identified ________________)

translation look-aside buffer

A solution to the 2-step memory access problem in the page table implementation via memory is a special fast-lookup hardware cache called the __________________ or TLB

translation look-aside buffer

The ____________________ or TLB stores the recently used virtual-to-physical address translations to speed up the memory access process

instructions, data, MMU, hit, miss

TLB used in page search:

• TLB stores a few page-table entries between 32 and 1024

• Sometimes two TLBs are used, one for ______________ and one for ______

• The _____ checks if the page number is in the TLB:

  • If so: _____ - Base address is extracted and used to access memory

  • If not: ______ - 2-step memory access (get the address from the page table)

LRU, RR, random

Replacement in TLB:

• Add recently called address in TLB instead of an existing one

• Replacement policies: _____ (least recently used), ____, _________

CPU, logical address, p, d, page number, frame number, TLB, TLB hit, f, d, physical address, physical memory

CPU, logical address, p, d, page number, frame number, TLB, TLB miss, p, f, page table, f, d, physical address, physical memory

effective access time

Access time differs between TLB hit and miss cases

• ________________ or EAT defines the overall performance of the system

hit ratio

___________ is the proportion of time a page is found in TLB

miss ratio

__________ is the proportion of time a page is not found in TLB (1- hit ratio)

access time

__________ is the time needed to access the memory once

hit ratio, access time, miss ratio, 2, access time

The formula for EAT is _________ x __________ + _________ x ___ x _____________

memory protection

_________________ is implemented by associating a protection bit with each frame to indicate if read-only or read-write access is allowed

• Can also add more bits to indicate page execute-only, and so on

valid-invalid bit, valid, invalid, page table length register, trap

A ________________ is attached to each entry in a page table:

• _______ indicates that the associated page is in the process’s logical address space, and is thus a legal page

• _________ indicates that the page is not in the process’s logical address space

• Or use a __________________ or PTLR

Any violations result in a ______ to the kernel.

virtual address, frame number, valid-invalid bit, page table, physical address