Exam 1 Review

Question 1

What is a Virtual Machine (VM)?

Answer 1

• A software system that allows an operating system to run as an
application in user-space
• Allows us to run multiple operating systems on a single computer

Question 2

Why Do We Use Virtual Machines?

Answer 2

• Running Windows/Linux on the same machine
• Sandboxing for testing
• Cloud computing

Question 3

Advantages So Far with Online IDEs

Answer 3

• Online IDEs are great for learning how to code
• Provides a standardized coding environment
• Little configuration / installation required – it just works!

Question 4

Why VM-Based Development Now?

Answer 4

Development in a more realistic environment
• Running on your local computer
• Logging into a virtual machine that runs Linux C similar to how system
administrators log into a server machine or cloud VM
• Build an application running on an actual operating system that you installed!
• Write C programs that interact with your operating systems using system calls

Question 5

What is an Operating System?

Answer 5

Operating systems provide an interface between hardware and user
programs, and makes hardware usable

Question 6

OS Functions

Answer 6

Extended machine providing abstraction of the hardware
• Hides the messy details which must be performed

It is a resource manager
• Time on CPU is shared among multiple users/programs
• Space in memory and on disks is shared among multiple users/programs

Question 7

What’s a Process?

Answer 7

A “program in execution”
• With associated (data and execution) context
• Process execution must progress in sequential fashion

NOT the same as “program” or “application”
• A given program may be running 0, 1, or >1 times

Each instance of a program is a separate process
• With its own address space and context

Question 8

Why Run Processes?

Answer 8

An operating system executes a variety of programs
• Batch systems – job
• Time-shared systems: user programs or tasks

Many processes can run concurrently
• Singer-user system: several programs (word processor, browser, email)
running at the same time
• OS internal programmed activities (ex: memory management)

Question 9

Process Creation in a Nutshell

Answer 9

• Parent processes create child processes, which in turn create other
processes, forming a tree of processes
• Generally processes are identified and managed via a process
identifier (PID)

Resource sharing
• Parent and children have separate virtual address space
• Parent and child shared some resources (e.g. open file descriptors, semaphores)

Question 10

Process Hierarchy

Answer 10

Init process
SSH server
User shell
Firefox/Emax

Init process
System processes

Question 11

First System Call: fork()

Answer 11

Both parent and child run concurrently after fork()

Linux does copy-on-write to reduce fork() overhead

Question 12

Second System Call: exec()

Answer 12

• exec() loads in a new binary for execution

* PC, SP, and memory (stack, heap, data) are all reset to run new program

Question 13

Third and Fourth System Calls: wait() and exit()

Answer 13

exit(status) – executed by a child process when it wants to terminate
• Makes status (an integer) available to parent
• Zero exit status means command exited without errors
• Non-zero exit status indicates errors

Question 14

Process Termination

Answer 14

Graceful termination via exit

Non-graceful termination when process is killed
• kill(pid, sig) – sends signal sig to process with process-id pid
• Ex: SIGKILL signal to terminate target process immediately
• Can be done from C code or from Shell
• A process can kill another process only if both processes belong to the
same user and if the “killer process” is owned by a super user

When a process terminates, resouces are reclaimed by system:
• PCB, memory, files

Question 15

What is a Process’s ”Context”?

Answer 15

Contents of the PCB

Execution Context
• Stack pointer
• Program counter
• Compute register values
• Segment register values
• Status (running, blocked, ready)

Memory Context
• Pointer to page table

Question 16

Context Switch: P1 to P2 (running)

Answer 16

Steps:

1. P1 stops running
2. CPU - kernel mode
3. OS starts running
4. OS copies CPU register values to P1’s PCB
5. OS scheduler decides P2 should run next
6. OS loads P2’s PCB values into CPU
7. OS - user mode
8. P2 starts running

Context Switching has Overhead
• Transition from user to kernel mode
• Copying contents to and from PCBs
• Potential memory and CPU cache misses when running another
process
• A well-designed OS should:
• Balance carefully fairness and context-switching overheads
• Minimize time spent in OS by running efficiently

