cse3320 - operating systems (OS) final exam review

operating systems

a collection of software that manages computer resources and gives user an interface

interrupts

• handled by the isr (interrupt service routine)

• array of function pointers pointing to the interrupt vector

• some small os systems use an event loop (status-driven system)

system calls

• user generated

• how we request to use resources

• malloc, printf, fread/open/close

• non-resource using functions are simple library calls

program

instructions written for a task

process

an instance of the program in execution

x86 ring protection

mechanism in x86 architecture to protect system resources (memory and I/O) from unauthorized access by less-privileged software.

just remember 0 is most privileged, ring 3 the least

how to switch from user to kernel?

1. switch processor to kernel mode

2. save and reload MMU (memory management unit) to switch to kernel address space

3. save program counter and reload with the kernel entry point

how does an OS track a process?

pid - process ids, with the datatype being pid_t (int) and PCBs

what is a PCB

Process Control Block

• one per process

• contains all the info you’d need to know, 170+ fields

• includes pointers to other structures like file and memory tables

• held in a task_struct (array of pointers to pcbs)

why the term “task”?

tasks represent both processes and threads

monolithic kernels

• used to one big blob loaded into memory

• all functionality in one space

• linux and ms-dos

what are the pros and cons of a monolithic kernel?

pros:

• everything is in ring 0 so no need to switch

cons:

• bloated

• blue screen of death can take down OS

layered architecture

modules in one layer call functions provided in that layer

object oriented architecture

• each OS module becomes an object and provides services

• any object can invoke another object’s functions

microkernel

• basic functionality in kernel (only code that needs priv. resources/instructions)

• everything else runs in user space

• less code in R0

• easier to inspect for flaws because of a smaller codebase

• could be slower as more interrupts will be called from user→kernel

Most OSes today are min-maxed to have as little code in the kernel and as much user functionality.

host (vm)

underlying hardware system

vmm / hypervisor

stands for virtual machine manager

creates and runs VMs by providing intrefaces identical to host

paravirtualization

guest OS modifed to work with the VMM

programming environment virtualization

VMM for virtual environments and not hardware (think .NET or the JVM for Java)

emulators

allow apps written for an environment to run on a different hardware license

vm benefits

• isolated from host OS

• freeze, suspend/resume, snapshot/resume, restore, clone

• multiple OSes on a system

type 0 hypervisor

• hardware-based, hypervisor supporting VM management and creation w/ firmware

• IBM LPAR, Oracle LDOM

type 1 hypervisor

• bare-metal hypervisor

• runs directly on the hardware, eliminating the overhead of a host OS

• VMware ESX, Citrix Xenserver, HyperV, KVM

type 2 hypervisor

• apps built to run on OSes and provide VMM features to guest OSes

• VMware Fusion and Workstation, Oracle Virtualbox

binary translation

when a VM OS wants to run a private instruction, the VMM tells the hypervisor to translate it into a non-privileged instruction.

process creation

• process gets created by a parent process using fork()

• init.d is the first process with no parent

• almost everything is inherited from parent, excluding:

  • pid, parent pid, file locks, pending alarms, pending signals

what does fork return?

• 0 in child process

• pid in parent process

why might fork fail?

• too many processes running

• too many processing for the current user

how would you terminate a process?

1. return from main function

2. C library exit

3. system can call _exit

   1. used when exec fails

what are some abnormal ways to terminate a process?

1. abort signal

2. any other abort

zombie process

a process that has completed execution but still lives in the process table

• this is so the parent can read the child’s exit status

orphan process

a child process whose parent process has terminated before the child process has finished running

child processes will always?

1. become zombies

2. read by parent

3. reaped by system

wait() and waitpid() do?

wakes up a process when the next child terminates.

child termination is asynchronous.

exec

Whenever exec is called, a new program specified by exec completely replaced the running process.

• text, data, heap, and stack are all replaced

• pid stays the same

exec family

exec(char const*file/path, *arg0/argv…)

options:

• l - list of command line arguments provided

• e - pointers to environment variables

• p - path environment variable used to fine file

• v - take in argv in array format

psuedo-parallelism

single CPU systems only run 1 process at a time, so processes are context swtiched between giving the illusion of parallelization.

multi-CPU systems have true parallelization and can run multiple processes at a time.

process model

• all running software is organized with sequential processes

• each process has a virtual CPU

