CS 162 Midterm 1 Review

c review session

basics

• false = 0, NULL, false (with #include )
• sizeof
  • (int) = # bytes in an integer, 4 bytes
  • (int*) = # bytes in a pointer, 8 bytes
  • (char) = 1 byt

pointers

• memory is one big array, and a memory address is just the index of a memory array
• each memory address holds one byte of data
• 0x7F368F68 is in a 32-bit system cuz it has 8 bytes * 4 bits per byte
• & = get the memory address of a variable
  • NULL is used if a pointer is invalid
• • = get the value (dereferencing)
• array is made like: int array[size] or (int ) malloc(sizeof(int)*3)
• strings will always end in “\0” null terminator
  • strncpy, strncat, strcmp

memory layout

• text = instructions of the program
• data (+bss) = statically allocated data aka globa/static variables, Strings, constants
  • global vars can be accessed by all functions and exist for the projects lifetime
• stack = local variables for each function call
  • stores local arguments and function parameters in a stack frame and removes when the function returns
• heap = dynamic memory that persists beyond function calls (malloc)
  • malloc, calloc, realloc, free

data structures

• struct my_struct { int x; char* y; }
• typedef = creates a new type that has the exact same structure as a data type
  • typedef <data type> <new data type name>
  • typedef int my_int;
• types.h
  • off_t (signed int for file offsets)
  • pid_t (signed int for process ids)
  • pthread_t (unsighted int for thread identifying)
  • size_t (unsigned int for size of obj)

useful functions

• strlen, strcpy, strcmp, fprintf, fopen, fclose, fread, fwrite
  • high level C library function
  • fread() maintains a user level buffer and always reads desired num bytes (read may not)
    • also fread calls read() during operation
• strcmp = 0 equal, >0 if str1 is greater, <0 if str1 is less

lec 1: what is an operating system

• operating system = implements a VM for application whose interface is easier to interact with than the raw hardware
• three main hats
  • referee = manage protection, fault isolation (process, dual execution mode), resource sharing (scheduling), communication (pipes/sockets)
  • illusionist = provide clean, easy to use abstractions of physical resources
  • glue = provides a set of common services, make sharing easier, minimuze reuse
• evaluation criteria
  • performance = implement the abstraction efficiently with low overhead, and equitably
    • overhead = added resource cost of implementing an abstraction
    • fairness = How “well” are resources distributed across applications
    • response time = how long does it take for a task to complete
    • throughput = Rate at which group of tasks can be completed
    • predictability = Are performance metrics constant over time?
  • reliability = system does what it should
    • availability = mean time to failure + mean time to repair
  • security = minimize vulnerability to attack
    • integrity = computer’s operation cannot be compromised by a malicious attacher
    • privacy = data stored on computer accessible to authorized users
  • portability = portable abstraction does not change as the hardware changes

lec 2: processes and kernels

requirements for virtualization

• the OS protects…
  • applications from other application’s code
  • OS from the applications
  • applications against inequitable resource utilization (memory, CPU time)

what is a process

• process = instance of a running program

• process life cycle

• process control block = process management by the OS, stores necessary metadata
  • PC, stack ptr, registers, pid, uid, list of open files, process state

operating system kernel

• lowest level of OS running on system
• kernel is trusted with full access to all hardware capabilities (all others are untrusted)
• dual mode operation
  • fixes the challenge of safe operations
  • use a bit for two modes of execution
    • user mode = processor checks each instruction before executing and limited set of safe instructions
    • kernel mode = executes with protection checks off (faster) and can execute anything

user vs kernel

• user = shell, C standard library
  • integer overflow and fread can happen here
• kernel = device drivers and scheduler
  • opening a file and dereferencing a NULL pointer are both procedures that leads to a transfer from user mode to kernel mode

hardware will support

• privileged instructions = unsafe instructions cannot be executed in user mode
  • cannot change mode bit, change address space, disable interrupts, perform IO operations, or halt the processor
  • iret is NOT allowed
  • int $0x30 is how you issue syscalls
• memory isolation/protection = memory accesses outside a process’s address space prohibited
  • OS and application both in memory and cannot read/write kernel memory
  • use virtualization for better control
    • expandable memory, sharable memory (virtual address → phys address), every process’s memory always starts at 0, we can dynamically change VA-PA mappings (no fragmentation!)
• interrupts = ensure kernel can regain control from running process
  • set to interrupt processer after a specific delay or specified event to regain control
• safe transfers = correctly transfer control between modes
  • system calls and exceptions (synchronous events aka trapping)
  • interrupts = async and can be maskable/nonmaskable
  • system calls = “narrow waste” cuz they ease into the user space and hardware

safe control transfer

• exceptions
  • any unexpected condition caused by user program will stop executing and enter kernel
  • synchronous and non-maskeable
  • processes missteps, attempted to execute a privileged instruction in user mode, debugger breakpoints
  • ex: division by zero
• interrupts
  • asynchronous signal to the processor that some external event occured and needs attention
  • how it works = processor detects interrupt, suspend user program, switch to kernel stack, identify interrupt type, invoke appropriate interrupt handler, restore user program
  • ex: keyboard press!
• kernel→user
  • new process creation like data structure init or setting registers
  • resuming after exception, interrupt, or syscall
  • switching to a diff process like loading new process state

lec 3: processes cont.

stack review

• stack = grows down, contains temp data like methods/function parameters, return address, local vars
• heap = grows up, dynamically allocated memory
• stack frame = all info on the stack pertaining to a function call

pointers

• frame pointer (%ebp) = base address of function’s frame
• stack pointer (%esp) = points to the next item on the stack
• instruction pointer (%eip) = current address of the program being executed
• ebx, eax, edx are all general registers for temporary data storage

• it always goes:
  • frame pointer (ebp), have stack pointer (esp) pointing at the ebp,
  • then create space for x =
  • then load parameters in reverse order
  • then instruction pointer eip gets added to the stack and jumps to the BAR location from “call bar”

• then jump stack pointer to the new frame pointer ebp for add
  • do add operation with 12(%ebp) and 8(%ebp)
  • store the result below ebp on the stack (move to eax register)
• begin popping local vars of the stack and restore control to EIP (instruction pointer)

big idea

• state of the programs execution is succinctly and completely represented by CPU register state: eip, esp, ebp, eflags/psw

user → kernel mode

• malicious user program (or IO device) cannot corrupt the kernel
• interrupts, exceptions, or system calls handled similarly → fewer code paths, fewer bugs
• reqs:
  1. limited entry = cannot jump to arbitrary code in kernel
  2. atomic switch = switch from process stack to kernel stack
  3. transparent execution = restore prior state to continue program

1. interrupt detection (hardware)

1. device sends electric signal over interrupt request line (IRQ) to interrupt controller
2. APIC converts IRQ to a vector number and sends signal to processor
3. processor detects interrupt by the IRQ code

2. save recovery state (hardware)

• save register values for process recovery
  • stack pointer esp
  • program counter eip
  • execution flags/program status word eflags

3. switching atomically to kernel stack

• switches stack pointer to base of kernel stack, pushes recovery state onto the new stack (+ optional error code)
  • hardware needs to save registers before switching to kernel stack bcuz it overrides the stack pointer/eip when switching
  • use a separate kernel stack for integrity and privacy

4. invoke interrupt handle (hardware)

• interrupt vector is an index into the Interrupt Vector Table
• index contains appropriate Interrupt Handler Routine
• handler saves all remaining user registers into stack and implements logic
• PURPOSE = ensures that we only start executing kernel code at predefined entry points

5. return to program

• pop all user regs from kernel stack
• invoke iret instruction to pop saved EIP, EFLAGS, and SP regs from kernel’s exception stack to relevant registers
• return to user mode

INTERRUPT SUMMARY

1. device sends signal to APIC
2. processor detects interrupt
3. save recovery state and switch to kernel stack
4. jump to interrupt handler table at appropriate vector and invoke interrupt handler
5. restore user program

*syscalls are handled VERY similarly!

• issue a “trap” instruction (int 0x80)
• differences for syscalls (AND exceptions!)
  1. extra layer of indirection (syscall table)
  2. leverage registers for parameters/values
  3. when executing iret, increment EIP by one to go to next instruction
  4. usually interrupts not disabled

lec 4: systems programming processes and communication

• processes in Linux form a family tree, with parents and many children starting from init

process management API

• exit = terminate a process
• fork = copy the current process
  • creates a new child process (copy) from an original parent process
  • copies address space, code/data segments, registers (including PC+SP), stack, pointers to files/IO
    • uses copy-on-write, so generally fast bcuz the OS doesn’t have to copy the entire address space!
  • all processes WILL finish even if the main terminates! separate processes
  • how to do_fork():
    1. allocate a new PCB (process control block)
    2. duplicate
    3. allocate new PID (process id)
    4. mark process as the READY state (start instruction pointer at the same fork() instruction in the child process)
  • fork >0 success, <0 error, =0 child process!
    • fork() returns PID of child to parent, if 0 then we know its a child

  fork()

  1. fork() invokes int 0x80 instruction - syscall
  2. CPU switches to kernel stack and copies recovery state
  3. CPU jumps to interrupt vector table (index 128) and invokes system_call_handler()
  4. handler identifies fork() using syscall dispatch table, where syscall number is stored in %eax reg
  5. do_fork() creates a new child PCB with duplicated memory context and same EIP
  6. schedule either child or parent process
• exec = change the program being run by the current proccess
  • useful to copy entire memory of process but can be pretty fast bcuz of copy-on-write mechanisms
  • interleaved with fork
  • open FDs are preserved across the exec syscall
    1. replace the code and data segment
    2. set EIP to point to start of new program reinitialize SP and FP
    3. push arguments to program onto stack

• wait = wait blocks parent process until one of its children processes exits
  • pid_t waitpid(pid_t pid, int *status, int options);
• kill = send a signal (interrupt-like notif) to another process
  • each signal has a default action that can override with signal handler
    • program jumps to signal handler function and program resumes after
  • ex: kernel → user mode transition
    1. aims to make process aware that specific event has occurred
    2. allow process to execute a signal handler function when event has occurred
• sigaction = set handlers for signals

Input/Output in Linux

• UNIX has the same IO interface for everything! → all files!!!
  • devices (printers, mouse), read/write files (disk), interprocess communication (pipes, sockets) = all the same!
  • user processes can interact with IO devices as if they are files!
  • read and write to pipe using syscalls
  • HOWEVER…
    • not everything stored on the disk is part of a file (such as boot loader and free map in pintOS)
    • kernel data structures CAN be stored as memory

core tenants of the unix/IO interface

• uniformity = same set of system calls (open, create, read, write, close)
  • open = enforces file permission bits
  • read = the first argument is usually not 1 (usually stdin is fd=1 and you usually don’t want to call read on that)
  • write = takes an int, a pointer, and size_t
  • lseek = used to reposition the file offset
  • close = closes a file
  • dup2 = duplicates a file descriptor
• open before use = must explicitly open file/device/channel
• byte-oriented = all devices, even block devices, are access through byte arrays
• kernel buffered reads/writes = data is buffered at kernel to decouple internals from application
• explicit close = must explicitly close resource after using it

file descriptor

• number that uniquely identifies an open IO resource in the OS (an index!)
  • stored in a file descriptor table! each process has a unique FD table and unique address space
  • if you FORK, the forked process inherits the FD table!!!!!
  • ALSO if you fork, its not like child and parents – all the processes are independent and will finish!
  • you can have multiple FDs→1 file, but not multiple files to 1 FD
• FD table stores…
  • file offset, file access mode and status flags from open(), reference to physical location (inode), and # of times opened
• open/create = all files explicitly opened via open or create (returns lowest numbered file descriptor not yet assigned and creates new FD)
  • open() will always start at the 0 index of the file!!!!!!!
• close = closes FD and allows that num to be reused with a diff file
  • close() does not wait for the buffer if we are also using fwrite/fclose

• read = reads data from open file using file descriptor, returns ssize_t
• write = writes data and returns ssize_t
• lseek = reposition file offset within kernel, returns off_t

lec 5: threads and the thread API

OS library

1. improved programming API = minimizes glue code and simulates additional functionality
2. performance = minimizes cost of syscalls

FDs to files

• FILE* = OS library wrapper for manipulating explicit files
  • contains FD, buffer array, lock
  • operates on streams (unformatted sequences of bytes)
• fputc, fputs, fgetc, fread, fwrite, fprintf, fscanf
  • these commands can make the program show up in a higher priority on the queue since they are part of the thread API
    • only in MLFQS
    • makes the program run faster!
• buffered IO (passes through an intermediate and then passes onto OS when enough data has accumulated to reduce file system calls)
  • maintains a per-file user-level buffer
  • Write Calls write to buffer and flushes buffer to disk when full (or on special char)
    • this makes it so that there’s many smaller writes and then passes to the disk when it has enough accumulated)
  • Read Calls read from buffer and reads from disk when the buffer is empty
    • the read call waits until the buffer is completely flushed before reading
  • operations on file descriptors are unbuffered and visible immediately

