1/108
Looks like no tags are added yet.
Two roles of an operating system
Facilitator: abstractions, resource accesss
Cop: protection, control
Preeemption
Take resources away from a long running process
Memory protection
Prevent one process from accessing another’s memory
Privileged and unprivileged modes
Applications run in unprivileged mode
OS runs in privileged mode
Process
A running instance of a program
Each process has its own:
Address space
File descriptors
Virtual CPU
Virtual CPU
A single process essentially thinks it has dedicated access to its own CPU
Different process ___ the same virtual addresses
can use
How to improve performance without multiple cores
Increase CPU utilization
Reduce latency
Execution environment
The context and runtime infrastructure provided by the OS in which a process executes
Return values of fork()
PID of new process in the parent
0 in the child
-1 on error
fork()
Creates a new process that is almost an exact copy of the current one
A process and a forked child process have ___ address spaces
different address spaces, but of the same size and contents
exit(status)
Causes normal termination of the current process, either implicitly or explicitly
waitpid(pid, *wstatus, options)
Blocks the parent process until the child process terminates
fork() vs spawn()
fork() has a simple interface and allows you to do whatever you want with the child process
spawn() combines fork() and execv() into a single function, which is a common pattern
Process Control Block
A struct of process and state information:
State of the process
Information necessary to run: registers, virtual memory mappings, open files
Other relevant data about the process
States of a process
New and terminated
Running
Ready
Waiting

