cs 370 - midterm 1

polling interrupt system

the processor repeatedly checks each device

vectored interrupt system

device tells processor that they were the ones who interrupted
interrupting device provides the processor with a unique address that points to its service routine

interrupt handling

The mechanism by which the processor detects, saves the current state, services the interrupt through an interrupt service routine, and then resumes normal execution.

process

• an executable stream (list of executables)

• a running program

• give each one an illusion its running alone and using CPU

• each is allocated memory and loaded into main memory. The memory contains:

  • text section: program code

  • stack: temporary data, local variables

  • data section: global variables

  • heap: memory dynamically allocated

  • block starting symbol (BSS): uninitialized variables

program is static code/data and process is a dynamic instance of code/data

whats the difference between a program and process?

operating system

• invested by General Motors Research Division for IBM mainfraims

• resource manager of CPU, memory, disk, etc

• A body of software the makes it easy to run programs, allow programs to share memory, and enabling programs to interact with devices

monolithic kernel

One of the structures of an operating system where everything is in the kernel (UNIX)

microkernel

One of the structures of an operating system where most of the OS code is in the user space (Mach, Amoeba)

MS-DOS

One of the structures of an operating system where its a simple, single-tasking, single-user disk operating system with no multitasking or protection

layered

One of the structures of an operating system where its divided into levels. Layer 0, the center, is the hardware and the highest level is the user interface

modular

One of the structures of an operating system where they implement loadable kernel modules. Each component (file systems, scheduling classes) is separate and loaded into kernel as needed

hybrid

One of the structures of an operating system that is not a pure model but combines multiple approaches

SYSGEN

the process of configuring and building an operating system so it is tailored to run on a specific computer system

Execution starts at a fixed memory location, and the initial boot code is stored in firmware ROM.

Where does execution begin when the system is powered on, and what holds the initial boot code?

A small piece of code, stored in ROM or EEPROM, that locates the kernel, loads it into memory, and starts it.

What is the boot loader, and where is it stored?

The ROM code loads a boot block, which then loads the boot loader from disk.

How does the two-step boot process usually work?

user mode (mode bit = 1) and kernel mode (mode bit = 0)

dual mode consists of what modes and what are their values?

system calls

services provided by the OS and accessed through APIs

a number is associated with each system call and system call interface maintains a table indexed according to these numbers

a type of trap

registers, block/table in memory and address of block

most system calls to pass parameters to the OS (from system calls) are through

blocked state

state of a process where it performed an operation that makes it not ready until some other event takes place

ready state

state of a process where the process is scheduled and ready to run

running state

state of a process where the process is running on a processor (CPU) (executing instructions)

processor control block (PCB)

where the processor contents and state of a process are stored (Process identifier (PID), process state, scheduling priority), especially useful when processes are being switched

separate for each process

trap

a type of interrupt that saves registers into main member, stack pointer, PC, in kernel space

build a new empty process from scratch or copy an existing process and change it appropriately

what are two ways to create a process?

fork()