• true CPU is shared

  • multiprogramming is the switching back and forth between processes

context switch

act of switching CPU from one process to another.

• context refers to the contents of the CPU register and program counter

steps to context switch?

1. pause the process and store the context somewhere

2. get and load the context of the next process

3. go to the line of code defined by the program counter and resume process execution

process states

1. running (using the CPU)

2. ready (paused for other process)

3. blocked (unable to run until external event happens)

CPU utilization formula

performance does not scale linearly.

say a process uses a fraction of the time p waiting for io; with n being the # of processes in memory, we can calc. CPU util with:

CPU Util = 1 - p^(n)

what are the types of scheduling?

• cooperative multitasking

  • processes voluntarily give up CPU usage

• pre-emptive multitasking

  • OS forcibly stops process and starts new one

what are the different types of scheduling systems?

• batch

  • for large mainframes

  • non-preemptive or preemptive with long time quantum ok

• interactive

  • preemptive for responsiveness

  • general purpose

• real time

  • sometimes preemptive

what are the goals for all of scheduling?

• policy enforcement: ensure it is carried out

• balance: keep all parts of system busy

what are the goals for batch scheduling systems?

• maximum throughput

• turnaround time

• maximum CPU utilization

what are the goals for real-time scheduling systems?

• predictability

• determinism

what are the goals for interactive scheduling systems?

• responsiveness

• meets user performance expectation

what are some scheduling metrics?

• *throughput: jobs per unit of time

• *turnaround time: time from arrival to completion

• *response time: time from process submission to process run

• wait time: time spent in queue

• cpu utilization

* means it is skewable

fcfs

first-come-first-serve

shortest job next

• based on runtime

• shortest job is picked out of the ones currently available

turnaround time

sum of (time of finish - time of arrival) / n

response time

sum of (time start - time arrived) / n

shortest job next w/ preemption

• same selection process as sjn

• if process in waitqueue has a runtime less than the remaining current process’ runtime, we can jump in

priority

highest priority first

priority w/ preemption

same as priority except we can switch whenever a process with a higher priority enters the queue

address space

• set of addresses in ram a process can use

• more programs = more partitions for memory

• segmentation faults can occur when you r/w to memory out-of-bounds

threads

in normal OSes, each process has an address space and 1 line of execution.

threads are multiple lines of execution and a share the address space.

what are some benefits of threads?

• overlaps CPU work with I/O; say we have a long I/O wait in a program, threads allow us to run CPU-intensive work while waiting

• more important tasks can be scheduled better

what is a user space thread?

• OS does not need to be aware of it

• can be implemented in any OS

• doesn’t need to switch into the kernel

• one blocking call makes all threads stop

• one page fault also makes all threads stop

what is a kernel space thread

• aware of all threads

• switches kernel-user boundary a lot

race conditions

when 2 or more processes/threads are r/w shared data, and the output depends on who ran what and when.

critical regions

• prevent race conditions from happening

• part of the program where shared memory is accessed

• example is a pthread mutex

mutex

• pthread_mutex_lock

  • locks mutex variable. blocks other calling threads until the mutex is unlocked

• pthread_mutex_trylock

  • tries to lock mutex. if it is already locked, return busy error code

• pthread_mutex_unlock

  • unlocks mutex if owned by that thread. must call to unlock for other threads

  • error occurs if it is already unlocked or the calling thread is not the owner of the mutex

what are the 4 ways to avoid race conditions?

1. no two processes can be in the same critical region together

2. no assumptions can be made about speed or number of CPUs

3. no prcess running outside the critical region can block processes

4. no process should wait forever to enter the critical region

priority inversion and starvation

• starvation and indefinite blocking

  • process is not deadlocked but not removed from the semaphore queue

• priority inversion

  • lower-priority process holds lock needed by higher priority process

  • can be solved by a 2-priority system or by priority elevation to the owner of the resource

deadlocks

when 2 processes/threads become blocked waiting for a resource that the other one has

can happen in networks.

what are the types of resources?

1. preemptable: can be taken away from a process w/ no ill effects

2. non-preemptable: one that cannot be taken away w/o potentially causing failure

what are the conditions for a deadlock to occur?

• mutual exclusion

  • each resource is currently assigned to one process or is available

• hold-and-wait

  • processes holding resources that were granted earlier can request new resources

• no preemption

  • previously granted resources cannot be taken away, and MUST be released by the process

