CPSC 457 Notes

• Operating system is a program that acts as an intermediary between user and computer
hardware.
• Computer systems can be divided into 4 parts –
o Users
o Application Programs
o Operating System
o Hardware
• One program always running in a computer is a kernel.
• Bootstrap program is program loaded at power up or reboot and is responsible for loading
operating system kernel.
• Device Controllers oversee a particular device type. So external devices and CPU can process
concurrently.
• CPU sends information to the external device, and it is stored in the buffer. The device controller
stores this information in the buffer and then forwards it to the external device when it is ready
to accept. CPU and device perform tasks concurrently, and device can inform CPU of finished
status using interrupts.
• Interrupts transfer control to the Interrupt Service Routine using Interrupt Vector.
• Interrupt Vector contains address to all Interrupt Service Routine.
• A trap or an exception is a software generated interrupt caused by error or user request.
• 2 ways of handling interrupts –
o Polling – constantly checking to see if the flag is raised
o Vector Driven
• System call – request to OS to allow user to wait for I/O completion
• Device status table – contains entry for each IO device indicating type, address, and state.
• Main Memory is volatile and random access
• Secondary storage is extension of main memory that provides large non volatile storage
capacity.
• Hard disk surface is divided into tracks which are sub divided into sectors.
• Disk Controller determines interaction between hard disk and computer.
• Caching – copying information temporarily in faster memory from slower storage for faster
access.
o Main memory can be viewed as Cache for secondary storage.
• Device controller transfers blocks of data to buffer storage without CPU intervention (while
reading data from memory). Interrupt is generated per block rather than per byte.
• Multi processors also know as parallel systems or tightly processed systems. Advantages include
–
o Increased throughput
o Increased reliability
o Increased economies of scale
• Asymmetric multiprocessing – each processor is assigned a specific task.
• Symmetric multiprocessing – each processor is assigned the same task / all tasks.
• Clustered Systems – like multiprocessor systems but with multiple systems working together.
 • Multiprogramming – batch system – needed for efficiency – because single user cannot always
keep cpu busy.
• Timesharing is logical extension where cpu switches jobs so that user can interact with programs
while they are running
• Dual Mode Operation (Kernel Mode(0) vs User Mode(1)) allows os to protect itself and other
system components. Mode bit is provided by hardware.
• Program is a passive entity stored on the disk; Process is an active entity. Process is a Program
in execution.
• Single threaded process has one program counter specifying location of next instruction to
execute.
• Multi threaded process has one program counter per thread.
• To execute a program all (or part) of the instructions must be in memory.
• Protection is any mechanism for controlling access of processes or users to resources defined by
OS.
• Security is the defense of the system against internal or external attacks.

-----x------

• Benefits of threads –
o Responsiveness
o Less overhead than process switching.
o Easier to share resources.
o Process can take advantage of multithreading architecture.
• Parallelism informs that system can perform more than one task simultaneously.
• Concurrency means that more than one task is making progress
o Single processor or core providing concurrency.

• 2 types of threads –
o User Threads: used by user through user level threads libraries. Eg – POSIX_PTHREADS
 o Kernel Threads: used by os

---x

• Process is a program in execution.

• Process has multiple parts –
o Stack
o Data section containing global variables.
o Program code – called text section.
o Current activity including program counter, processor registers.
o Heap containing memory dynamically allocated during the run.
• States of processes –
o New: The process is being created
o Ready: process is waiting to be assigned to a processor
o Running: Instructions being executed
o Waiting: The process is waiting to for IO or event
o Terminated: Process has finished execution

• Process Control Block contains information associated with each process.

• Process Scheduling maximizes use of CPU by making sure it is not idle.
 • Process Scheduler selects among available process for next execution of CPU.