benefits of API

• syscalls are 25x more expensive than FILE* calls
• buffering is the key to supporting diff FILE IO APIs (additional functionality!)
  • decouples the rate at which the application writes from the speed at which the file system writes (so the user can write to the user level buffer without worrying about the speed of the underlying hardware)
• kernel always reads fixed size block from disk
  • buffers into user space
• parses buffer to read and write chars/blocks/lines
  • allows user to write individual chars or lines

buffering

OS concurrency/parallelism

• efficiently manage…
  • many different processes
  • concurrent interrupts
  • network interfaces
• must provide programmers with abstractions for expressing and managing concurrency

threads

• single execution sequence that represents a task, runs on a dedicated virtual processor with sequential code
• processes AND threads have a lifecycle:
  • new, ready, running, waiting, terminated
• needed for…
  • natural program structure = simultaneously update screen, fetch new data from network, receive keyboard input
  • exploiting parallelism = split unit of work into n tasks and process tasks in parallel on multiple cores
  • responsiveness = high priority work should not be delayed by low priority work, you can schedule as separate threads for independence
  • masking IO latency = continue to do useful work on separate threads while blocked on IO (latency = delay before transfer of data)
• threads are not the same as processes!
  • processes = granularity of isolation and protection for OS, consists of 1+ threads!
  • threads = concurrent sequences of computation, contained in processes