Question 17

Life of a Process

Answer 17

Process Created
Ready
Running
Terminated/Blocked

Question 18

When Does Context Switching Occur?

Answer 18

• (1) Currently running process makes a system call and is blocked
• Process is put on the blocked queue
• Scheduler picks up another process in ready queue to run
• (2) Currently running process terminates
• Scheduler picks up another process in ready queue to run
• (3) Hardware or software interrupt happens
• OS handles the interrupt and blocked processes may become ready
• Scheduler may choose to continue running current process of pick another process to run
• (4) Current process used up its current “time slice”
• Scheduler picks up another process in ready queue to run

Question 19

Typical Scheduler Heuristics

Answer 19

Each process runs for a fixed time slice (typically 100 msec)
• Response times vs throughput tradeoffs

Some processes have higher priority over others:
• Interactive applications that block frequently because of system calls
• User-defined priority (using “nice” command in Linux or task manager in
Windows)
• System daemons
• User has a higher priority over other users using the computer

Question 20

State Transitions for fork and exec

Answer 20

fork()
• Clones the child process
• Both parent and child become ready
immediately

exec()
• Open file, load (or map) contents to
memory, reset context
• Process goes to ready state as soon
as this happens
• Might block if opening or loading
the file takes a while

Question 21

Quick Primer on I/O System Calls

Answer 21

Input and output (I/O) – any interactions between computer and external devices, such as keyboard, mouse, disks, printers, and monitors.

In Linux, all input and output (I/O) is done by writing to files as sequences of bytes

Each I/O device is uniquely identified by a file descriptor:
• STDIN – keyboard
• STDOUT – display on screen
• Other file descriptors: open files, network sockets

Question 22

Example I/O System Calls

Answer 22

Functionally equivalent calls
scanf(“%s”, buf)
fscanf(STDIN_FILENO, “%s”, buf)
read(STDIN_FILENO, buf, …)

System calls documented in section 2 and 3 of Man pages
• Type “man 2 read” or “man 3 fread” for examples

read() attempts to read up to count bytes from file descriptor fd
into the buffer starting at buf.

   On files that support seeking, the read operation commences at
   the file offset, and the file offset is incremented by the number
   of bytes read.  If the file offset is at or past the end of file,
   no bytes are read, and read() returns zero.

   ssize_t read(int fd, void *buf, size_t count);

The function fread() reads nmemb items of data, each size bytes
long, from the stream pointed to by stream, storing them at the
location given by ptr.

   The function fwrite() writes nmemb items of data, each size bytes
   long, to the stream pointed to by stream, obtaining them from the
   location given by ptr.

      size_t fread(void *restrict ptr, size_t size, size_t nmemb,
                    FILE *restrict stream);
       size_t fwrite(const void *restrict ptr, size_t size, size_t nmemb,
                    FILE *restrict stream);

Question 23

State Transitions for I/O System Calls

Answer 23

read()
• If error, put process in ready state
• If input is available, put process in ready state
• If no input is available, put process in blocked state

write()
• If error, put process in ready state
• If I/O channel is not available, put process in blocked state, otherwise put process in ready state

Question 24

Invoking a System Call

Answer 24

The code for the “function” is in the OS
• Operates in kernel mode
• Different address space
• Context switching required!

Limited number of entry points (“functions”)
• A user process can’t just jump to anywhere it likes in the OS

A system call might not return right away
• Process’ state might change to blocked as a result of the system call’s
actions
• OS might decide to schedule a different program

Question 25

TRAP Instructions

Answer 25

Step 1: CPU mode
changes from user to
kernel (supervisor)

Step 2: OS pops off register values
storing program’s current execution
context and stores in the PC

Step 3: OS pops off syscall# printf
and parameters

Step 4: Calls appropriate function in
kernel via dispatcher

Step 5: Push return value for printf
onto stack

Step 6: OS scheduler decides which
process to run next (could be P1 or
another process)

Step 7: OS sets mode back to user
from kernel mode

Step 8: Reload registers from PCB
of process to run

Step 9: Run next instruction after
system call