Ready state
Process can run, and is waiting to be ran by the kernel
Waiting state
Requires an async event (e.g. disk operation) to proceed
Yield
A process voluntarily gives up resources
Context switch
Changing the process running on a CPU
Causes of context switching
Blocks waiting for an event
Voluntary yields
Exits
Preemption
Common causes of preemption
Timer interrupts updates CPU time
I/O-completion interrupt
Ways the kernel gets control
System calls
Exceptions
Interrupts
System call
An interface to allow a user-level application to request a service from the operating system
Exception
Current instruction causes an exceptional condition: page fault, illegal instruction, etc.
Interrupt
External event generated asynchronously by hardware: periodic timer expiration, I/O completion
Thread
A schedulable execution context within a process
Threads within the same process share:
Address space
Open files and other process resources
A thread has its own:
CPU register values, including the PC
Stack
Benefits of using threads
Lightweight abstraction for concurrency
Allow one process to use multiple CPUs or cores
Allow a program to overlap I/O and computation
Critical section
A part of a concurrent program in which a shared object is accessed
Race condition
When the outcome of execution depends on the particular order in which access takes place
Mutual exclusion
The guarantee that at most one thread is executing within the critical section at any given time
Progress
If no thread is on the critical section and threads are trying to enter, then one will eventually enter
Bounded waiting
Once a thread T requests entry, there is a bound to how many other threads can enter before T does
Progress vs. bounded waiting
If threads are trying to enter but none can, progress fails
If thread A waits while B repeatedly leaves and re-enters forever, bounded waiting fails
Sequential consistency
The result of execution is as if all operations were executed in the same sequential order, in the order specified by the program
Requirements of sequential consistency
Maintaining program order on individual processors
Ensuring write atomicity
Which process should the kernel run in a single CPU system?
If 0 runnable, run idle loop (or halt CPU)
If 1 runnable, run it
If >1 runnable, must make a scheduling decision
T/F: fork() returns once
False: fork() is called once, but returns twice
Concurrency vs. multithreading
Concurrency is a general concept about managing multiple tasks so they can make progress over overlapping time periods
Multithreading is a technique to achieve concurrency by creating multiple execution paths (threads) within a single process
File descriptor
A small non-negative integer that a process uses to refer to an open file or I/O resources
FD system calls
open() which opens a file and returns an FD
read(fd, …) locates the resource associated with the FD and copies it over
write(fd, …) locates the resource associated with the FD and writes to it
close(fd) removes the lookup layers and releases the resource associated with the FD
Steps of a process-to-process context switch
Save the CPU state needed to resume the current process
Change the current process’ state from running to ready, waiting, or terminated
Run the scheduler to select a ready process
Change the selected process’ state from ready to running
Switch to the selected process’ userspace address space
Switch to the selected process’ kernel stack
Restore the CPU state previously saved for the selected process
Library OS
A library of standard services with no protection
Benefits of a Library OS
Able to simplify assumptions such that the system runs one program at a time, and there are no bad users or programs
Drawbacks of a Library OS
Poor utilization of hardware and human user (must wait for each program to finish)
Multi-user OS
Use protection to serve distrustful users and apps
What is required in a Multi-user OS
Need policies for how much CPU a single user can use
Total memory usage might be greater than what is in the machine
Super-linear slowdown with increasing demand
What is an operating system?
A layer between applications and hardware
Hardware can be made useful to the programmer
Provides abstractions for applications (usually)
Interposition/mediation
The OS is placed between an application and other resources
Track everything that specific application is allowed to access
On every access, look in the table to check if that access is legal
Typical OS structure
Most software runs as user-level processes
The OS kernel runs in privileged mode
Creates/delete processes
Provides access to hardware
Kernel
The part of the OS that responds to system calls, interrupts, and exceptions
System calls
Special instructions which transfer control to the kernel
Zombie
A terminate child whose parent has not collected its exit status using waitpid()
Orphan
A child process whose parent has terminated before calling waitpid() on the child
What happens when a parent terminates without calling waitpid()?
If the child dies first: the child process becomes a zombie
If the parent dies first: the child process becomes an orphan
It is reparented and then reaped (remaining resources are freed)
Kernel entry steps
Enter the kernel
Elevate access
Turn off interrupts
Save state
Jump to kernel entry point
If entering from user mode, switch to process’ kernel stack
Save execution state
Determine cause and dispatch handler
Re-enable interrupts when appropriate
Kernel stack
A protected stack for its own function calls, local variables, and saved state
Application stack
A process’ (or thread’s) stack in user address space
Trap frame
Pushed onto the kernel stack when a trap (system call, exception, interrupt) occurs
Saves the process’ program counter and register values
Used to return from the handler
T/F: The kernel may modify the trap frame before returning
True: to modify return values
Which is typically larger: a trap frame or switch frame
The trap frame as it must save enough state to resume the interrupted execution
Switch frame
Pushed onto the kernel stack when the kernel switches processes
Does not need to save caller-saved registers
Used when the process is scheduled again
Steps of a system call
Process invokes a system call, eg. close()
Enter the kernel
The process’ trap frame is pushed onto the kernel stack
Call mips_trap() to determine whether caused by exception, interrupt, or system call
Call sys_call() to determine which system call to dispatch
Dispatch the system call sys_close()
Store the return value in the trap frame
Return to the current process
Creating a new thread with pthread_create()
Creates a new thread in the current process
Returns 0 on success
Error on failure
Terminating a thread with pthread_exit()
Terminates the calling thread
Does not return
Joining a thread with pthread_join()
Waits for a given thread to terminate
Returns 0 on success
Error on failure
What happens when a thread exits?
Its execution context and resources are given up
Kernel-level thread
An execution context represented and managed by the kernel
Thread control block (TCB)
Contains thread-specific information needed by the kernel to manage the kernel-level thread
T/F: A kernel-level thread only executes within a kernel
False: it can execute user code and enter the kernel when needed
User-level thread
When a kernel-level thread runs in userspace, a userspace library/runtime can create additional execution contexts
Benefits of user-level threads
Switching between user-level threads can happen entirely in userspace
Do not require entering the kernel
Can be much lighter-weight
T/F: Every kernel-level thread is a system call
True
1:1 thread configuration
Each thread maps to a unique kernel-level thread
High overhead
A blocking system call allows other threads to still run
N:1 thread configuration
N user-level threads map to the same kernel-level thread
Lower overhead
A blocking system call will block all threads mapped to the same kernel-level thread
N:M thread configuration
N user-level threads are mapped to M kernel-level threads
Lower overhead than 1:1, but higher than N:1
A blocking system call will block the calling thread, but does not prevent other threads from running
Lost wakeup problem
A signal is sent just before or during the moment that a waiter goes to sleep, and so the signal is lost: the waiter sleeps forever
Hand-over-hand locking
lock(m1)
lock(m2)
…
unlock(m1)
unlock(m2)
Deadlocks
When two or more threads wait on each other and no progress can be made
Necessary conditions for deadlock
Mutual exclusion
Hold and wait
No preemption
Circular wait
T/F: If a resource-acquisition graph has a cycle, then there is a deadlock
False: only converse is true
Lock ordering
Prevent deadlock with a partial order on resources: eg. always acquire mutex m1 before m2
Course-grained vs. fine-grained locking
Course-grained locking is simple, and serializes independent operations
Fine-grained locking allow for more concurrency
More overhead and complexity involved
Why does the kernel increment the program counter by 4 when handling an exception?
So that the process does not re-run the instruction that caused the exception
Spurious wakeup
A thread woken up randomly by the OS
File-descriptor table
Owned by an individual process
Entries point to entries in the system-wide open-file table
T/F: two different process’ file descriptors can point to the same entry in the system-wide open-file table
True
Pipe
A memory buffer in the kernel
T/F: Piped processes are run sequentially
False: both processes must exist before using a pipe
Memory and I/O buses
CPU accesses physical memory over a memory bus
Methods of accessing devices
Explicit I/O instructions
Memory-mapped I/O
Explicit I/O instructions
There are explicit instructions to read and update data
Memory-mapped I/O
Each device register has a physical memory address; use loads and stores to read and update data
Device Driver
The part of the kernel that interacts with a device
Polling
The kernel driver repeatedly checks device status
Direct Memory Access
The CPU initiates the transfer, and the device moves the data and notifies the CPU when finished