• threads inside of the same process are not isolated
  • they share an address space and IO state (FDs)
    • meaning they can modify stack variables of another thread in the same process!
  • they execute disjoint instruction streams tho, so they have an individual stack, register state, etc

user threads vs kernel threads

• user threads
  • one PCB (process control block) for the process
    • process control block = status, register state, process ID, execution time, memory space, translation
  • each thread has own TCB (thread control block) stored in heap of process
    • registers are saved in kernel memory
    • the page table base register would be set to point to the second process’s page tables during a context switch
      • the kernel rounds down %esp to the nearest page, so the struct thread is at the bottom of the page that the corresponding kernel stack is on
    • file descriptor table is in memory
    • buffered data is NOT flushed during a context switch
  • threads in user-space only, invisible to kernel
  • lower overhead compared to kernel-level threads
• kernel threads
  • essentially kernels know about all the threads happening so they can schedule all of them however they want
  • each thread has own TCB, scheduled individually, and needs mode switch to switch threads
  • PCBs of threads mapped in the same process all share the same process share address space, files, code/data
    • but they have their own stack and registers

pthreads

• pthread_create = creates and runs new thread
• pthread_join = suspends execution of calling thread until target thread terminates
  • generally you can use this at the end because it will ALWAYS WAIT until the threads finish running before joining!
  • you have to run this on all ur threads tho (like for loop or smthg)
