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

image

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

image

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

image

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 image

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

image

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

image

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

image

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

image
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

image

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