Question 26

System Calls are More Expensive

Answer 26

Going between user and kernel mode is more expensive
• Have to save current process state
• Have to restart state when done
• More expensive than a function call

Restarting a different process can be even more expensive
• Have to load a different address space
• Likely to destroy caches and virtual memory

Question 27

Interrupts

Answer 27

System calls are
initiated by user
programs

Interrupts are
the opposite
Hardware
interrupt
External
devices
When interrupts happen:
1. Stop running user
program
2. Trap to kernel
3. Run interrupt handler
4. Go back to user mode

Question 28

Examples of Hardware Interrupts

Answer 28

Clock Pulse
• Causes OS to re-invoke the scheduler to run another process
• Example: every 100 msec
• Update system time

Input (from keyboard, network, disk)
• Change that process from blocked to ready
• Re-invoke scheduler

Illegal Instruction
• Send signal to (or terminate) process that issued instruction

Question 29

Interrupts vs System Calls

Answer 29

Interrupts are similar to TRAP instructions, except they are triggered by
hardware, not initiated by the currently running process

An interrupt might occur at almost any point in a running process
• The process isn’t expecting it, and so it isn’t saving its parameters, etc.
• “returning” from an interrupt means restarting at the point of last
interruption

System calls have return values but not interrupts

Question 30

Interrupts Steps

Answer 30

Step 1: P1 is happily running
Step 2: Interrupt happens.
CPU transitions to kernel mode
Step 3: Interrupt signal is
processed by OS’s Interrupt
Service Routine (ISR)
Step 4: ISR saves P1’s state in PCB
Step 5: ISR identifies right device
driver to call using interrupt ID

Upon completion
• OS calls scheduler to select a process in ready queue to run
• May be the original one, may be something else

OS sets CPU mode bit back to user
• And reloads state registers (PC, etc.) for process selected to run next

Now we’re back in a user space running the process
• Current instruction is whatever it was last doing before context switched

Process gets on with its business
• No need to pop any return value, since process doesn’t know interrupt
occurred

Question 31

Terminology: Signal

Answer 31

• Asynchronous software notification to a process of an event
• “Software Interrupt” but can only be initiated by another process, not
necessarily by the OS
• Simplest form of inter-process communication
• Each signal has a symbolic name
• Starts with SIG*
• Defined in signals.h

Question 32

Terminology: Signal Handler

Answer 32

• Used by the process that receives the signal to handle the signal
• May overwrite default action

Question 33

Are Signal-Handlers Pre-Emptible?

Answer 33

It depends!

For the same signal type, signals are usually processed one at a time
per thread.
• E.g. if Ctrl-C is handled, other Ctrl-C signals are blocked on the same
thread.
• Not guaranteed, they may be merged

For different types, they can be preempted
• E.g. a SIGKILL in the middle of a SIGINT handler

To avoid preemption, use signal blocking in handler

Question 34

Advanced Signal Handling

Answer 34

• sigaction(…)
• Similar to signal(…) but offers more control at the expense of more complexity
• act
• Pointer to sigaction struct about action to be taken
• oact
• Pointer to previous action associated with signal

int sigaction(int sig, const struct sigaction *restrict act,
struct sigaction *restrict oact);

Question 35

User Level Threads

Answer 35

Thread management done
by user-level threads library
entirely in user mode.
As far as the OS is
concerned, it is a “singlethreaded”
process
(old) Examples:
POSIX Pthread
Java Threads

Question 36

Kernel Level Threads

Answer 36

For each process, the kernel
has a table with one entry
per thread, for thread’s
registers, state, priority, and
other information
Examples:
Windows XP/2000
Linux
Mac OS X
Kernel is aware of threads
and schedules them

Question 37

Threads: Some Modern Enhancements

Answer 37

• No guarantee main thread maps to the top of memory. It is near the
top, but may have other things above it
• Example: virtual dynamic shared object (vDSO)
• Rest of stack can be created at random memory areas, not in a stack
area at the top, for security reasons
• Heap need not be contiguous
• POSIX Pthreads in Linux is now kernel-level and allow for fast context
switching. Read up on Native POSIX thread library (NPTL)
• Modern Java uses kernel level threads for Linux and Windows