• pthread_yield = causes thread to yield the CPU to other threads
• pthread_exit = terminates thread and makes value_ptr available to any successful join
  • typically this results in DATA LOSS

threads vs processes

• threads are useful in a process in sockets!
• you can basically accept a socket and then create a thread with that socket, without worrying about closing the socket each time
  • then at the end you can close it once
  • this is much easier than the previous process bcuz ur not copying them anywhere

pthread_create()

summary

• protection is at the process level → threads are not isolated
  • threads share an address space and are nondeterministic
  • RACE CONDITION :’)

lec 6: synchronization - concurrency and mutual exclusion

sockets vs pipes

• SOCKET = 2 way, PIPE = 1 way
  • pipe = between processes on the same machine
  • socket = between different OR same machine
• establishing a pipe
  • call pipe syscall, then fork, then close one end of the pipe in the parent process and close other end in child process

interprocess communication: pipes

• pipe implements a queue abstraction
  • implemented as a kernel buffer with two file descriptors, with one for writing to pipe and one for reading
  • block the queue if the pipe is full OR empty
• after the last “write” descriptor is closed, we close the pipe
• reads return “EOF”
  • after the last “read” descriptor is closed, writes generate SIGPIPE signals which signals a broken pipe and ends the process
    • sigpipe = when you try to output to a socket that isn’t connected
  • if the process ignores, then the write fails with EPIPE error