• Maintains scheduling queues –
o Job Queue – set of all processes in system
o Ready Queue – set of all processes in main memory waiting to execute
o Device Queue – set of processes waiting for IO device
• Queueing diagram represents queues, resources and flows
• Two types of schedulers –
o Long Term Scheduler: invoked infrequently (once every few seconds/minutes). Decides
which processes come into the ready queue. Controls the degree of multi-
programming.
o Short Term Scheduler: is usually the only one there, is invoked frequently (once every
few ms). Decides which processes from the ready queue should be executed by the CPU.
• Processes can be either described as –
o I/O bound processes: process that uses cpu in short bursts
o CPU bound processes: process that uses cpu for longer periods of time with short burst
of cpu inactivity
• Context Switching – when cpu switches from one process to the other and saves program state
of the old process in its pcb and loads the program state of the new process from its pcb. No
useful work is done during context switch.
• Context of a process is represented in its PCB.
• Process PID – the pid of the self - getpid
• Getppid – returns pid of the parent process of the calling process
• Fork() – creates a new child process that executes from the line after fork
o Return value is negative if the creation of child process was unsuccessful
o Return value is zero if the child process was created and the process in question is the
child
o Return value is positive if the child process was created and the process in question is
the parent (return value is the pid of the child)
• Wait () – suspends a parent process until one of its children process has exited.
o Returns pid of terminated child process which can be compared with fork
• Zombie – child process completed but no parent picked up exit code. PCB still exists
• Orphan Process – parent process terminates before child process completes.

---x----

• System Calls –
o System() (in C) is a command that takes string input and executes it in the command line
▪ Eg – system(“echo I like CPSC”)
▪ System call causes a new process to be formed for executing the command
o Exec/execve – used to perform command line operations but in a different way to
system
▪ New process takes the process-id of the old process.
▪ No return value unless error. -1 if error has occurred.

--x—
Threads

• A thread
o Uses process resources.
o Has its own independent flow of control (Program counter)
o Duplicates essential resources like stack.
o May share process resources with other threads (code section, data section, Heap)
o Dies if the parent process dies.
• Threads can access local data of another thread through the pointer of the variable.
• Use Pthread_create to create new threads
o Can pass specific arguments to the threads via this function
o Returns positive number if thread creation was unsuccessful.
o Returns 0 if thread creation was success.
• Execution of threads is not dependent on the time of birth of threads. Thread A created after
Thread B can execute first based on various different factors (if there is no correctly placed
pthread_join somewhere)
• Threads exit automatically after their function’s return statement. Pthread_exit is called
implicitly inside each thread.
• void pthread_exit(void *v_ptr); - argument is a pointer that can house any return data since
after exiting the thread all local data is lost.
• Main thread uses exit() which is different from pthread_exit
• To wait until a thread completes execution – use pthread_join
o If successful – returns 0
o Else error
o Is a blocking function
o int pthread_join(pthread_t th , void **vtr); - as an argument it uses a pointer in which
the return from thread (from pthread_exit) is stored
• Ordinary Pipes – allow for inter process communication between parent and child processes
• Named Pipes – allow for inter process communication b/w processes without need for child-
parent relationship
•

---x---

Synchronization

Initial value of semaphore may indicate how many simultaneous processes can be run on the system.
Based on below code (Semaphore+1) processes can run simultaneously

• blocking wait –
o wait(S){
while(S<=0);
S--;
 //proceed to critical section
}
• signal pair for above –
o signal(S){
S++
}

free to use multiple waits and signals

• non blocking wait

o wait(S){
S->value--;
if(S->value<0)
//put process to sleep

• signal pair –
o signal(S)
S->value++
if(S->value<=0)
wake up one of processes in queue
• Critical Section Problem solving criteria -
o Mutual Exclusion -
o Bounded Time – how many times can p1 enter while p2 is waiting to enter. Ideally
should be 1
o Progress requirement
• Deadlock – two or more processes waiting processes waiting for an event that can only be
caused by another waiting process
• Starvation – Indefinite blocking

---x---

Monitors

• Abstract data type where internal variables are accessible only by code internal to procedure
o Eg - Implementing an interface for a printer
• Only one process is active in the monitor at one time.