The Gateway to Computer Science Excellence


Day Date Contents Slides Assignments
 1  Oct 31 Introduction to Operating System
Process, program, How process works?
Components of process 
fork() call- cloning, parent and child process, example program
 2  Nov 9 Process- process states- New(process starts but not ready for execution- 
waiting for resources), Ready, Running, Blocked, Terminated
Running to ready state- scheduler voluntarily stops a process(preemptive)
Running to blocked- I/O wait
Process Control Block- state, ID, address space pointer, open file descriptor
Address space- stack, heap, data, code
Context switch between processes- things to save- PC, register file, virtual memory info
Cache on context switch- invalidate or add process ID in the cache
Is context switch expensive? - Yes
Speed of memory is 100 times slower but pipelined execution reduces this time
Parallelism inside CPU- given a sequence of instruction execution time 
can't be predicted
context switch- transparent to the user
Threads- light weight process(less switching time)
-Kernel level and user level threads
Assignment 2
Assignment 3
 3  Nov 10 Is a single processor system, is there any advantage of multithreading?- Yes in case 
of IO bound job, but if the process is only CPU bound then there is no advantage
Is the physical memory divided for each OS? No physical memory is RAM and OS 
resides in disk which is independent of the physical memory.
Single CPU with multiple logical cores- SMT- simultaneous multithreading
Long-term - can run complex scheduling algorithms, takes job from disk to the ready queue
Short-term - order in which job executes in CPU
Medium term- swaps in and out jobs from CPU
Dispatcher- After short- term scheduler decides next process dispatcher takes care
 of context switch
CPU Scheduling- Utilization, throughput, turn-around time, waiting time, response time
 4  Nov 11 Process- fork
child process duplicate the parent address space
fflush(stdout)- usage
Will fork work without virtual memory?- Relative addressing works but if absolute addressing
is used both child and parent process writes to same location
How to share data among processes?- Message passing, shared memory-common address
space ensures view serializability
Scheduling algorithms
1. FIFO - easy implementation, convoy effect
2. SRTF- shortest remaining time first- pre-emptive
    SJF- shortest job first- non preemptive
3. Highest response ratio first
4. Round Robin- FCFS, preemptive FIFO
    Time interval increases, response time decreases
5. Priority based
burst time, advantage of preemption
Scheduler sends interrupt to switch processes
 5  Nov 12 Is CPU utilization better for i)preemptive or ii) non-preemptive algorithms?
Not much difference as it depends on the set of processes
SJF- CPU utilisation can be low as at any instant all process are waiting for IO
Virtual Memory- it gives 'VIEW' of very large physical memory
Memory management unit
Virtual Memory- runs a program which is larger than physical memory
Virtual address to physical address mapping
If all the processess are less than main memory is there any use of virtual memory?
In multi-user system - virtual address space is partitioned
Paging- internal fragmentation
Segmentation- external fragmentation
 6  Nov 13 Indexing analogy to paging
In paging no need to store key value in multiple levels as an array(direct index) can be used to 
store physical address pointers.
First level of page table should be in main memory
For paging- page tables and page frame sizes are different
Paging done by OS for itself
Segmentation- variable size segments with base address and limit register
In paging can the page table point to other location than MM?
Yes it can point to disk or I/O devices
What happens when swap space is 0?- Programs larger than physical 
memory cant be run
Cache - in CPU, OS don't care
VM- is it transparent to CPU?- VA generated by CPU
All addresses generated by CPU is logical
How many memory accesses in VM?
one page table lookup(in main memory) and actual memory access
What if there is cache?- only one memory access from TLB(more than 1)
VM cannot be faster than physical addressing
TLB is a small cache in CPU that caches only page table entries
 7  Nov 14 Problems on multi-level paging- number of bits required for addressing next level 
page table/page frame in each of the level
Page table will always be in main memory
Inverted page table- indexed using physical address 
No direct mechanism of sharing of pages
same virtual address present in inverted page table can be distinguished by process id
Page replacement
page fault service
optimal page replacement
FIFO- Belady's anomaly- page fault may increase on increasing number of
frames with same page size
LRU- least recently used page is replaced, 
MRU- most recently used page is replaced,
Random page replacement
8 Nov 15 Paging- multilevel paging, examples- number of address bits used in each level, 
size of page table used in paging, number of levels in paging
9 Nov 19 Cache misses- with examples
Process synchronisation
Critical section problems, solution- mutual exclusion, progress, bounded waiting
Peterson's solution
10 Nov 21 Test and set instruction, mutex, semaphore, 
Test and set satisfying bounded waiting for n processes
priority inversion with example
 11 Nov 22 If mutual exclusion is not satisfied, progress is satisfied?Yes
No starvation implies progress
Deadlock implies starvation
Deadlock- prevention and avoidance
If we prevent deadlock, we avoid deadlock
If we prevent deadlock, we avoid deadlock
Deadlock can be avoided by other means too.
Four conditions of deadlock
1)mutual exclusion-to break share resource 
2)hold and wait, 
3)no preemption, 
4)circular wait
Deadlock implies unsafe state
Unsafe state does not imply deadlock
From safe state process can move to unsafe state if more resources are allocated
Why we need Banker's algorithm?
In resource allocation graph only one instance of a resource can be represented
Example of Banker's algorithm
 12 Nov 23 File system
Disk structure- platters, cylinder, track, sector, read/write head
Disk access time-seek time, rotational latency, transfer time
linear velocity, angular velocity
Files-access methods- sequential and direct, mounting, shortcuts- hardlink, symbolic
File structure- tree structure, acyclic graph(shortcuts), directory- single level, multilevel
File allocation methods- contiguous, linked, indexed
Levels of indirection in indexed file
Disk scheduling algorithms- FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK
RAID- levels
  • 🚩 Edit necessary | 👮 toxicdesire | 💬 “latex code is confusing, edit with proper math symbols for fractions and multiplication”
posted Nov 24, 2018 in Operating System by | 449 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,471 answers
95,274 users