I took CSI3131: Operating Systems during the Winter 2019 Semester. The notes below reflect my learning over the duration of the course. Each section anchor is hyperlinked in the table of contents above. References and footnotes are present1 and can be found at the end of the document.
Operating Systems covers the design and implementation of basic operating systems, and provides students with hands-on experience solving OS-level problems involving processes, threading, memory management and Input/Output. Section A is being taught by Burak Kantarci (
[email protected])
Winter 2019 lectures run from January 7th to April 5th; the second week of the year through to the end of week fourteen. Lecture notes are labeled according to week, then by day/lecture. My schedule for this class/year is as follows:
Tuesday 1600h - Lecture in Morisset Hall 218
Tuesday 1730h - Laboratory in SITE 2052
Thursday 1430h - Lecture in Morisset Hall 218
Thursday 1430h - Tutorial in Simard Hall 425
Each week entry is filled with the material that will be covered in the coming week, to review on the weekend-of. Each event entry should contain a summary of the learning and notes.
MathJax has been included for the presentation of formulae and mathematics, tutorial
here
.
It can be written inline, like so: $$ A \times B = C $$ - pretty neat. The primary means of inclusion will probably be in a block, to present formulae:
$$
v_{O} = IR = \left( \frac{R}{ R + r_{D}} \right) (v_{s} + V_{DO})
$$
Might be good to glance though the first chapter or two of the textbook in preparation for the winter semester.
Chapter One is an introduction and overview of computing environments.
Chapter Two is on Operating-System Structures
Solutions to the practice questions and extra materials are available at
http://www.os-book.com
.
Today’s CSI lecture discussed parent and child processes, including use of the fork() command (paired with wait() and exit) to orchestrate a simple parent+child process.
Generally, this week has been discussing processes. The following concepts are earmarked as important:
Process states, including switching.
The PCB (Process Control Block) - What it does, stores.
Process scheduling.
Operations on processes.
Mechanisms for process cooperation. (IPC)
Job, task and process are used interchangeably during the lectures.
Process states:
New - Process is being created & loading.
Waiting - Process requires some event to occur.
Ready - Process is not running, but ready to be assigned to run.
Running - Process is executing instructions.
Terminated - Execution has finished.
Process information is saved in a PCB (Process Control Block) which includes all of the context for a process in the waiting, ready, or running state. When program execution is put on hold, the PCB is saved so execution can resume with CPU registers in the same state at a later time:
Process State
Process Number
Program Counter (PC)
Registers
Memory Limits
List of Open Files
Given a list of I/O, System and User programs, a Scheduler must be utilized to determine the order in which waiting tasks are executed.
Process Scheduling Queues can be used. Job (all processes), Ready (processes in main memory) and Device (I/O) queues separate processes and run them based on queue priority. In this scenario, Long Term Schedulers are responsible for moving jobs from the Job (new state) to Ready queue (ready state), and the Short Term Scheduler manages programs in the main memory, choosing to make them run or wait. Medium Term Schedulers may also be used to swap processes from the main memory to disk (Swap Space).
/*
* rcf016_fork.c - Experimental program that uses UNIX sys calls.
* Copyright (C) 2018 Ryan Fleck under the GNU GPLv3.
* Compiled & tested using GCC.
*/#include<stdio.h>#include<unistd.h> // Provides fork()#include<stdlib.h> // Provides exit()// sys/types and sys/wait provides wait()
#include<sys/types.h>#include<sys/wait.h>intmain(intargc,char**argv){puts("I am a process, about to fork().");intpid=fork();//Forks _at this point_ in execution.
if(pid==0){puts("I am child.");exit(0);}else{intstatus;wait(&status);printf("I am parent. Child exited with status %i.",status);}return0;}
fsck is used to check and optionally repair one or more Linux file systems. filesys can be a device name (e.g. /dev/hdc1, /dev/sdb2), a mount point (e.g. /, /usr, /home), or an ext2 label or UUID specifier (e.g. UUID=8868abf6-88c5-4a83-98b8-bfc24057f7bd or LABEL=root). Normally, the fsck program will try to handle filesystems on different physical disk drives in parallel to reduce the total amount of time needed to check all of the filesystems.2
Reading week. Midterm preparation. Date: Feb 26. Covers:
Module-1: Operating System Overview
Module-2: Processes
Module-3: Threads
Module-4: CPU Scheduling
Module-5: Process and Thread Synchronization
--until Semaphores (exclusive; semaphores not included)
An interrupt request is sent through the control bus, and an IHR (Interrupt Hander Routine) is started by the OS.
An instruction cycle will check for interrupts after each instruction is executed. If present, the current program is suspended and the interrupt handler is executed.
Can have different priorities:
Can occur sequentially, interrupts cannot be interrupted.
Can have priorities: certain interrupts take precedence.
Interrupt Classes:
Program IO for output and errors.
Exceptions that stop execution.
Timers that preempt a program to perfomr another task.
Cache is very fast CPU memory. When requesting data, the processor will check the cache for a word, and pull a block with the word from main memory if not present.
Access Time - how long does it take to bring a referenced word into the processor?
Where T is Total time, T1 is access time for cache, T2 is ‘at for main memory.
‘AT Hit Ratio - Fraction of data that is in the cache when it is called.
Types:
Programmed IO
CPU waits for each IO operation, checking if IO op is complete.
Cycles are used to monitor the IO.
Interrupt-Driven IO
CPU executes instructions while IO is running.
IO response processed and stored in memory/storage by the CPU.
Direct Memory Access
CPU sends request to DMA module.
DMA module assigns a block of memory for IO to directly transfer data to.
Interrupt sent when task is complete.
CPU only involved at the beginning/end of transfer, free otherwise.
Improper synchronization - Programs waiting for IO must recieve signals correctly.
Failed mutual exclusion - Prevent simultaneous data access.
Deadlock - Programs wait for each other endlessly (Canadian computers).
Solutions to Multiprogramming and Time Sharing problems:
System Structure
Processes
Systematic way of initiating, controlling and monitoring program execution.
A Process is an executable program including:
Associated data: variables, buffers.
Execution context: content of registers, process priority.
Memory Management
OS provides programs with virtual memory.
Memory space of a program can exist on real memory and on disks.
All program calls to memory are to virtual memory.
Hardware mapper must map virtual memory to hardware.
When an address that is not present in hardware memory is referenced:
A block of lower-usage memory is persisted to disk (swap space).
Referenced data is moved to hardware memory (real memory).
Information Protection/Security
A filesystem is implemented to organize long-term data storage on disks.
Data objects (files) are loaded into virtual memory for manipulation.
Access control is implemented to restrict the usage of certain processes and files to specific users or roles.
Scheduling/Resource Management
Differential Responsiveness ensures important processes are executed first.
Fairness ensures processes of the same class are given equal access to resources.
Efficiency - “Maximize throughput, mimimize response time, accomodate as many users as possible.”3
A dispatcher (dispatcher is the short-term scheduler) decides which process in memory to execute next from a queue.
Long term scheduler responsible for determining what subset of programs in a queue should be active. Too many, and the CPU will thrash as it context switches continuously.
Queues exist for each IO device, so processes do not access them simultaneously.
Dispatcher - Short term scheduler responsible for moving progs from ready to running.
Medium term - Selects which processes to move to/from swap space.
Long term - Selects which progs to move from new to ready, into memory.
Context Switching
In a multiprogramming scenario, when a prog is waiting for another prog or io, its context is saved into a PCB, and a ready program is brought back into the CPU.
PThreads: POSIX standard API for kthread init/sync.
intmain{intid[6];for(i=0;i<6;i++){id[i]=i;pthread_create(&tid[i],&attr,worker,&id[i]);}return0;}void*worker(){printf("I am a Worker Thread");pthread_exit(0);}
Java Threads: extend Thread class or implement Runnable for uthreads.
classWorkerextendsThread{publicvoidrun(){System.out.println("I Am a Worker Thread");}}publicclassFirst{publicstaticvoidmain(Stringargs[]){Workerx=newWorker();x.start();System.out.println("I Am The Main Thread");}}
Join with thread.join();
Interrupt with thread.interrupt();
Use ThreadLocal to create thread-specific data.
Implementations
UNIX
Calls them tasks, clone() sets full/little sharing.
Windows XP
Implements one-to-one mapping.
Threads contain id, register set, separate user/kernel stacks.
Maximize resources by ensuring CPU does not waste cycles on blocked ops.
Scheduling algos balance resouces based on different needs.
Majority of CPU bursts are very short before blocked waiting for IO.
Dispatcher module gives the proc selected by the short-term scheduler CPU time. Dispatch latency is the time it takes the dispatcher to stop a process and begin running another.
Optimize For:
Servers -> Throughput, # of processes that complete per time unit.
Batch Systems -> Low turnaround time, submitted job completion.
Heavily loaded sys -> Fairness & waiting time.
Time Sharing sys -> Response time, request submitted to system response.
There will be questions about the above optimization scenarios. The following metrics will need to be provided, along with averages:
Utilization is the percentage when processes are running. (90%)
Throughput is the processes finished divided by the time. (4/23)
Turnaround TIme is measured in time units, how fast the sys finishes computation since proc arrival (3us)
Waiting Time: duration after proc arrival when proc not being executed.
Response Time: duration between proc arrival and first execution.
Generally:
Maximize CPU Utilization and throughput.
Minimize turnaround, waiting, response times.
Preemptive:
Definition: taking measures to handle an imminent event.
OS Definition: CPU switches tasks before proc voluntarily releases it.
Example: Proc uses up alloted time slice, switches from running to ready.
When proc arrives, it is put at the end of the ready queue.
Proc at front of queue runs until finished.
Not preemptive. Dumb algo.
Convoy effect: low CPU and IO utilization as everything waits.
SJF: Shortest Job First - two cases:
NonPreemptive:
CPU bursts allowed to finish.
Preemptive:
CPU bursts interrupted when a shorter burst-len task arrives.
Gives minimum average waiting time.
Burst times estimated with exponential averaging:
$$ t_n $$ - Length of $$ n^{th} $$ cpu burst.
$$ \tau_{n+1} $$ - Predicted length of next cpu burst.
$$ \alpha $$ - Inclusively between 0 and 1, relative weight of val. Should be lower if a process has more anomalies. Closer to 1, more emphasis placed on immediately previous burst.
Transplanted from [Java Manual]({{ site.url }}/java#semaphores).
A Semaphore is a data structure used to address synchronization problems. It can be used in a variety of patterns. Essentially, a semaphore is a number that can be incremented or decremented, but not read, and the value of the semaphore dictates if a thread can continue operating, or must wait. The rules are well defined in the Little Book of Semaphores8 (This numbered list of rules is copied from the text.):
When you create the semaphore, you can initialize its value to any integer, but after that the only operations you are allowed to perform are increment
(increase by one) and decrement (decrease by one). You cannot read the
current value of the semaphore.
When a thread decrements the semaphore, if the result is negative, the
thread blocks itself and cannot continue until another thread increments
the semaphore.
When a thread increments the semaphore, if there are other threads waiting, one of the waiting threads gets unblocked.
A basic implementation of a semaphore in Java appears as follows, utilizing the built-in Thread library for wait() and notify() to stop and start the threads.
Wait and signal are used in a number of different ways. At this point, it is best to discuss some common patterns to show how semaphores work, and when to apply them. In the subsections below, threads are labeled A, B, C... N, and Semaphores are sx, sy, sz... n or sa, sb, sc when created to deal with a specific thread.
When thread A requires thread B to complete an action before it can continue, it must wait until thread B sends a signal. This ensures that A will never dostuff() before B does.
Semaphoresx=newSemaphore(1);/* Thread A */sx.wait();doStuff();/* Thread B */doStuff();sx.signal();
When thread A and B need to wait for each other, and cannot continue to execute until both finish certain commands. Neither thread can proceed until they reach a given point. To implement this, ensure each thread signals as it arrives, and is placed into the thread queue as count is below zero. The second thread to signal() will call wait() on the first thread, which will call wait() on the second thread, and both can continue to dostuff2(), though the order is not guaranteed.
// Tracks if A is ready.SemaphoresaReady=newSemaphore(0);// Tracks if B is ready.SemaphoresbReady=newSemaphore(0);/* Thread A */doStuff();saReady.signal();sbReady.wait();doStuff2();/* Thread B */doStuff();sbReady.signal();saReady.wait();doStuff2();
Short for Mutual Exclusion, ensures only one thread can execute the code in a crital section concurrently. A very large number of threads can operate concurrently using this model, and it is guaranteed that only one will ever doCriticalStuff() at any given moment.
Semaphoresx=newSemaphore(1);/* Thread N */sx.wait();doCriticalStuff();sx.signal();
The Multiplex pattern allows a set number of threads to enter a critical path concurrently. This pattern is identical to the Mutex pattern, but the Semaphore is instatiated with value n as count, where n is the thread limit.
Semaphoresx=newSemaphore(n);/* Thread N */sx.wait();doCriticalStuff();sx.signal();
An n-threaded generalization of the Rendezvous pattern. All threads will be blocked until the nth thread arrives, and then all can continue simultaneously. The solution incorporates a turnstile where the semaphore is rapidly decremented, then incremented, allowing each thread to pass through after the nth thread arrives. Unfortunately, this barrier pattern can only be used once as the turnstile does not reset itself.
// Mutex used to update the thread count.Semaphoremutex=newSemaphore(1);intcount=0;// Barrier used to count incoming threads.Semaphorebarrier=newSemaphore(0);// Init as locked./* Thread N */mutex.wait();count++;mutex.signal();// Makes the barrier one to enable turnstile.if(count==n)barrier.signal();// Turnstile occurs.barrier.wait();barrier.signal();doStuff();
Threads wait before and after executing the critical section, in order to ensure no threads lap the others. Only one barrier is open at a time. When count reaches n, barrierB is locked and barrierA is opened, and vice versa. Locking/unlocking the barriers involves incrementing the semaphore once so it can turnstile when all the threads arrive.
// Mutex used to update the thread count.Semaphoremutex=newSemaphore(1);intcount=0;// Barrier used to count incoming threads.SemaphorebarrierA=newSemaphore(0);// Init as locked.SemaphorebarrierB=newSemaphore(1);// Init as open./* Thread N */mutex.wait();count++;if(count==n){barrierB.wait();barrierA.signal();}mutex.signal();barrierA.wait();barrierA.signal();doStuff();// Critical point.mutex.wait();count--;if(count==0){barrierA.wait();barrierB.signal();}mutex.signal();barrierB.wait();barrierB.signal();
A queue ensures threads of different types proceeed in pairs.
SemaphoretypeX=newSemaphore(0);SemaphoretypeY=newSemaphore(0);/* Thread A of type X */typeY.signal();typeX.wait();doStuff();/* Thread B of type Y */typeX.signal();typeY.wait();doStuff();
How can we programmers guarantee that a thread or process has exclusive access to a set of resources in a ‘critical section’ of the code? A good solution must meet a few requirements. Mutual Exclusion must be attained, where only a single thread is executing the critical section simultaneously. The CS must be accessible to all threads that need to enter it, and deadlock should be avoided. Sharing is caring, so Bounded Waiting must be implemented to eliminate famine.
The Critical Section Problem can be solved with software, hardware or higher level software abstractions like semaphores and monitors.
avoidance, prevention, allowing deadlocks then detection +
recovery, ignoring the problem and pretending that deadlocks
never occur in the system, recovery strategies.
Implements a FIFO circular buffer, but entires have a use bit. The pointer skips an entry and turns the ‘use’ bit off if the use bit is present when attempting to replace a frame.
Interesting experiments that occur as a result of knowledge gained in the classroom will be documented here, if any are completed.
Footnotes are used by placing [^ref] where a superscript number should be placed, and [^ref]: explanation can be used in-place or at the end of the document. All referenced footnotes will be collected and placed at the end of the document.
More info.
↩︎
linux.die.net,
fsck
- check and repair a Linux file system ↩︎
CSI3131 Slides - Module 1 - Computer Systems Overview ↩︎
Thrashing - When the CPU is trying to process too many programs simultaneously, and constant context switching and swapping prevents any real work from being completed. ↩︎