CSC 246 Exam 1

Advantages and disadvantages of OS

virtualizes interface, easy to use, safe, allocates resources, allows programs/users to share hardware resources

system programs

lie between user and system calls, define the view of the system, what user actually interacts with

System calls

how OS provides interface to end users

Caching

The local storage of frequently needed files that would otherwise be obtained from an external source, much faster than memory

Temporal locality

program is likely to access data it has accessed recently (stored locally for quick and recent use)

Spatial locality

The program is likely to access data that is close to data it has accessed recently

Examples: sequential code execution, table of data (array/list).

Write-through cache

data simultaneously updated to cache and main memory

Write-back cache

updates the underlying memory when the data is moved out of the cache, updates to main memory when cache line is ready to be replaced, designed to reduce number of writes to memory

Device controller

A processor that controls the physical actions of storage and I/O devices, communicates with CPU via bus

DMA

direct memory access, completes bulk transfers between device controller and memory

Interrupt

a way for device controller to get the CPU attention

Interrupt Vector

address that informs interrupt handler where to find start routine, helps the dispatch control to the right part of the kernel

Trap

kind of interrupt that that comes from user programs

Trap instruction simultaneously

1. Jumps into the kernel
2. Raises the privilege level to kernel mode

Return-from-trap instruction simultaneously

1. Returns into the calling user program
2. Reduces the privilege level back to user mode

Dual mode operation

Privileges for kernel can not be performed by users (prevents infinite loops and protects OS from errant users)

Kernel Mode

Access to all CPU instructions and registers, where privileged instructions can be performed

User mode

Access to a restricted set of CPU features. Can't run privileged instructions

Switching to Kernel Mode

Interrupt driven
-Hardware by device
-Software interrupt exception or trap
1. Error
2. Request for OS service
What happens once interrupt occurs, CPU will do..
1. Suspend current instruction
2. jump to interrupt handler
3. switch to kernel mode

System Call vs Subroutine

system calls are priveleged and the subroutines are not

System Call Implementation

1. Invokes the intended system call in OS kernel and returns status of the system call and any return values
2. Caller only needs to obey the API and understand what the OS will do because of the execution of that system call
3. Most of the details of the OS interface are hidden from the programmers

Memory Protection

Program is restricted to contiguous region of memory. Base register and Limit register are used so that the CPU checks between them on every access to memory

Base registers

address the first byte the CPU can access while in user mode

Limit registers

number of bytes the program can access (starting from base)

CPU Protection

Timer interrupt makes sure that CPU can switch to kernel mode

Timer Interrupt

Kernel sets the timer before giving the user a chance to run, makes sure that user can't run indefinitely

I/O Protection

I/O instructions are privileged
OS forces user programs to request them via system call

jobs of operating system

Support for program execution

Memory provider for porgram

Allocate, use and return resources for program

Protection and security mechanism provider

IPC permission Error

Responder Accounting

UI Provider

System boot

1. Start running firmware at a known address
2. Load boot loader from 2nd storage
3. Bootstrap loader copies kernel into mem and starts exec
4. Kernel initializes interrupt vectors + other ds
5. Kernel starts running utilities

Two major components of modern operating system

Kernel and system utilities

Kernel

everything behind the system call interface
-file system, CPU scheduling, memory management
-all running in kernel mode
Mostly implemented as a collection of functions

System utilites

-to keep the system running
-to let users interact with the system

Monolithic kernel

design where everything runs in the kernel, bad for bugs and portability, code not organized

Microkernel

move some OS components into user space to make kernel smaller, easier to extend, add new features in user space, easier to port to a new architecture, less code in kernel mode, so more resistant to failure, more secure however more overhead

Requirements of microkernel

- well-defined categories of user mode OS services
- well-defined interfaces for each type of service

Process

an abstraction for a running program that includes the ability to execute instructions, protected region of memory, ability to have and use resources, usually associated protection domain

Process memory layout

text, stack, heap, data

Stack

local variables, return adresses

Heap

dynamically allocated memory

data

writeable global variables

text

code and other global, read only data

Process creation

1) Assign a unique process identifier to the new process.

2) Allocate space for the process.

3) Initialize the process control block.

4) Set the appropriate linkages.

5) Create or expand other data structures.

PID tree

Creating a process is called a parent process
creating a new process is the children of that process
the process can create others so it becomes a tree

int fork(void)

makes a child
child has a copy of the parent's memory return 0
parent return an ID

int wait(int *child_status)

makes a parent wait for its children to terminate

void _exit(int status)

terminate the current program

int execl(char *path, char *arg0, char *arg1, ..., null );

gets a process to run a different program
called after fork()

Context Switch

1)interrupt occurs (PC pushed to stack, switch to kernel mode, jump to interrupt handler)
2) decide to run process P1 instead scheduling decision
3) save a copy of PC and other CPU registers to P0
4) Save memory bounds for P0
5) Restore memory bound for P1
6) Copy P1 PC into stack
7) Return from Interrupt

PCB layout

state, pid, copies of pc and other registers, memory bounds, accounting info, open files (no state or registers for multithreaded process)