• circular wait

  • there must be a circular list of two or more processes, each of which is waiting for a resource held by the next member of the loop.

how can we deal w/ deadlocks?

1. it goes away by itself

2. detect and recover

3. dynamic avoidance by careful resource allocation

4. prevention

what are the 5 types of binding?

• coding

• compiler

• link

• load

• run

what is binding?

binding is how the computer associates variables/functions/instructions to memory addresses.

relocation

when the compiler knows it has a func/var, but does not have enough info to figure out where to put it, it can leave a note in the relocation table for the linker to fill in the address later.

volatile storage

loses memory when power is taken away

nonvolative storage

keeps memory when power is taken away

memory manager

part of os that manages memory, tracking everything.

physical addresses

addresses used to refernce to physical memory

logical addresses

addresses the CPU generates as a program executes

how would you convert from a logical address to a physical one?

you need a base register, which denotes the “start” and “end” of where your process lives in memory.

logical + base register = physical

swapping

bringing an entire process into physical memory, run it for a bit, then send it back to the disk

internal fragmentation

there is unused memory in a fixed-size chunk

e.g. motorcycle in a car parking space; there is open space, but you cannot use it.

external fragmentation

there are available memory blocks but they are not contiguous (not touching one another)

e.g. bus looking for parking; if we combined open spaces, there would be space for a bus, but if they are scattered the bus will not fit

compaction

reorganizing fragmented space, expensive to do so

first fit

chooses the first block with a size >= the requested memory

a downside is that it tends to retread areas, meaning it will go back to the beginning every time to find the first available block.

next fit

first fit but the next request starts where the last allocation occured; this solves the retreading problem.

it goes back to the beginning if no space has been found.

best fit

searches heap end-to-end to find block closest in size to request with the least wasted space in the block.

worst fit

opposite of worst fit, meaning it finds the block with the most space.

worst fit is good at breaking down larger blocks.

what are the ways we can manage free memory?

• bitmap

• free list

bitmap

there is 1 bit per block on the disk.

• 1 = in use

• 0 = free

most space efficient over the long term, as it will always remain the same size.

free list

a linkedlist where each element points to the next open block.

better for determining contiguous blocks.

pages

divisions of the virtual address space into fixed size partitions

frames

divisions of the physical address space into fixed size partitions

page tables

used to translate virtual addresses into physical addresses.

every entry has these fields:

• frame #: physical frame where this page resides

• valid/invalid bit: if the page is in physical memory

• r/w bit: is the bit r/w-able

• executable: can we execute the code in that page

• c/nc: cache/no cache

page 0 holds the offset of the ram (similar to base register from earlier)

parts of a virtual address

[ page number | offset ]

page #: what page the data is on

offset: where inside the page the data is

number of entries = 2^(page number)

size of page = 2 ^ (offset)

translation look aside buffer (tlb)

a cache where we keep frequently accessed pages.

• holds the last n number of lookups we did in our page table

• costs e (TLB lookup time), where e < M (time it takes to access memory normally w/o cache)

serial effective access time

serial does these steps in order:

[tlb lookup] → [use phys. addr.] → [memory access]

M = memory lookup time

e = TLB lookup time

a = % a hit is successful

2M = on lookup failure, you must go through page table → frame table, forcing you to do 2 memory lookups

serial EAT = (M + e)(a) + (2M + e)(1-a)

serial TLBs tend to be larger than parallel ones and therefore have better hit rates (a).

parallel effective access time

the difference between parallel and serial is that the TLB runs both the TLB lookup (e) and normal memory lookup at the same time (2M).

M = memory lookup time

e = TLB lookup time

a = % a hit is successful

2M = on lookup failure, you must go through page table → frame table, forcing you to do 2 memory lookups

parallel EAT = (M + e)(a) + (2M)(1-a)

parallel TLBs tend to be smaller to accomodate for the extra logic.

page fault

when a process tries to access a virtual addreess not loaded in physical memory

locality of reference

• temporal locality

  • recently used data/instructions are likely to be used again soon

  • loop counters, stack vars, recent array elements

• spatial locality

  • data near recently used addresses are likely to be used soon

  • sequential instructions, iterating through a loop

what does locality of reference have to do with page tables

locality is why paging works efficiently; it depends on locality.

storage in the page table often times means there will be fewer invalid lookups, meaning:

• better TLB hitrate

• fewer page faults