IPC across machines: sockets

• sockets are an abstraction of 2 queues that can read or write in either direction to different machines
• example: client and server, like connecting to eecs.berkeley.edu or our VM from the instructional accounts

socket functions

• socket() = creates the socket
• bind() = bind the socket to an address
• listen() = listen for connections
• accept() = server accepts a new connection (usually blocks until a client connects)
  • efficient solution would be to create new threads for each new client instead of blocking the new clients while handling the current request
• connect() = used by the client to connect to a server!
• send() = send and receive data with send() and receive()

connection setup over TCP/IP (Transmission Control Protocol)

• identify connections with a 5-tuple:
  1. Source IP Address
  2. Destination IP Address
  3. Source Port Number
  4. Destination Port Number
  5. Protocol (always TCP here)

dispatch loop

1. RunThread();
   • load state into cpu, load environment, jump to PC
2. ChooseNextThread();
3. SaveStateOfCPU(curTCB);
4. LoadStateOfCPU(newTCB);

internal events

• blocking on IO = the act of requesting IO implicitly yields the CPU
• waiting on a signal from other threads
• thread executes a yield = thread gives CPU to another thread voluntarily

external events

• what happens if thread never does any IO, never waits, and never yields control?
  • we must find a way for dispatcher to regain control
• interrupts and timers

User Level Threading

• threadfork() = user-level thread create
  • takes in fcnPtr, fcnArgPtr[], size of stack to alloc)
• TCB initialize
  • initialize register fields, stack pointer points at stack, PC return address at ThreadRoot(), a0 and a1 are registered to fcnPtr and fcnArgPtr
• stack initialize
  • minimal - x86 needs to push a return address on stack, nothing else
  • grows down with execution of thread

multiprocessing vs multiprogramming

• Multiprocessing = Multiple CPUs
• Multiprogramming = Multiple Jobs or Processes
• Multithreading = Multiple threads per Process

concurrent threads

• independent threads
  • no state is shared with other threads
  • deterministic AND reproducible