where you create a new process (more specifically a copy of the process that called it

• Both the parent and child continue execution from the point of the fork() call.
  
  In the parent process, fork() returns the PID of the child.

• In the child process, fork() returns 0.

pid_t pid = fork();

if (pid == 0) {
    // This is the child process
} else {
    // This is the parent process
    // pid contains the child’s PID
}

exec()

when to run program that is different from calling program, essentially replaces the program that called it

does not return if it succeeds

wait()

a process wants to wait for a child process it made to complete to get its exit code and PID

exit()

when process reaches its end and asks the OS to delete it. 0 is successful and -1 is an issue

zombie state

when the program exited but has not been cleaned up/called wait from its parent process (its PCB is still there)

can be prevented by the parent process calling wait() to wait for its completion and tell OS to clean it up

abort()

when parent terminates executino of a child either because

• child exceeded allocated resources

• task to child is no longer required

• parent is exiting and the OS doesn’t allow the child to continue if its parent terminates

orphan state

when parent process terminates without invoking wait while program is running

Static: code, global variables
dynamic: stack and heap

address space is the addresses the process has. Whats in an address space?

time sharing

one of the ways to run processes simultaneously by running a process, stopping, and running another by saving CPU registers to memory when process isn’t running

load its code/static data into memory, initializing the stack, do I/O work, and transfers control to CPU to process

how does OS get a program running?

space sharing 

one of the ways to run processes simultaneously by sharing memory across processes

memory management unit

part of processor that helps with address translation. Checks if its bounds. Adds base register to logical address to form physical address.

may also contain a segment table for each process in segmentation implementation

base register

smallest physical address

bounds register

size of this process’s virtual address space
OS kills process if it goes beyond this 

context switching

the operating system’s process of saving the state (like base and bounds registers) of the currently running process and loading the state of another process so the CPU can switch execution between them.

free partition

block of available memory

first fit

one of the ways to satisfy a request of size n from a list of free memory

find the first block that is big enough and return amount to user. Put back any space not used

best fit

one of the ways to satisfy a request of size n from a list of free
memory

search through the free list and find the smallest chunk that is as big/bigger than the requested size. Put leftover memory back.

produces smallest leftover free partitio

worst fit

one of the ways to satisfy a request of size n from a list of free
memory

Find the largest chunk and allocate the requested amount. Put the leftover on the freelist. 

performs badly and produces the largest leftover free partition

advantages of base & bounds registers

• provides protection

• supports dynamic relocation

• simple 

• fast

disadvantages of base & bounds registers

• each process must be allocated contiguously

• no partial sharing: cannot share limited parts of address space

external fragmentation

Have enough space in total but not contiguous space

physical memory comes full of little holes of free space, making it hard to allocate new segments

internal fragmentation 

Have a process where you have wasted space

allocated memory may be slightly larger than requested memory (a portion of the internal memory is not used)

segmentation

• have a base/bound pair for each segment (code, stack, heap) of address space (instead of one pair)

advantages: enables sparse allocation of address space, different protection for different segments, enables sharing of segments, supports dynamic relocation for each segment 

disadvantages: segments must be allocated contiguously, internal fragmentation still an issue, external fragmentation may happen for large segments

top two

in segmentation, we use the ___ ___ bits from the logical address for segment

lowest bits

in segmentation, we use the ___ ___ bits from the logical address for offset within segment

paging

another way to virtualize memory by splitting address space into fixed sized units called a page and physical memory is also split into pages, called page frames

eliminates requirement that address space is contiguous

- still internal fragmentation but no external fragmentation
- page tables take a lot of memory
- doubled the time to translate addresses from virtual to physical because of page table lookups
- fast to allocate/free because no searching for suitable free space
- simple to swap memory to disk

1,024 B

1 KB =

page table

maps virtual page number to physical page frame
- also contains valid (whether or not that page has been allocated by the process), protection, present, reference, and dirty bit

split it into a virtual page number and offset, replace virtual page number with physical frame number

to translate a virtual address with paging you do what?

offset

tells us which byte within page we want

log₂(page size in bytes)

given known page size, how many bits are needed in address to specify offset in page?

2¹⁰

how many bytes in a KB

2²⁰

how many bytes in a MB

2^(# bits for page number)

given the number of bits for page number, how do you calculate how many pages are there?

page table base register

points to the page table

page table length register

indicates size of the page table

2^12

how many bits is 4 KB?

translation lookaside buffer (TLB)

helps speed up address translation and minimize number of memory accesses per instruction by caching recently used page table entries.’'

has page number, page number, valid bit (whether entry has a valid translation in it), and other bits

don’t have to go to page table every single time

resides in CPU

usually improves performance for memory accesses with high spatial and temporal locality, not random memory accesses 

improve performance by:
- increasing page size (fewer unique page translations needed to access same amount of memory)

disadvantage:
- TLB increase cost of context switches

fully associative

what most TLBs are these days and simultaneously checks all of them at once through parallel; no hash function

number of TLB misses / number of TLB lookups

the equation for TLB miss rate

number of TLB hits / number of TLB lookups

the equation for TLB hit rate

1 + TLB miss rate

effective access time (EAT)

number of TLB entries * page size 

TLB Reach is how much memory you can access in TLB. how do you calculate it?

flush TLB on process switches, have an address space identifier (ASID) so processes can share TLB 

how to deal with multiple processes and TLB?

inverted page tables

only need entries for virtual pages with valid physical mappings 

physical page maps to corresponding page table

each segment has a page table

what happens when you combine paging + segmentation?

Disadvantage:
- potentially large page tables for each segment

multi-level page tables

a different structure for page tables that are not contiguous

• page the page tables

• if an entire page of page table entries is invalid, don’t allocate that page

• creates multiple levels of page tables; outer level “page directory”

• each page table fits in within a page