Introduction, 4 structural elements of a computer, top-level view of computer components, MAR, MBR, Address register, Buffer register, Processor registers, user-visible registers, index register, segment register, base address and offset, stack pointer, control and status register, program counter, Instruction register, flags or condition codes, interrupt registers, instruction execution, instruction cycle - fetch and execute stage, opcode, accumulator, I/O function, Interrupts, program control flow with and without interrupts, interrupt handler routine, short i/o wait, long i/o wait, interrupt processing.
Introduction, command line interpreter, GUI, CLI (Command Line Interface), RUNCOM, Multics Shell, BASH, CSH, KSH, TCSH, COMMAND.COM, echo $SHELL to get the current shell, Basic command line editing, command and file completion, getting help in Linux, info, man, --help, -h, The UNIX/Linux philosophy, How do I use the shell?, shell scripting, shell keywords, shell commands, Why shell scripting, the bash shell, type command, 'hello world' script, echo $?, shebang, #!, shell comments, debugging a script, set command, /etc/init.d directory, variables in shell, environment variables, printf command, user defined variables, sample code, export variables, unset command, getting user input via keyboard, IFS variable (internal field separator), handling multiple values using read, performing arithmetic operations, creating an integer variable, creating constant variables, variable existence check, path name expansion, using aliases, script execution order, adding color to prompt, PROMPT_COMMAND variable, setting shell options, Exercises 1 - 5, conditional execution, test command, if structure, if..else..fi, nested ifs, multilevel if-then-else, exist status of a command, conditional execution - logical AND, OR, /etc/shadow, Logical Not, conditional expression, string comparison, file attributes comparison, shell command line parameters, difference between $@ and $*, exit command, case statement.
Introduction, what is a process?, Process Control Block (PCB), simplified structure of a PCB, Typical elements of a PCB, Process trace, dispatcher, program counter, 2 state process model, 5 state process model, single-blocked queue, multiple-blocked queue, 6-state process model, 7-state process model, OS control tables, memory tables, I/O tables, file tables, process tables, Process control structures, Program Status Word (PSW), EFLAGS register, Process List structures, Process Modes, Process status register (PSR), Current Privilege level (CPL), Interrupt Return (IRT), Processor creation, Processor switching, when to switch processes?, clock interrupts, I/O interrupt, memory fault, trap, supervisor call, difference between mode switching and process switching, the init process, daemon process, systemd, upstart, pidof, runlevel, killall, pgrep, top, ps, process creation and fork, fork sample code, execlp, process segments, elf (Executable and Linkable format), readelf, pages (4KB), fork-exec combination, SIGCHLD, process overlaying, close-on-exec, spawn(), race conditions, zombie process, orphan process, wait system call, predict the output of the following fork program, fork bomb, exec system call, unistd.h, execle, execve, errno, process termination, abort, SIGKILL, cascading termination, cooperating processes, producer consumer problem, bounded-buffer version.
Introduction to signal handling, asynchronous notification, default singnal handler, sending signals, kill, raise, SIGFPE, SIGSEGV, SIGPIPE, handling signals, signal() system call, SIGKILL, SIGSTOP, SIG_IGN, SIG_DFL, SIGTSTP, SIGQUIT, Ctrl+\, SIGQUIT, SysRq, SIGABRT, assert(), program trying to ignore SIGABRT, throwing signal to itself, abort(), SIGFPE, division by zero, floating point exception, SIG_DFL, default signal handler, kill system call, INT_MIN, limits.h, SIGILL - illegal instruction, zombie process, init process, SIGTERM, default signal for the kill command is TERM, SIGSTOP, SIGCONT, SIGSEGV - for improper memory handling, SIGALRM, alarm(), sample code, implementing sleep() function, SIGCHLD, other signals, APCs in Windows.
Introduction, long-term, short-term and medium-term schedulers, 7-state process model, levels of scheduling, queueing diagram for scheduling, long-term scheduler, process-bound and I/O-bound processes, CPU-I/O Burst cycles, preemptive and non-preemptive scheduling, dispatch latency, scheduling algorithms, turnaround time, waiting time, response time, throughput, scheduling criteria, priority based scheduling, priority queueing, first-come-first-serve (FCFS), Round-robin, Shortest-process-next (SPN), Shortest-remaining-time (SRT), Highest response ratio next (HRRN), Feedback, virtual round robin, multilevel queue scheduling, feedback based scheduling, multilevel feedback queue.
Multiprogramming, multiprocessing, distributed processing, mutual exclusion, busy waiting, principle of concurrency, atomic operation, critical section, deadlock, race condition, starvation, a simple example, another example, bounded-buffer producer consumer problem, race condition - final result depends on the order of execution of instructions, critical section problem, entry-section, critical-section, exit-section, remainder-section, why not disable the interrupt?, lock variables, strict alternation, peterson's solution, multi-process solution, bakery algorithm by Leslie Lamport, synchronization hardware, test-and-set-lock instruction, swap/XCHG instruction, compare-and-swap instruction, properties of machine instruction approach, spinlock, sleep and wakeup, semaphore by Dijkstra, library analogy for semaphores, p and v operations, wait(), signal(), strong semaphore, weak semaphore, deadlocks and starvation while using semaphores, binary and counting semaphores, solving bounded-buffer producer-consumer problem using semaphores, reader-writer problem -- a classical example of multi-process synchronization problem, readers' preference, dining philosopher's problem, waiter solution, creating semaphores in Linux, sem_t, sem_init, sem_wait, sem_post, sem_getvalue, sem_destroy, C program for producer-consumer problem, exercises.
Introduction, light-weight process, difference between threads and processes, thread states - spawn, block, unblock, finish, user-level and kernel-level threads, thread library, advantages and disadvantages of user-level threads, POSIX Pthreads, Mach C-threads, advantages and disadvantages of kernel level threads, combined approach, multithreading models - many-to-one, one-to-one, many-to-many, POSIX threads, sample program, pthread_create, handling thread IDs, pthread_self(), gettid(), pthread with mutex, pthread_mutex_t, can thread really speed up execution?, sample code - primality testing, clone() system call, sys_clone(), fork(), exit(), Linux threads, Linux Process/thread model -- interruptible & uninterruptable, zombie, ready, executing, stopped, sample code, sending signal to a specific thread, pthread_kill(), sample code, thread pool - faster to service a request, limits the number of threads, java threads, one-to-one thread model in Windows, pthread_yield(), sample code, difference between pthread_yield() and sleep().
Threads and processes, Kernel threads, context switch, user space threads, fibers, GNU Pth, advantages and disadvantages of fibers, NPTL (Native Posix Thread Library), LinuxThreads, POSIX Thread Trace Tool (PTT), clone(), pthread_crate(), how to implement user level threads in Linux, getcontext() and setcontext(), makecontext() and swapcontext(), setjmp and longjmp, hybrid model, implementing kernel level threads in linux, how efficients are threads in Linux, why not a hybrid kernel_space/user_space implementation?, clone and fork, mprotect(), wait(), CLONE_THREAD flag, pthread_join() blocking call, C++ multi-threading performance on indepedent data, cache performance and threading, L1 and L2 shared per core (usually) but L3 is not, guidelines for converting single threaded code to multi-threaded, CPU cache intro, ITLB & DTLB caches, replacement policies, cache entry structure, multi-core caches, False sharing in multi-threaded programming, grouping of cache-lines (64 or 128 bytes), Cache coherence protocol - MESI (Modified, Exclusive, Shared & Invalid), write-through and write-back policies, MESI state diagram, false-sharing scenarios (no padding & no spacing, no padding but spacing, padding but no spacing, padding & spacing), solution to false sharing. detection of false-sharing in Visual Studio.
Introduction, joint progress diagram, execution paths, reusable and consumable resources, dealing with deadlocks - prevention, avoidance and detection, resource allocation graphs, necessary and sufficient conditions for deadlock, circular wait, mutual exclusion, hold-and-wait, no preemption, methods for handling deadlocks, deadlock prevention, deadlock avoidance, safe state, safe sequence, resource allocation graph algorithm, Banker's algorithm by Dijkstra, limitations of Banker's algorithm, examples, deadlock detection and recovery - single instance and multiple instance of resources, when to use the detection algorithm, recovery from deadlock - using process termination and preemption, selecting the victim, rollback.
Introduction, memory hierarchy, job of a memory manger, mono-programming, multiprogramming with fixed partitions, internal fragmentation, relocation and protection, hardware support for relocation, dynamic partitioning, external fragmentation, memory compaction, placement algorithm, best-fit, first-fit and next-fit, 50-percent rule, swapping & virtual memory, overlaying, loading and linking, dynamic run-time linking, loading, absolute loading, relocatable loading, dynamic run-time loading, linking, linkage editor, dynamic linker, DLL hell, dlfcn.h, paging, frames, frame-number & offset, page size as a power of 2, mapping logical to physical address, segmentation, user's view of a program, segment numer & offset, segmentation hardware, example of segmentation.
Introduction to Virtual Memory, relationship between pages addressed by virtual address and the frames in physical memory, page table, page table entry (PTE), 'a process may be larger than all of the memory', simple paging & virtual memory paging, simple segmentation and virtual memory segmentation, locality and virtual memory, thrashing, principle of locality, paging behavior, goals of virtual memory, virtual memory using paging, each process has its own page table, present and modify bit, frame number, control bits, address translation on a paging system, page table base register, 'page tables are subjected to paging just as other pages are', two-level hierarchical page table, address translation of two-level paging system, forward-mapped page table, inverted page table, hash table, hash anchor table, scatter index, hash table index, translation lookaside buffer (TLB), TLB hit & miss, flowchart representing the operation of a paging and TLB, page fault interrupt, principle of locality, associative mapping, direct vs associative lookup of PTEs, address-spcae identifiers (ASIDs), cache system, TLB and cache system, how to decide the size of a page?, page fault, resident set (W), 'page size is a hardware design decision', virtual memory using segmentation, segment table, virtual memory scheme based on segmentation, modify/dirty bit, control bits, combined paging and segmentation, segment number and offset, page number and offset, virtual address format, OS policies for virtual memory, fetch policy - demand paging, pure demand paging, locality of reference, swap device (secondary memory), demand segmentation, copy on write scheme, exec(), duplicating pages, fork() & vfork(), prepaging technique, placement policy, replacement policy, Optimal policy, LRU (Least Recently Used), FIFO (First-In-First-Out), Clock algorithm (second chance algorithm), reference/use bit, comparison between the four page replacement algorithms, LFU (Least Frequently Used), MFU (Most Frequently Used), Thrashing - a process spends more time paging than executing, working-set model,page fault frequency (PFF) technique to control thrashing, relation between working set and page fault rate, which processes to suspend when thrashing happens, lower priority process, exercises.
Operating System Concepts
Last Updated: Feb 2019