old 471 notes (module 2)
process
difference between process and program
objects are to classes as
processes are to programs
program can create multiple processes
to do different tasks within the program
task
how can two processes communicate?
two methods
message passing
types of message passing/communication'
non-blocking
aka
asynchronous
nonblocking send
message sent and next instruction is executed
nonblocking receive
receiver receives a message or a null msg if none have been sent
blocking
blocking send
unless receiving process receives the message,
the sender that sent the message to the receiving process cannot execute the next instruction until it has been received
blocking receive
process executing receive operation cant execute the next instruction unless it has something to receive
aka
synchronous
direct
asymmetric
only sender must know name of receiver
symmetric
receiver must also know name of sender to receive a message from them
indirect
multiple processes can share mailboxes(ports),
only one can read a message from a port at a time,
by default the process creating the mailbox is the owner and only they have read access, but this can be transferred
creating/deleting,sending to/from mailboxes requires
. system calls by the OS
Automatic buffering
msg buf allocated dynamicaly
explicit buffering
message buffer allocated directly
buffering
3 types
zero capacity
sender blocks until receiver gets msg, msgs cant be stored in queue
bounded capacity
queue has finite cap for msgs, senders must block if queue is full, otherwise they can block/unblock at will
unbounded capacity
no blocking, queue has inf cap for msgs
two kinds of messages
receive
process receives a message from a sender
send
sender sends a message to a receiving process
requires 2 things
os support
system calls for every message transfer, making it slower
2 advantages
simpler to set up
works well across multiple computers
example
client-server system
can a client-server system use shared memory?
no, because theyre on different machines
3 client-server communication stategies
Sockets
socket
defiintion
an endpoint for communication
notation
ip address:port number
how do processes use sockets?
using pairs of sockets,
with each socket associated
with buffer space
ex:
given client host X with ip 160.22.19.7 sending msg on port 1656
and web server with ip 160.22.19.7 receiving msg on port 80
socket(160.22.19.7:1656) - socket(160.22.19.7)
Remote procedure calls
like calling a normal
method, except the method is
on a remote machine, with
only a stub existing on both machines
where the procedure would be
3-5 step process
local process calls local stub
parameters
passed to
stub are packaged
and transmitted
by the RPC system
RPC daemon
on remote end accepts
parameters and calls
the appropriate remote machine's stub
with those parameters
results(if any) are packaged and
transmitted back to local
local unpacks results, returns them to
local stub
optional, only if results
are meant to be returned
example of rpc system
networked file system
Pipes
definition
channels of communications between processes
can be
Unidirectional or bidirectional
meaning
1 way comms or 2 way
half-duplex or full-duplex
meaning
full: pipe is capable of sending and receiving at the same time
half: can only send or receive at any point in time
types
Ordinary
unidir, 2 ends
consumer reads from reading end
producer writes to writing end
only exist when pairs of processes
exists, once they terminate
the pipe terminates
named
bidir,can be used by
more than one pair
of processes,
persist beyond
process termination
of all processes
used by it
example case
multiple processes writing to a file,
only one reader process
aka
fifo
shared memory
the memory is stored in the address space of a process but is accessible to other processes
does not require
system calls after setup, access occurs at memory speed, making it faster
2 disadvantages
complicated to set up
doesnt work well across multiple computers
better in what situation
large amounts of information must be shared quickly on the same computer
definiton
executes code
two types of instructions executed by processes
cpu-based
cpu burst
consecutive time spent executing cpu based instructions
cpu-io burst
one instance of cpu burst followed by an io burst
cpu-io burst cycle
alternating between cpu and io bursts
click to edit
io-based
io burst
consecutive time spent executing io based instructions
unit of execution
instance of a program
consists of
difference between process and source/object code of a program
object and source code are never altered
fundamental entities in operating systems
thread
definition
unit of cpu utilization
types of threads based on who
started it
kernal thread
can execute one or more user threads
associated with the operating system
exist within os
a single kernel thread only operate on a single cpu
user thread
associated with the applications
exist above the kernel
written by app programmers
user threads
must be
mapped to
kernel threads
3 models of thread mapping
many-to-one model
many user-level threads are all mapped onto a single kernel thread
1 advantage
thread mgmt handled by thread library in user space,
making it efficient
2 drawbacks
if a blocking system call is made, then the entire process blocks, even if the other user threads would otherwise be able to continue.
a single kernel thread can operate only on a single CPU, therefore individual processes cant be split across multiple CPUs
One-To-One model
separate kernel thread for each user thread
2 advantages
blocking system call doesnt stop entire process
individual processes can be split across cpus
1 drawback
more overhead, slows system
many-to-many
any number of user threads to equal or smaller number of kernels
3 advantages
individual processes can be split across cpus
blocking system call doesnt stop entire process
thread mgmt handled by thread library in user space,
making it efficient
made up of
program couinter
stack
set of registers
3 thread libraries
POSIX Pthreads
either user or kernel level,
extends POSIX standard thread library
Win32 threads
kernel level, windows
Java threads
uses posix or win32 depending on system
example: file being opened
process is created and associated with the opening of the file
all threads associated with the file are able to use the process
difference between thread and process'
threads are to the heap as processes are to dynamically allocated variables
threads share memory by default
threads == shared_ptr
processes do not share memory by default
processes == unique_ptr
does what
executes a full process
which can do two things
create a child process
create a thread
process states
definition
states a process can be in during execution
5 process states
new
no resources allocated to the process yet
process has not entered system
process enters this state when it is created
process in this state take up no space in memory
process ID is assigned here by the operating system
process ID
aka
pid
ready
process can enter this state in 5ways
process enters this state as soon as it is admitted to the system
process enters this state after completing I/O or an event while in the waiting state
process enters this state when it receives a system interrupt while in the running state/ is waiting for some other interrupt to occur
interrupt
cpu scheduler takes the
a child process is forked and is executed, taking up the current CPU and placing its parent in the ready queue
child process
when created, is an exact copy of its parent,
has the same values
although they share code,
they do not share data, as threads do
once created, exists and runs independent of parent
if parent is terminated, what happens tot he child?
either dies or becomes an orphan
orphan
a child that continues to run after its parent has been terminated
why is it called "forking" a child process?
it runs alongside the parent 
a process's time slice for its CPU expired
once it enters the system, resources are allocated to the process
which resources
everything needed(memory) except the CPU
means
ready to execute
running
process enters this state when a CPU has been allocated to it by a CPU scheduler
aka
scheduler dispatch
dispatcher module
gives control of the CPU to the process selected by the short-term scheduler while a scheduler is selecting the next process to run
process scheduling
process of selecting one of the processes in
the ready queue processor allocation and future execution
ready queue
queue of all PCBs belonging to processes in the ready state
stored in operating systems portion of main memory
affected by degree of multiprogramming
degree of multiprogramming
definition
number of processes a single-processor system can handle efficiently
determined by 5 things
amount of memory available
to be allocated to running processes
program IO needs
program CPU needs
memory access speed
disk access speed
formula
number of ready, waiting, running processes
3 types of schedulers
short-term scheduler
aka
cpu scheduler
program that selects the process on the ready queue for execution on the processor
done when cpu becomes idle
chooses the next process based on one of 5 criteria:
CPU utilization
goal is to keep the CPU busy
how busy?
40-90% utilization
kinds of jobs accepted
any process in ready queue is fine
Throughput
a measure of work done by a CPU
number of processes that complete their execution per time unit
kind of jobs accepted
shorter ones,
means more jobs can complete per time unit
Turnaround time
time between a process entering the system to the time it is terminated and leaves the system
periods spent by the process waiting to get into memory, periods spent waiting in the ready queue, periods spent executing on the cpu, and periods spent doing io
including 4 periods
completion-arrival
Waiting time
total time that a process waits in the ready queue overall CPU bursts.
starttime-arrival
Response time
time between when a process was submitted to the system to the time the first response was produced
relevant for interactive jobs
5 categories of scheduling algorithm
max cpu utilization
max throughput
min turnaround time
min waiting time
min response time
six scheduling algorithms
First-come, First-served ()
simplest CPU-scheduling algorithm
goal
whichever process that is at the front
of the ready queue is selected
aka
whichever process arrived first is selected
meaning
aka
FCFS
implemented via
fifo queue
steps in implementation
when a process enters the ready queue,
its pcb is linked to the tail of the queue
when cpu is free, the process that is linked to the head of the queue is allocated to that cpu
the currently running process's pcb is removed from the queue
example
process, burst time
P1, 24
P2, 3
P3, 4
gantt chart
assuming negligent context switch time, when does each process start and end? what is the waiting time for each process? what is the average waiting time?
P1 starts at 0 and stops at 24
P2 starts at 24 and ends at 27
P3 starts at 27 and ends at 31
w1 = 24 - 0 -24 = 0
w2 = 27 - 0 - 3 = 24
w3 = 31 - 0 - 4 = 27
AvgW = 0 + 24 + 27 / 3 = 51/3 = 17
waiting time formula
endtime - entry time - cpu burst
what if the order they arrived in is P2, P3, P1?
gantt chart:
P1 starts at 7 and stops at 31
P2 starts at 0 and ends at 3
P3 starts at 3 and ends at 7
w1 = 3 - 0 - 3 = 0
w2 = 7 - 0 - 3 = 4
w3 = 31 - 0 - 24 = 7
AvgW = 0 + 7 + 4 / 3 = 11/3 = 3.33
why is this wiating time better?
shorter jobs are exeucted before long ones, avoiding the
convoy effect
when short jobs are positioned after long ones in the ready queue, and must wait for the long ones to finish
disadvantage
when short jobs are stuck waiting for long jobs,
it becomes inefficient because it must wait for those jobs to finish
extreme case
one cpu-bound followed by many io-bound processes
aka
convoy effect
Shortest-job-first (SJF)
2 types
preemptive
aka
remaining-time-first scheduling
shortest-remaining time-first scheduling
occurs when a process arrives in the ready queue with a predicted burst time shorter than the time remaining for the current process's burstly running
implementation
each time a process arrives in the ready queue, halt the current process, let scheduler get the CPU, let scheduler decide which process to be assigned to that CPU, then execute chosen process
example, given p1 burst 8 arrival 0 p2 burst 4 arrival 1 p3 burst 9 arrival 2 p4 burst 5 arrival 3
at t =0, P1 executes because its the only process in the ready queue
at t=1,P2 arrives with a predicted burst time of 4,
while p1 still has 7 left, p2 is executed because it is less than 7
at t=2 p3 arrives with 9, p2 has 3 left, p2 is continued
at t=3 p4 arrives with 5, p2 has 2 left, p2 continues
t=5 p2 ends, p4 is executed
at t=10 p4 ends, p1 is executed
at t=17 p1 ends, p3 is executed until 26
p1 waiting time completion turnaround
10-1 = 9
9+8=17
17-0=17
p2 waiting time completion turnaround
0
5
5-1=4
p3 waiting time completion turnaround
17-2 = 15
26
26-2=24
p4 waiting time completion turnaround
5-3 = 2
10
10-3=7
average waiting time average turnaround time
6.5
13
what are their priorities? why?
p2 1
p4 2
p1 3
p3 4
p2 is shortest, then p4, p1,p3
disadvantage
many more context switches compared to nonpreemptive sjf
nonpreemptive sjf
example,
given p1 burst 6
p2 burst 8
p3 burst 7
p4 burst 3
all procs are in RQ at time 0
p4 then p1 then p3 then p2
goal
pick the a job with the shortest remaining time first
implementation
ties are broken by
use priority
arbitrary choice
must know length of of next cpu burst for each process in the ready queue
advantage
yields smallest average waiting time given a seto f processes
Priority scheduling
priority
an integer value associated with each process
smaller int = higher priority
two kinds
preemptive
2 disadvantages
each switch
requires context switch
tasks with low priority can linger if a continuous stream of higher prioirty processes keep coming in
solution
aging
definition
as a process lingers in a ready queue over time, increase its priority value
aka
starvation
example of preemptive priority scheduling
sjf
how is priority determined in sjf?
the shorter the burst time the higher the priority
when a process arrives in the ready queue, halt currently running process, if incoming proc has higher priority, preempt the current proc and execute the incoming proc, else continue current
nonpreemptive
no currently running processes get interrupted
even if it has higher prio
Round-robin scheduling
worst case performance
lower q == more contxt switches == more overhead
useful for
interactive processes
ex: contxt switches for proc w/burst 10, q 12, q 6, q 1
q12 cs = 0
q6 cs =1
q1 cs = 9
type of scheduling
nonpreemptive
implementation
eqch process is given a quantum, once that quantum is finished, process is preempted and placed in the back of the RQ
else if process burst ends the cpu is released without waiting for quantum to end
quantum
symbol
q
small amount of time
ex
10-100ms
best case performance
higher q == similar to fifo
Multilevel queue scheduling
3 types
Multilevel feedback queue scheduling
implements aging by allowing processes to between queus of differing prioirty lvels
fixed prioirty scheduling
serve all processes in highest prioirty queue, then all in next hightest prioirty, etc
disadvantage
starvation
time slice
each queue gets a certain amount of time on the cpu to schedule its processes
different ready queues for different kinds of processes
cpu is shared between different queues
3 methods of determining algorithm performance
Deterministic modeling
use predetermined workload to find the performance of each kind of algorithm under that load
Queueing models:
uses queuing theory
aka
gantt charts, make a model of the queue
Implementation
implement the algorithm and measure the performance from there
how are the start and end times of processes in the ready queue portrayed?
gantt chart
shows the process that is being executed on the CPU at any given time
long-term scheduler
aka
job scheduler
picks a process from a pool of jobs stored on disk, loads them into memory, then adds them to the ready queue
medium-term scheduler
swaps out processes to reduce degree of mulitprogramming, releasing its memory and increasing available memory to be allocated to processes
swap out
move a process out of the ready queue and on to disk, state stored in pcb
context-switch
when a currently running process is interrupted, swapped out, and another ready process is brought in for execution
time for one context-switch = time between storing state in pcb and restoring state from pcb
swap out, swap in take up cpu time,
context-switch therefore does as well
swap in
putting a process that was swapped out to disk back into the ready queue, state restored from pcb
maintain a good mix of processes in the system,
prevent cpu over/underuse, io device over/under use do to flood of cpu-bound or io-bound processes
2 types of scheduling
non-preemptive scheduling.
currently executing process is stoppable and put to ready state, with the CPU getting assigned to another process
default, unless specified otherwise
preemptive scheduling.
currently executing process is allowed to continue execution until it either terminates or goes to a wait state
4 cases where scheduling decisions are made
Switches from running to waiting state (non-preemptive)
Switches from running to ready state (preemptive)
Switches from waiting to ready (preemptive)
Terminates (Non-preemptive)
when a process:
3 steps
1 switching context
time to do these things
Dispatch latency
definition
time it takes for the dispatcher to stop one process and start another process to run.
2 switch to user mode
3 jump to location in user program to restart that program
means
process is currently running on the CPU
process is being executed
what can happen to a running process?
the CPU scheduler can interrupt the process, sending the process back to the ready state and freeing up the CPU it was running on
waiting
process enters this state when it receives I/O, event wait
the processor's PCB is then entered into that I/O device's I/O queue
I/O queue
each IO device has one
stored in the operating system's portion of main memory
process exits this state when I/O or event is completed
terminated
process enters this state when it leaves the system
processes in this state take up no space in memory
any resources used by the process are freed after terminating
types of resources used by process that are freed on termination
files closed
memory
4 reasons for system to terminate a process automatically
system couldnt deliver required system resources
kill() command, or other unhandled interrupt
parent can kill its child if the task given to it is no longer needed
parent exits and does not want child to go on without it or operating system kills children by default
diagram
use web capture not select
when is a process's status saved?
running to ready
running to waiting
why is it saved
so that when execution is resumed, it can start back where it left off
how is a process's status saved
within a process control block
process control block
diagram
consists of
process state
process number
program counter
address of the next instruction to be executed
CPU registers
contents of the registers prior to the last halting of a process
memory-limits
info about the memory allocated to the process
list of open files
files opened by the process
...
other info needed to resume a process
part of a process
only three states have resources allocated, take up no space in memory,
and are the only ones the operating system cares about
ready, running, waiting
types based on instructions
io-bound processes
spends more time on io instructions than cpu
too many overloads io queue, underutilize cpu overutilize io devices
cpu-bound processes
spends more time on cpu instructions than io
too many overloads ready queue,
underutilize io devices overutilize cpu
types based on communications
independent
cant affect or be affected by other processes
cooperating
can affect or be affected by other processes
4 reasons for this
modularity
process can be broken up into cooperating modules with each one implemented as a process
information sharing
different processes can use the same file
ex
pipelines
computation speed
task may broken down into sub-tasks to be solved simultaneously
(particularly when multiple processors are involved
convenience
lets a single user multitask
types of processes based on number of threads
Traditional process
aka
heavyweight
single-threaded
one program counter
one set of registers
one stack
Multi-threaded process
multiple threads within a single process
each having their own program counter, stack, and set of registers and sharing common code,
data, and structures(ex:files)
useful for
process has multiple tasks to perform independently of one another, especially if one of them can block the others and we want them to go on without being blocked
ex
web server being able to fulfil multiple requests at once, without doing one after the other or forking new processes to handle each one
4 benefits
Responsiveness
prevents the blocking or slowness
of one thread from slowing down the others
Resource sharing
By default, threads share common code, data, and other resources, which allows multiple tasks to be performed simultaneously in a single address space.
Economy
easier to make,manage, context switch threads compared to processes
Scalability
execution of a mt app can be split
across availabe processors