Question 38

Multithreaded Applications

Answer 38

General Rule of Thumb
• A need to share data structures among threads
• No need to for the OS to enforce resource separation
• Threads need to trust each other

Example Applications
• Web Server
• Serves several clients at once
• Serve other clients while waiting for a disk read to complete for one client

Web Browser
• Load different pages simultaneously

Question 39

Web Servers:

Handling Concurrent Requests

Answer 39

• Using multiple threads

* So that only the flow processing a particular request is blocked

Question 40

Parallelism in Multi-Thread Programs

Answer 40

• Threads can enable parallelism, e.g. different threads operating on
different parts of a data processing task
• When there are multiple cores, each core can run a different thread
from the same process
• Thread affinity: way to bind threads to cores, so threads do not move
from core to core (moving results in poor cache performance)
• What if there’s only one core and multiple threads, or more threads
than cores?
• Subset of threads run on available cores at a time
• When there is only one core, main benefit of threads is division of labor or
interleaving I/O and CPU

Question 41

Race Conditions vs Synchronization

Answer 41

Multiple processes operating on shared data structures, each running
burst of CPU instructions

Race condition:
• Two processes/threads are executing concurrently running CPU bursts on
shared data structures
• Result can depend on the interleaving of the two instruction bursts
• Race conditions cause bugs that are hard to reproduce

Synchronization:
• Process A is blocked waiting for another process B to complete an action
• When process B is done, signal A which blocks and run
• Blocking and not busy waiting

Question 42

What are Pipes?

Answer 42

• Easy way for processes to communicate with each other
• Think of a pipe as an actual physical pipe
• A pipe fills up with data (water)
• One end of the pipe reads (drains)
• Other end of the pipe writes (fills)

Question 43

Pipe API

Answer 43

int pipe (int fd[2])
fd[0] is open for reading
fd[1] is open for writing
Output of fd[1] is input of fd[0]

• For single process, pipe is next to useless. Usually, process that calls
pipe then calls fork
• Reading from a pipe whose write end has been closed returns EOF
• Write to a pipe whose read end has been closed generates a SIGPIPE.
Can be caught or ignored

Question 44

N Stage Pipeline

Answer 44

• Call pipe() N-1 times to create N-1 pipes
• Call fork() N times from the parent process
• For each pair of processes, call dup2() to redirect the STDOUT of
process 1 to be the write end of the pipe
• For each pair of processes, call dup2() to redirect the STDIN of
process 2 to be the read end of the pipe

Question 45

Process Group

Answer 45

• Process group is a collection of processes established for sending a
signal to an entire group
• Processes in a pipeline form a group
• See setpgid to allow a process to change its process group

Question 46

Goal of Job Control

Answer 46

• Job Control allows us to start multiple jobs (groups of processes) from
a single terminal
• Control which jobs can access the terminal (send/receive from
standard in/out) and which jobs runs in the background
• Prevents illegal behavior
• Example: if a background process tries to read from the terminal, a
SIGTTIN signal is delivered to stop the process

Question 47

Synchronous vs Asynchronous Wait

Answer 47

If a parent (shell) creates a process group of child processes, how can
the parent know when the child processes are done?

Synchronous Solution
• Busy wait on all child processes – have a loop that waits on each child

Asynchronous Solution
• Useful for background processes
• Parent waits for SIGCHLD (stopped, exited) signals from children
• When a child sends a SIGCHLD, use SIGCHLD handler
• Call waitpid – specifically, the non blocking version
• Based on return value of child, figure out if child is stopped, exited, etc.
Use WIFSTOPPED(status), WIFSIGNALED(status) to check status

Question 48

Problems with Semaphores

Answer 48

• Incorrect use of semaphore operations:
• signal(mutex) … wait(mutex) results in no mutual exclusion
• wait(mutex) … wait(mutex) results in a deadlock
• Omitting:
• wait(mutex)
• signal(mutex)
• Both