COSC360 Exam 2

Multiprogramming

multiple processes are ready in memory to run at a given time and the OS can switch between them

Timesharing

OS rapidly switches CPU among multiple processes giving the illusion of interactive use of the machine

Interactivity

allows users to receive timely responses from the system while their programs are running instead of waiting long periods

Address space

running program’s view of memory in the system; set of addresses you have access to

Virtual addresses

address used by a program within its address space; not real physical address, but translated by OS and hardware into physical address

Process protection

OS ensures a process cannot access/modify memory outside its own address space

Stack

memory is automatically allocated/deallocated by the compiler; function calls, local variables, and return values; aka automatic memory

Heap

allocations/deallocations are explicitly handled by the programmer

malloc()

allocated a specified number of bytes on the heap and returns a pointer to that memory

free()

deallocated previously allocated heap memory

Garbage collection

system detects unused memory and frees it

Common memory errors

Forgetting to allocate memory → seg fault

Not allocating enough memory → buffer overflow

Forgetting to initialize allocated memory → uninitialized read

Forgetting to free memory → memory leak

Freeing memory before you’re done with it → dangling pointer

Freeing memory repeatedly (double free) → undefined

Calling free() incorrectly → invalid frees

Address translation

hardware transforms each memory access and changes the virtual address to a physical address where the desired information is located

Physical address

actual location in main memory (RAM) where data resides

Virtual address

each memory reference generated by the process; address generated by a program; part of its own private address space

Base

used to transform virtual addresses into physical addresses

Bounds

ensures addresses are within the confines of the address space

Memory management unit (MMU)

part of the processor that helps with address translation, checks if addresses are within bounds, helps enforce memory protection

Free list

a list of the ranges of the physical memory which are currently not in use

Segmentation

Idea of having a base and bounds pair per logical segment of the address space

Allows OS to place each one of the segments in the address space (code, stack, heap) in different parts of physical memory

Segmentation fault

arises from a memory access on a segmented machine to an illegal address

Segment vs offset values

Segment is determined from the top bits of the virtual address, offset is the remaining bits which specify the location within the segment

Segment is which section of memory you’re talking about, offset is how far inside that section you go

Hardware uses segment to select correct base bounds pair and uses the offset to check if it is within bounds and adds it to the base to form the physical address

External fragmentation

problem where physical memory becomes full of little holes of free space

Internal fragmentation

any unasked for/unused space in chunks of memory bigger than that requested handed out by the allocator

Splitting

find free chunk of memory that can satisfy the request and split it into two; first chunk will return to caller and second chunk will remain on the list

Coalescing

When a chunk of memory is freed, merge it with neighboring free chunks into a single larger free chunk to reduce fragmentation

Header block

kept in memory usually just before the handed-out chunk of memory; minimally contains size of the allocated region and may contain additional pointers to speed up deallocation

Best Fit

find chunks of free memory big/bigger than requested size in free list and return the smallest

Worst Fit

find largest chunk and return the requested amount and keep remaining large chunk on free list

First Fit

finds first block that is big enough and return requested amount to user; advantage is speed

Next Fit

keeps and extra pointer to the location within the list where one was looking last

Pages

fixed-size block of a process’s virtual memory

Frames

fixed-size block of physical memory; each page is stored in one page frame

Page table

per-process data structure that stores address translations for each of the virtual pages of the address space letting us know where in physical memory each page resides

Virtual page number

part of virtual address that identifies which virtual page and is used to index the page table

Offset (in segmentation)

How far from the start of the segment the address is (aka where inside the segment)

PA = Base[segment] + Offset

Segment

Continuous chunk of virtual memory; each represents a logical part of the program (ex: code, heap, stack); often determined by top bits of the VA

Offset (in paging)

part of VA that specifies which byte within a page is being accessed

Physical frame number

Physical addresses; identifier of a physical page frame in memory; used in page table to translate virtual page into its physical memory location

Valid bit

indicates whether the particular translation is valid; crucial for supporting a sparse address space

Present bit

indicates whether this page is in physical memory or on a disk (meaning it has been swapped out)

Hard disk drive

place to stash away portions of address spaces that currently aren’t in great demand; sit at the bottom of the memory hierarchy with memory just above

Swap spaces

space on the disk reserved for moving pages back and forth; swaps pages out memory to it and then swaps pages into memory from it

Page hit

occurs when CPU accesses a memory page already present in RAM

Page miss/fault

act of accessing a page that is not in physical memory

Page in

process of reading a page from disk into physical memory

Page out

process of writing a page from physical memory to disk

Page-replacement policy

Process of picking a page to kick out/replace

Eviction

process of removing a page from physical memory to make space for a new page when memory is full

Cache

fast memory holding recently/frequently used pages so they can be accessed quickly

Optimal replacement policy

policy that evicts the page that will be used farthest in the future and produces the fewest possible misses

Policies: FIFO

Evicts the page that has been in memory the longest

Policies: Random

Evicts randomly chosen page

Policies: Least Recently Used (LRU)

replaces least recently used page

Policies: Least Frequently Used

replaces least frequently used page when an eviction must take place

Policies: Most Recently Used (MRU)

Evicts page that was used most recently

Policies: Most Frequently Used

Evicts page with the highest number of accesses

Dirty Bit

aka modified bit; set any time a page is written and thus can be incorporated into the page-replacement algorithm

associated with a page that indicated whether it has been modified in memory

1 → page has been modified so the OS must write it back to the hard disk before replacing to avoid data loss

0 → page has not been modified and can be discarded without updating disk

Demand Paging

OS brings the page into memory when it is accessed “on demand”

Thrashing

condition where system spends most of its time swapping pages in and out (paging) instead of executing programs usually because there isn’t enough physical memory