• cooperating threads
  • shared state between multiple threads, nondet and nonrep :(
• advantages of cooperating threads:
  1. share resources
  2. speedup cuz overlapping IO, computation, and multiprocessors (parallel)
  3. modularity - chop up larger problem into simpler pieces
• disadvantages = sensitive to data, interleaving, shared vars can become inconsistent

lec 7: synchronization - concurrency, locks, atomic instructions

timer

• thread_tick = updates thread counters, if quanta exhausted we set yield flag
• thread_yield = on path to return from interrupt, sets current thread back to READY, pushes back onto ready_list, selects next thread (upon iret)
• schedule = selects next thread to run and sets status to RUNNING, if user thread it activates the process, then returns to intr_handler

threads

• yields overlapped IO and computation without deconstructing code into non-blocking fragments
• requests proceeds to completion, blocking as required (shared state can get corrupted)

atomic operations

• an operation that always runs to completion or not at all (NOT DIVISIBLE!)
• fundamental building block = if no atomic oeprations, then no way for threads to work together
• most instructions aren’t atomic (like ++ and —), but memory loads/stores are atomic

definitions

• synchronization
  • using atomic operations to ensure cooperation betw threads
  • only load/store is atomic
• mutual exclusion
  • only one thread can do a particular thing at a time
• critical section
  • piece of code that only one thread can execute at one time
  • causes busy-waiting if the CPU has to wait too long
• lock
  • used to protect the critical section
  • acquire at the beginning, release at the end
  • alloc: structure Lock lock or pthread_mutex_t lock
  • init: lock_init(&lock) or lock = PTHREAD_MUTEX_INITIALIZE
• why do we disable interrupts
  • to avoid interruption between checking and setting the lock value
  • the hardware timer usually generates non-maskable interrupts (not ignored)
  • disadvantages:
    • does not help prevent multiple processors from accessing the same critical section
    • critical events might be missed since interrupts are disabled
    • user programs don’t have the ability to disable interrupts
• locks can be implemented using atomic operations
  • test&set or compare&swap
  • this means that we do not need trapping into the kernel

lec 8: synchronization - locks, semaphores

atomic operations

• problem was you can’t give lock implementation to users AND doesn’t work well on multiprocessor
• solution! → atomic instruction sequences
  • read a value and write a new value atomically
  • hardware can do this on uni and multiprocessors
  • use compare&swap(&address, reg1, reg2)

futex aka fast user-space mutex

• int futex(int *uaddr, int futex_op, int val, const struct timespec *timeout );
• interface to the kernel sleep functionality, includes wait and wake conditionally

semaphores

• generalized lock, non-negative integer value
• down() (P) or up() (V) the semaphore to synch
• initial value = 1
  • “mutual exclusion” or “binary semaphore” or “mutex”
  • used like a lock!
  • OR use as a capacity blocker aka sema_init(10000) like game_capacity
• initial value = 0
  • “scheduling constraints”
  • allows thread 1 to wait for a signal from thread 2
  • so “start” ups the semaphore, “finish” downs the semaphore
• use a separate semaphore for each constraint you have!
  • consumer waits for producer to fill buffers (SCHECO), producer waits for consumers to empty buffers (SCHECO), one thread can manipulate buffer queue at once (MUTEX)

lec 9: synchronization - semaphores, monitors, read/writers

• use locks for MUTEX and condition variables for managing concurrent access to shared data
• monitor = a lock and zero or more condition variables for managing concurrent access to shared data
  • condition variable = queue of threads waiting for something INSIDE a critical section
  • allows sleeping inside the critical section by atomically releasing lock at the time we go to sleep
  • wait(&lock) = atomically release lock and go to sleep, re-acquire lock later before returning
  • signal() = wake up one waiter if any
  • broadcast() = wake up ALL waiters
  • RULE: must hold lock when doing condition variable operations!
• hoare monitors
  • signaler gives up lock, CPU to waiter, waiter runs immediately
  • then waiter gives up lock, processor back to signaler when it either exits critical section OR waits again
• mesa monitors
  • signaler keeps lock and processor
  • waiter/thread placed on ready queue (no priority)
  • practically, we need to check the condition again after the wait
    • use WHILE (isEmpty(&queue)) { … } instead of an if statement
• DIFFERENCE
  • HOARE = signaling thread immediately transfers lock and control of the CPU to the waiting thread
  • MESA = waiting thread will be woken up after being signaled, and may be scheduled to run at a later time

example of monitor (lock AND sem) implementation

• uses broadcast cuz if someone arrived second that is going in the right direction, we want them to know they can go

Reader/Writers problem

• if we want many readers and only one writer at one time

• readers signal() to wake up just ONE writer
• writers broadcast() to wake up ALL readers

monitors from semaphores

• with mesa, this is possible!
• wait if necessary and then signal when something changes so waiting threads can proceed
• make sure to release the lock on an exception/error!

extras

scheduling algorithms

• MLFQS = multilevel feedback queue scheduling
  • processes are permanently assigned to the queue and cannot move
  • low scheduling overhead but not flexible, depends on priority
  • causes starvation cuz high priority queues can remain there indefinitely
• FCFS = first come first serve
  • maximizes throughput vs SRTF since fewer context switches
  • may cause starvation due to potential threads running indefinitely