Process state

new, ready, running, waiting, running, or terminated

Process counter

counter indicates the address of the next instruction to be executed for the process

CPU registers

may hold an instruction, a storage address, or any kind of data

I/O status information

This information includes the list of I/O devices allocated to the process, a list of open files, and so on.

Process state: New

The process is being created
this-\>ready \= admitted

Process State: Running

Instructions are being executed on the CPU
this-\>exit \= terminated
this-\>I/O or event wait \= waiting
this-\>interrupt \= ready

Process State: Ready

The process is waiting to be assigned to a processor
this-\>scheduler dispatch \= running

Process State: Waiting

the process is waiting for some even to occur (such as completion or reception of a signal)
this -\> I/O completion \= ready

Process State: Terminated

process has finished execution, still has a process ID, but isn't runnable

PCB Organization

Process table lists all of the PCBs, moves PCBs during context switch to keep resources busy

Scheduling queue

list of PCBs for a process waiting on service

ready queue

list of processes ready to run, scheduled by CPU scheduler

Signals

signal are mechanism for upcalls
used in UNIX syst to notify P that a particular event has occured, maybe received either synchronously or asynchronously depending on the soruce of and the reason for the event

generated by occurence
delivered by a process
must be handled

Asynchronous signal

UNIX - Signal that notifies an external process.

Synchronous signal

UNIX - Signal that notifies the process itself (division by zero, illegal memory access, ...)

IPC Mechanism

Message Passing - pipe and message queue
Shared memory

Message Passing IPC

message - sequence of bytes to exchange
system call to:
move msg btw p memo
send msg
receive msg
Examples
POSIX anonymous pipes, message queue

anonymous pipes

calls used pipe() read() write() close(), indirect, boundaries not respected

Message Queue

calls used mq_open() mq_send() mq_receive() mq_close mq_unlink(), indirect, boundaries respected

Blocking

process waitng until its request is done
aka p waits for IO, p goes into waiting state bc no progress
important mech

Nonblocking

I/O call returns as much as available

Block receive

waits to receive message

Non-blocking receive

check for a message, check back later if one isn’t received

blocking send

Wait until you can get rid of the message (either to the OS or the receiver)

Non-blocking send

try to send, try later

Buffering

OS holds msg tmp
msg have been sent out but not received
sender makes progres even if receive falls behind

Shared memory

two programs connect via memory shmget() shmat()
-write into share memory to communicate
-read from share memo to receive msg
-no need for explicit calls for communication
indirect, lots of busy waiting, poor synchronization

busy waiting

a method by which processes, waiting for an event to occur, continuously test to see if the condition has changed and remain in unproductive, resource consuming wait loops

direct communcation

name process id to send to

indirect communication

send via name communication channel

Create a pthread

pthread_create(&tid, NULL, startRoutine, args)

join thread

pthread_join(tid, &returnptr (NULL))

Pthreads

refers to the POSIX standard defining an API for thread creation and synchronization
allows for different tasks to in parallel accross in multi computing cores
less time consuming than processes

shared data in thread

heap, data, text, code

not shared in thread

stack, registers

Thread Implementation advantages

Lower context switch overhead
lower cost per thread
user space code can make application specific scheduling choices
reduced consumption of kernel resources
portability

kernel level thread

kernel maintains control block for each thread and independently schedules each thread aka lightweight processes

user level thread

does everything inside a process, so kernel does not know about them, is a lot less expensive but disadvantage is the blocking behavior

Thread Implementation disadvantages

reduce concurrency
may reduce share cpu time

Blocking behavior

big disadvantage of user level thread

Pthread API

compile -lpthread
pthread_create(&thread, NULL, startRoutine, argPtr)
pthread_exit(returnPtr)
pthread_join(tid, &returnPtr)

Many-to-one-model

maps many user-level threads to one kernel thread, can't run in parallel on multi processors
whole thing gets blocked
can acess the kernel at the time so multiple threads are unable to run in parallel

One-to-one model

maps each user thread to a kernel thread. provides more concurrency than the many to one model by allowing another thread to run when a thread makes a blocking system call; also allows multiple threads to run in parallel on multiprocessors
drawback creating user thread req creating the corresponding thread and a large number mayb burden perf

Many-to-many model

Maps many user-level threads to a smaller or equal number of kernel threads. Developers can create as many user threads as necessary, and the corresponding kernel threads can run in parallel on a multiprocessor as they become available. blocked other thread can make another thread for exec. More important threads go to one kernel thread

Asynchronous cancellation

kills the thread. Is problematic bc thread is stopped in the middle of the job its performing which may mess things up across the shared variables

Deferred cancellation

define cancellation points where thread terminates
pthred_cancel(tid)

times CPU scheduler will run

-process terminates
-process yeilds CPU
-process blocks
-timer interrupt occurs
-another process finished waiting and has more priority

cpu utilization

how often cpu runs user process

throughput

how many processes are finished per time unit

turnaround time

time end - time arrival

waiting time

time a process spends in the ready state (turnaround - burst)