OS Crashcourse

OS crash course
What is an Operating System?

• A program that acts as an intermediary
between a user of a computer and the
computer hardware.
• Operating system goals:
– Execute user programs and make solving user problems easier.
– Make the computer system convenient to use.
• Use the computer hardware in an

efficient manner.
Operating System Concepts

Operating System Definitions
• Resource allocator – manages and

allocates resources.
• Control program – controls the
execution of user programs and
operations of I/O devices .
• Kernel – the one program running at all
times (all else being application
programs).
Multiprogrammed Batch Systems
Several jobs are kept in main memory at the same time, and the
CPU is multiplexed among them.

Time-Sharing Systems–Interactive Computing
• The CPU is multiplexed among several jobs that are

kept in memory and on disk (the CPU is allocated to
a job only if the job is in memory).
• A job swapped in and out of memory to the disk.
• On-line communication between the user and the
system is provided; when the operating system
finishes the execution of one command, it seeks the
next “control statement” from the user’s keyboard.
• On-line system must be available for users to access
data and code.

Computer-System Operation
• I/O devices and the CPU can execute concurrently.
• Each device controller is in charge of a particular
device type.
• Each device controller has a local buffer.
• CPU moves data from/to main memory to/from
local buffers
• I/O is from the device to local buffer of controller.
• Device controller informs CPU that it has finished
its operation by causing an interrupt.
Dual-Mode Operation (Cont.)
• Mode bit added to computer hardware to indicate the current
mode: monitor (0) or user (1).
• When an interrupt or fault occurs hardware switches to
monitor mode.
Interrupt/fault
monitor user
set user mode
Privileged instructions can be issued only in monitor mode.

Memory Protection
• Must provide memory protection at least for the
interrupt vector and the interrupt service routines.
• In order to have memory protection, add two
registers that determine the range of legal
addresses a program may access:
– Base register – holds the smallest legal physical
memory address.
– Limit register – contains the size of the range
• Memory outside the defined range is protected.

Hardware Address Protection

Hardware Protection
• When executing in monitor mode, the
operating system has unrestricted access to
both monitor and user’s memory.
• The load instructions for the base and limit
registers are privileged instructions.

Common System Components
• Process Management
• Main Memory Management
• File Management
• I/O System Management
• Secondary Management
• Networking
• Protection System
• Command-Interpreter System

Process Management
• A process is a program in execution. A process needs
certain resources, including CPU time, memory, files,
and I/O devices, to accomplish its task.
• The operating system is responsible for the following
activities in connection with process management.
– Process creation and deletion.
– process suspension and resumption.
– Provision of mechanisms for:
• process synchronization
• process communication

Main-Memory Management
• Memory is a large array of words or bytes, each with its
own address. It is a repository of quickly accessible data
shared by the CPU and I/O devices.
• Main memory is a volatile storage device. It loses its
contents in the case of system failure.
activities in connections with memory management:
– Keep track of which parts of memory are currently being used
and by whom.
– Decide which processes to load when memory space becomes
available.
– Allocate and deallocate memory space as needed.

File Management
• A file is a collection of related information defined by

its creator. Commonly, files represent programs (both
source and object forms) and data.
activities in connections with file management:
– File creation and deletion.
– Directory creation and deletion.
– Support of primitives for manipulating files and directories.
– Mapping files onto secondary storage.
– File backup on stable (nonvolatile) storage media.

I/O System Management
• The I/O system consists of:

– A buffer-caching system
– A general device-driver interface
– Drivers for specific hardware devices

Secondary-Storage Management
• Since main memory (primary storage) is volatile and too
small to accommodate all data and programs
permanently, the computer system must provide
secondary storage to back up main memory.
• Most modern computer systems use disks as the principle
on-line storage medium, for both programs and data.
activities in connection with disk management:
– Free space management
– Storage allocation
– Disk scheduling

Networking (Distributed Systems)
• A distributed system is a collection processors that do not share
memory or a clock. Each processor has its own local memory.
• The processors in the system are connected through a
communication network.
• Communication takes place using a protocol.
• A distributed system provides user access to various system
resources.
• Access to a shared resource allows:
– Computation speed-up
– Increased data availability
– Enhanced reliability

Protection System
• Protection refers to a mechanism for
controlling access by programs, processes, or
users to both system and user resources.
• The protection mechanism must:
– distinguish between authorized and unauthorized
usage.
– specify the controls to be imposed.
– provide a means of enforcement.

Command-Interpreter System
• Many commands are given to the operating
system by control statements which deal with:
– process creation and management
– I/O handling
– secondary-storage management
– main-memory management
– file-system access
– protection
– networking
Command-Interpreter System (Cont.)
• The program that reads and interprets control

statements is called variously:
– command-line interpreter
– shell (in UNIX)
Its function is to get and execute the next

command statement.

Microkernel System Structure
• Moves as much from the kernel into “user” space.
• Communication takes place between user modules
using message passing.
• Benefits:
- easier to extend a microkernel
- easier to port the operating system to new
architectures
- more reliable (less code is running in kernel mode)
- more secure
Process Concept
• An operating system executes a variety of programs:
– Batch system – jobs
– Time-shared systems – user programs or tasks
• Textbook uses the terms job and process almost
interchangeably.
• Process – a program in execution; process execution
must progress in sequential fashion.
• A process includes:
– program counter
– stack
– data section

Implementing processes by
interleaving the processor

Diagram of Process State

Process Control Block (PCB)

•
Context Switching
Program Counter
• General Purpose register
• Base Register
• Limit register
All together these registers provide a context for
the process to operate on.
In multiprogramming systems, it is necessary to run
a process for a short time and then switch to
another process. This is known as process switching
or context switching.
Before switching the context it is necessary to store
the register values of the previous process and to
load the register values of the incoming process

9. O.S. will figure out who responds to I/O.
10.Now we are in Procedure B which is handling i/o interrupt.
This handling will make process1 ready again.
11.We call dispatcher.
12.The dispatcher is running. The dispatcher decides to restart
process1.
13.The dispatcher reinitializes the system stack and switches to
process 1 with an rti instrcution.
14.We are finally back in process1 after syscall.

Flow
1. Process 1 is of Control
running. It isduring process
using the processswitching
stack.
2. Process 1 executes a syscall instruction to do some i/o. We
switch to system mode and system stack.
3. O.S. calls Procedure A to handle syscall.
4. When the work of Procdure A is completed we call the
dispatcher.
5. The dispatcher selects process 2 to restart.
6. Rti instruction switches to user mode and jumps to process
2. The system stack pointer is reinitaialized so it is empty.
7. We are running inside process 2. Eventually after completion
of i/o an i/o interrupt will occur.
8. The i/o interrupt switches computer to system mode and
enters O.S. Contd.

Schedulers
• Long-term scheduler (or job scheduler)

– selects which processes should be
brought into the ready queue.
• Short-term scheduler (or CPU scheduler)
– selects which process should be
executed next and allocates CPU.
• Medium term scheduler- swap in swap
out

Process Creation
• Parent process create children processes, which, in
turn create other processes, forming a tree of
processes.
• Resource sharing
– Parent and children share all resources.
– Children share subset of parent’s resources.
– Parent and child share no resources.
• Execution
– Parent and children execute concurrently.
– Parent waits until children terminate.
Process Creation (Cont.)
• Address space
– Child duplicate of parent.
– Child has a program loaded into it.
• UNIX examples
– fork system call creates new process
– exec system call used after a fork to replace the
process’ memory space with a new program.

Cooperating Processes
• Independent process cannot affect or be
affected by the execution of another process.
• Cooperating process can affect or be affected by
the execution of another process
• Advantages of process cooperation
– Information sharing
– Computation speed-up
– Modularity
– Convenience
Interprocess Communication (IPC)
• Mechanism for processes to communicate and to synchronize their
actions.
• Message system – processes communicate with each other without
resorting to shared variables.
• IPC facility provides two operations:
– send(message) – message size fixed or variable
– receive(message)
• If P and Q wish to communicate, they need to:
– establish a communication link between them
– exchange messages via send/receive
• Implementation of communication link
– physical (e.g., shared memory, hardware bus)
– logical (e.g., logical properties)

Buffering
• Queue of messages attached to the link;
implemented in one of three ways.
1.Zero capacity – 0 messages
Sender must wait for receiver (rendezvous).
2.Bounded capacity – finite length of n messages
Sender must wait if link full.
3.Unbounded capacity – infinite length
Sender never waits.

CPU Scheduler
• Selects from among the processes in memory that are
ready to execute, and allocates the CPU to one of them.
• CPU scheduling decisions may take place when a
process:
1.Switches from running to waiting state.
2.Switches from running to ready state.
3.Switches from waiting to ready.
4.Terminates.
• Scheduling under 1 and 4 is nonpreemptive.
• All other scheduling is preemptive.

Dispatcher
• Dispatcher module gives control of the CPU to
the process selected by the short-term scheduler;
this involves:
– switching context
– switching to user mode
– jumping to the proper location in the user program to
restart that program
• Dispatch latency – time it takes for the dispatcher
to stop one process and start another running.

Scheduling Criteria
• CPU utilization – keep the CPU as busy as possible
• Throughput – # of processes that complete their
execution per time unit
• Turnaround time – amount of time to execute a
particular process
• Waiting time – amount of time a process has been
waiting in the ready queue
• Response time – amount of time it takes from when a
request was submitted until the first response is
produced, not output (for time-sharing environment)

First-Come, First-Served (FCFS) Scheduling
Process Burst Time

P1 24
P2 3
P3 3
• Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3
0 24 27 30
• Waiting time for P1 = 0; P2 = 24; P3 = 27

• Average waiting time: (0 + 24 + 27)/3 = 17

FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order
P2 , P3 , P1 .
• The Gantt chart for the schedule is:
P2 P3 P1
0 3 6 30
• Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3
• Much better than previous case.
• Convoy effect short process behind long process

Shortest-Job-First (SJR) Scheduling
• Associate with each process the length of its next CPU burst.
Use these lengths to schedule the process with the shortest
time.
• Two schemes:
– nonpreemptive – once CPU given to the process it cannot be
preempted until completes its CPU burst.
– preemptive – if a new process arrives with CPU burst length less
than remaining time of current executing process, preempt. This
scheme is know as the
Shortest-Remaining-Time-First (SRTF).
• SJF is optimal – gives minimum average waiting time for a
given set of processes.

Example of Non-Preemptive SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (non-preemptive)
P1 P3 P2 P4
0 3 7 8 12 16
• Average waiting time = (0 + 6 + 3 + 7)/4 - 4

Example of Preemptive SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (preemptive)
P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16
• Average waiting time = (9 + 1 + 0 +2)/4 - 3

Determining Length of Next CPU Burst
• Can only estimate the length.

• Can be done by using the length of previous
CPU1.bursts, using
t  actual lenght
n of nexponential
th
CPU burst averaging.
2.  n 1  predicted value for the next CPU burst
3.  , 0    1
4. Define :
 n1   tn  1    n .

Prediction of the Length of the Next CPU Burst

Examples of Exponential Averaging
•  =0
– n+1 = n
– Recent history does not count.
•  =1
– n+1 = tn
– Only the actual last CPU burst counts.
• If we expand the formula, we get:
n+1 =  tn+(1 - )  tn -1 + …
+(1 -  )j  tn -1 + …
+(1 -  )n=1 tn 0
• Since both  and (1 - ) are less than or equal to 1, each
successive term has less weight than its predecessor.

Priority Scheduling
• A priority number (integer) is associated with each process
• The CPU is allocated to the process with the highest priority
(smallest integer  highest priority).
– Preemptive
– nonpreemptive
• SJF is a priority scheduling where priority is the predicted
next CPU burst time.
• Problem  Starvation – low priority processes may never
execute.
• Solution  Aging – as time progresses increase the priority of
the process.

Round Robin (RR)
• Each process gets a small unit of CPU time (time quantum),
usually 10-100 milliseconds. After this time has elapsed, the
process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time
quantum is q, then each process gets 1/n of the CPU time in
chunks of at most q time units at once. No process waits more
than (n-1)q time units.
• Performance
– q large  FIFO
– q small  q must be large with respect to context switch, otherwise
overhead is too high.

Example of RR with Time Quantum = 20
Process Burst Time

P1 53
P2 17
P3 68
P4 24
• The Gantt chart is:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
• Typically, higher average turnaround than SJF, but better response.

Single and Multithreaded Processes

Benefits
• Responsiveness
• Resource Sharing
• Economy
• Utilization of MP Architectures

Bounded-Buffer
• Shared data
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

Bounded-Buffer
• Producer process
item nextProduced;
while (1) {
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}

Bounded-Buffer
• Consumer process
item nextConsumed;
while (1) {
while (counter == 0)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}

Bounded Buffer
• The statements
counter++;
counter--;
must be performed atomically.
• Atomic operation means an operation that

completes in its entirety without interruption.

Bounded Buffer
• The statement “count++” may be implemented in machine
language as:
register1 = counter
register1 = register1 + 1
counter = register1
• The statement “count—” may be implemented as:
register2 = counter
register2 = register2 – 1
counter = register2

Bounded Buffer
• If both the producer and consumer attempt to
update the buffer concurrently, the assembly
language statements may get interleaved.
• Interleaving depends upon how the producer

and consumer processes are scheduled.

Bounded Buffer
• Assume counter is initially 5. One interleaving of statements is:
producer: register1 = counter (register1 = 5)

producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter (register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)
• The value of count may be either 4 or 6, where the correct

result should be 5.

Race Condition
• Race condition: The situation where several
processes access – and manipulate shared
data concurrently. The final value of the
shared data depends upon which process
finishes last.
• To prevent race conditions, concurrent

processes must be synchronized.

The Critical-Section Problem
• n processes all competing to use some
shared data
• Each process has a code segment, called
critical section, in which the shared data is
accessed.
• Problem – ensure that when one process is
executing in its critical section, no other
process is allowed to execute in its critical
section.

Algorithm 3
• Combined shared variables of algorithms 1 and 2.
• Process Pi
do {
flag [i]:= true;
turn = j;
while (flag [j] and turn = j) ;
critical section
flag [i] = false;
remainder section
} while (1);
• Meets all three requirements; solves the critical-section
problem for two processes.

Bakery Algorithm
Critical section for n processes
• Before entering its critical section, process

receives a number. Holder of the smallest
number enters the critical section.
• If processes Pi and Pj receive the same
number, if i < j, then Pi is served first; else Pj is
served first.
• The numbering scheme always generates
numbers in increasing order of enumeration;
i.e., 1,2,3,3,3,3,4,5...
Bakery Algorithm
• Notation < lexicographical order (ticket #, process id
#)
– (a,b) < c,d) if a < c or if a = c and b < d
– max (a0,…, an-1) is a number, k, such that k  ai for i - 0,
…, n – 1
• Shared data
boolean choosing[n];
int number[n];
Data structures are initialized to false and 0
respectively
Bakery Algorithm
do {
choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n – 1])+1;
choosing[i] = false;
for (j = 0; j < n; j++) {
while (choosing[j]) ;
while ((number[j] != 0) && (number[j,j] < number[i,i])) ;
}
critical section
number[i] = 0;
remainder section
} while (1);

Synchronization Hardware
• Test and modify the content of a word atomically
.
boolean TestAndSet(boolean &target) {
boolean rv = target;
tqrget = true;
return rv;
}

Mutual Exclusion with Test-and-Set
• Shared data:
boolean lock = false;
• Process Pi
do {
while (TestAndSet(lock)) ;
critical section
lock = false;
remainder section
}
Semaphores
• Synchronization tool that does not require busy waiting.
• Semaphore S – integer variable
• can only be accessed via two indivisible (atomic)
operations
wait (S):
while S 0 do no-op;
S--;
signal (S):
S++;

Critical Section of n Processes
• Shared data:
semaphore mutex; //initially mutex = 1
• Process Pi:
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (1);

Semaphore Implementation
• Define a semaphore as a record
typedef struct {
int value;
struct process *L;
} semaphore;
• Assume two simple operations:

– block suspends the process that invokes it.
– wakeup(P) resumes the execution of a blocked process P.

Semaphore Implementation
• Define a semaphore as a record
typedef struct {
int value;
struct process *L;
} semaphore;
• Assume two simple operations:

– block suspends the process that invokes it.
– wakeup(P) resumes the execution of a blocked process P.

Implementation
• Semaphore operations now defined as
wait(S):
S.value--;
if (S.value < 0) {
add this process to S.L;
block;
}
signal(S):
S.value++;
if (S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}

Two Types of Semaphores
• Counting semaphore – integer value
can range over an unrestricted
domain.
• Binary semaphore – integer value
can range only between 0 and 1; can
be simpler to implement.
• Can implement a counting
semaphore S as a binary semaphore.

Dining-Philosophers Problem
• Shared data
semaphore chopstick[5];
Initially all values are 1

Critical Regions
• High-level synchronization construct
• A shared variable v of type T, is declared as:
v: shared T
• Variable v accessed only inside statement
region v when B do S
where B is a boolean expression.
• While statement S is being executed, no other process

can access variable v.
Critical Regions
• Regions referring to the same shared variable
exclude each other in time.
• When a process tries to execute the region

statement, the Boolean expression B is
evaluated. If B is true, statement S is executed.
If it is false, the process is delayed until B
becomes true and no other process is in the
region associated with v.
Bounded Buffer Producer Process
• Producer process inserts nextp into the shared
buffer
region buffer when( count < n) {

pool[in] = nextp;
in:= (in+1) % n;
count++;
}

Monitors
• To allow a process to wait within the monitor, a
condition variable must be declared, as
condition x, y;
• Condition variable can only be used with the
operations wait and signal.
– The operation
x.wait();
means that the process invoking this operation is
suspended until another process invokes
x.signal();
– The x.signal operation resumes exactly one suspended
process. If no process is suspended, then the signal
operation has no effect.

Dining Philosophers
void pickup(int i) {
state[i] = hungry;
test[i];
if (state[i] != eating)
self[i].wait();
}
void putdown(int i) {
state[i] = thinking;
// test left and right neighbors
test((i+4) % 5);
test((i+1) % 5);
}

Dining Philosophers
void test(int i) {
if ( (state[(I + 4) % 5] != eating) &&
(state[i] == hungry) &&
(state[(i + 1) % 5] != eating)) {
state[i] = eating;
self[i].signal();
}
}

Binding of Instructions and Data to Memory
Address binding of instructions and data to memory addresses can

happen at three different stages.
• Compile time: If memory location known a priori,

absolute code can be generated; must recompile
code if starting location changes.
• Load time: Must generate relocatable code if
memory location is not known at compile time.
• Execution time: Binding delayed until run time if
the process can be moved during its execution
from one memory segment to another. Need
hardware support for address maps (e.g., base and
limit registers).
Multistep Processing of a User Program

Logical vs. Physical Address Space
• The concept of a logical address space that is bound to a
separate physical address space is central to proper
memory management.
– Logical address – generated by the CPU; also referred to as
virtual address.
– Physical address – address seen by the memory unit.
• Logical and physical addresses are the same in compile-

time and load-time address-binding schemes; logical
(virtual) and physical addresses differ in execution-time
address-binding scheme.
Memory-Management Unit (MMU)
• Hardware device that maps virtual to physical
address.
• In MMU scheme, the value in the relocation

register is added to every address generated by
a user process at the time it is sent to memory.
• The user program deals with logical addresses; it

never sees the real physical addresses.
Dynamic relocation using a relocation register

Dynamic Loading
• Routine is not loaded until it is called
• Better memory-space utilization; unused
routine is never loaded.
• Useful when large amounts of code are needed
to handle infrequently occurring cases.
• No special support from the operating system is
required implemented through program design.

Dynamic Linking
• Linking postponed until execution time.
• Small piece of code, stub, used to locate the
appropriate memory-resident library routine.
• Stub replaces itself with the address of the
routine, and executes the routine.
• Operating system needed to check if routine is in
processes’ memory address.
• Dynamic linking is particularly useful for libraries.

Contiguous Allocation
• Main memory usually into two partitions:
– Resident operating system, usually held in low memory with
interrupt vector.
– User processes then held in high memory.
• Single-partition allocation
– Relocation-register scheme used to protect user processes from
each other, and from changing operating-system code and data.
– Relocation register contains value of smallest physical address;
limit register contains range of logical addresses – each logical
address must be less than the limit register.

Hardware Support for Relocation and Limit Registers

Contiguous Allocation (Cont.)
• Multiple-partition allocation
– Hole – block of available memory; holes of various size are
scattered throughout memory.
– When a process arrives, it is allocated memory from a hole
large enough to accommodate it.
– Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
OS OS OS OS
process 5 process 5 process 5 process 5

process 9 process 9
process 8 process 10
process 2 process 2 process 2 process 2

Dynamic Storage-Allocation Problem
How to satisfy a request of size n from a list of free holes.
• First-fit: Allocate the first hole that is big enough.

• Best-fit: Allocate the smallest hole that is big enough;
must search entire list, unless ordered by size. Produces
the smallest leftover hole.
• Worst-fit: Allocate the largest hole; must also search
entire list. Produces the largest leftover hole.
First-fit and best-fit better than worst-fit in terms of speed
and storage utilization.

Fragmentation
• External Fragmentation – total memory space exists to satisfy
a request, but it is not contiguous.
• Internal Fragmentation – allocated memory may be slightly
larger than requested memory; this size difference is memory
internal to a partition, but not being used.
• Reduce external fragmentation by compaction
– Shuffle memory contents to place all free memory together in one
large block.
– Compaction is possible only if relocation is dynamic, and is done at
execution time.
– I/O problem
• Latch job in memory while it is involved in I/O.
• Do I/O only into OS buffers.

Paging
• Logical address space of a process can be noncontiguous; process is allocated
physical memory whenever the latter is available.
• Divide physical memory into fixed-sized blocks called frames (size is power of 2,
between 512 bytes and 8192 bytes).
• Divide logical memory into blocks of same size called pages.
• Keep track of all free frames.
• To run a program of size n pages, need to find n free frames and load program.
• Set up a page table to translate logical to physical addresses.
• Internal fragmentation.

Address Translation Architecture

Implementation of Page Table
• Page table is kept in main memory.
• Page-table base register (PTBR) points to the page table.
• Page-table length register (PRLR) indicates size of the page
table.
• In this scheme every data/instruction access requires two
memory accesses. One for the page table and one for the
data/instruction.
• The two memory access problem can be solved by the use
of a special fast-lookup hardware cache called associative
memory or translation look-aside buffers (TLBs)

Paging Hardware With TLB

Effective Access Time
• Associative Lookup =  time unit
• Assume memory cycle time is 1 microsecond
• Hit ratio – percentage of times that a page number is
found in the associative registers; ration related to
number of associative registers.
• Hit ratio = 
• Effective Access Time (EAT)
EAT = (1 + )  + (2 + )(1 – )
=2+–

Two-Level Paging Example
• A logical address (on 32-bit machine with 4K page size) is divided into:
– a page number consisting of 20 bits.
– a page offset consisting of 12 bits.
• Since the page table is paged, the page number is further divided into:
– a 10-bit page number.
– a 10-bit page offset.
• Thus, a logical address is as follows:
page number page offset

pi p2 d
where pi is an index into the outer page table, and p2 is the displacement
10 page10table.
within the page of the outer 12

Two-Level Page-Table Scheme

Address-Translation Scheme
• Address-translation scheme for a two-level 32-bit
paging architecture

Hashed Page Table

Inverted Page Table Architecture

Segmentation
• Memory-management scheme that supports user view of memory.
• A program is a collection of segments. A segment is a logical unit such as:
main program,
procedure,
function,
method,
object,
local variables, global variables,
common block,
stack,
symbol table, arrays

User’s View of a Program

Segmentation Hardware

Example of Segmentation

Background
• Virtual memory – separation of user logical memory from
physical memory.
– Only part of the program needs to be in memory for execution.
– Logical address space can therefore be much larger than
physical address space.
– Allows address spaces to be shared by several processes.
– Allows for more efficient process creation.
• Virtual memory can be implemented via:

– Demand paging
– Demand segmentation

Virtual Memory That is Larger Than Physical Memory

Demand Paging
• Bring a page into memory only when it is needed.
– Less I/O needed
– Less memory needed
– Faster response
– More users
• Page is needed  reference to it

– invalid reference  abort
– not-in-memory  bring to memory

Page Fault
• If there is ever a reference to a page, first reference will trap to
OS  page fault
• OS looks at another table to decide:
– Invalid reference  abort.
– Just not in memory.
• Get empty frame.
• Swap page into frame.
• Reset tables, validation bit = 1.
• Restart instruction: Least Recently Used
– block move
– auto increment/decrement location

Steps in Handling a Page Fault

What happens if there is no free frame?
• Page replacement – find some page in

memory, but not really in use, swap it out.
– algorithm
– performance – want an algorithm which will result
in minimum number of page faults.
• Same page may be brought into memory

several times.

Page Replacement
• Prevent over-allocation of memory by modifying page-
fault service routine to include page replacement.
• Use modify (dirty) bit to reduce overhead of page

transfers – only modified pages are written to disk.
• Page replacement completes separation between

logical memory and physical memory – large virtual
memory can be provided on a smaller physical
memory.
Page Replacement Algorithms
• Want lowest page-fault rate.
• Evaluate algorithm by running it on a
particular string of memory references
(reference string) and computing the number
of page faults on that string.
• In all our examples, the reference string is
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

FIFO Page Replacement

FIFO Illustrating Belady’s Anamoly

Optimal Page Replacement
Replace page that will not be used for longest period of time.

LRU Page Replacement
The page which has been used least recently will be replaced.

LRU Algorithm (Cont.)
• Stack implementation – keep a stack of page
numbers in a double link form:
– Page referenced:
• move it to the top
• requires 6 pointers to be changed
– No search for replacement

Use Of A Stack to Record The Most Recent Page References

LRU Approximation Algorithms
• Reference bit
– With each page associate a bit, initially = 0
– When page is referenced bit set to 1.
– Replace the one which is 0 (if one exists). We do not know the
order, however.
• Second chance
– Need reference bit.
– Clock replacement.
– If page to be replaced (in clock order) has reference bit = 1. then:
• set reference bit 0.
• leave page in memory.
• replace next page (in clock order), subject to same rules.

Second-Chance (clock) Page-Replacement Algorithm

Counting Algorithms
• Keep a counter of the number of references
that have been made to each page.
• LFU Algorithm: replaces page with smallest

count.
• MFU Algorithm: based on the argument that

the page with the smallest count was probably
just brought in and has yet to be used.
Thrashing
• If a process does not have “enough” pages,
the page-fault rate is very high. This leads to:
– low CPU utilization.
– operating system thinks that it needs to increase
the degree of multiprogramming.
– another process added to the system.
• Thrashing  a process is busy swapping pages

in and out.
Thrashing
• Why does paging work?

Locality model
– Process migrates from one locality to another.
– Localities may overlap.
• Why does thrashing occur?
 size of locality > total memory size
Working-Set Model
•   working-set window  a fixed number of page references
Example: 10,000 instruction
• WSSi (working set of Process Pi) =
total number of pages referenced in the most recent  (varies
in time)
– if  too small will not encompass entire locality.
– if  too large will encompass several localities.
– if  =   will encompass entire program.
• D =  WSSi  total demand frames
• if D > m  Thrashing
• Policy if D > m, then suspend one of the processes.

Working-set model

Storage-Device Hierarchy

Caching
• Use of high-speed memory to hold recently-
accessed data.
• Requires a cache management policy.
• Caching introduces another level in storage
hierarchy. This requires data that is
simultaneously stored in more than one level
to be consistent.

Migration of A From Disk to Register

Disk Scheduling
• The operating system is responsible for using hardware efficiently —
for the disk drives, this means having a fast access time and disk
bandwidth.
• Access time has two major components
– Seek time is the time for the disk are to move the heads to the cylinder
containing the desired sector.
– Rotational latency is the additional time waiting for the disk to rotate the
desired sector to the disk head.
• Minimize seek time
• Seek time  seek distance
• Disk bandwidth is the total number of bytes transferred, divided by
the total time between the first request for service and the completion
of the last transfer.

FCFS
Illustration shows total head movement of 640 cylinders.

SSTF (Cont.)

SCAN (Cont.)

C-SCAN (Cont.)

C-LOOK (Cont.)

Selecting a Disk-Scheduling Algorithm
• SSTF is common and has a natural appeal
• SCAN and C-SCAN perform better for systems that place a
heavy load on the disk.
• Performance depends on the number and types of requests.
• Requests for disk service can be influenced by the file-
allocation method.
• The disk-scheduling algorithm should be written as a separate
module of the operating system, allowing it to be replaced
with a different algorithm if necessary.
• Either SSTF or LOOK is a reasonable choice for the default
algorithm.

Chapter 11: File-System Interface
• File Concept
• Access Methods
• Directory Structure
• File System Mounting
• File Sharing
• Protection

File Structure
• None - sequence of words, bytes
• Simple record structure
– Lines
– Fixed length
– Variable length
• Complex Structures
– Formatted document
– Relocatable load file
• Can simulate last two with first method by inserting appropriate control
characters.
• Who decides:
– Operating system
– Program

File Operations
• Create
• Write
• Read
• Reposition within file – file seek
• Delete
• Truncate
• Open(Fi) – search the directory structure on disk for entry
Fi, and move the content of entry to memory.
• Close (Fi) – move the content of entry Fi in memory to
directory structure on disk.
File Types – Name, Extension

•
Access
Sequential Access
Methods
read next
write next
reset
no read after last write
(rewrite)
• Direct Access
read n
write n
position to n
read next
write next
rewrite n
n = relative block number

Directory Structure
• A collection of nodes containing information about all files.
Directory
Files
F1 F2 F4
F3
Fn
Both the directory structure and the files reside on disk.

Backups of these two structures are kept on tapes.
Information in a Device Directory
• Name
• Type
• Address
• Current length
• Maximum length
• Date last accessed (for archival)
• Date last updated (for dump)
• Owner ID (who pays)
• Protection information (discuss later)
Operations Performed on Directory
• Search for a file
• Create a file
• Delete a file
• List a directory
• Rename a file
• Traverse the file system

Single-Level Directory
• A single directory for all users.
Naming problem
Grouping problem

Two-Level Directory
• Separate directory for each user.
•Path name
•Can have the same file name for different user
•Efficient searching
•No grouping capability

Tree-Structured Directories

Example of Indexed Allocation

Indexed Allocation – Mapping (Cont.)
outer-index
index table file

Free-Space Management (Cont.)
• Bit map requires extra space. Example:
block size = 212 bytes
disk size = 230 bytes (1 gigabyte)
n = 230/212 = 218 bits (or 32K bytes)
• Easy to get contiguous files
• Linked list (free list)
– Cannot get contiguous space easily
– No waste of space
• Grouping
• Counting
Free-Space Management (Cont.)
• Need to protect:
– Pointer to free list
– Bit map
• Must be kept on disk
• Copy in memory and disk may differ.
• Cannot allow for block[i] to have a situation where bit[i] =
1 in memory and bit[i] = 0 on disk.
– Solution:
• Set bit[i] = 1 in disk.
• Allocate block[i]
• Set bit[i] = 1 in memory

Linked Free Space List on Disk

OS Crashcourse

Uploaded by

Copyright:

Available Formats

OS Crashcourse

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

OS Crashcourse

Uploaded by

Copyright:

Available Formats

OS crash course

What is an Operating System?

• Use the computer hardware in an

Operating System Concepts

• Resource allocator – manages and

Operating System Concepts

• The CPU is multiplexed among several jobs that are

Operating System Concepts

Privileged instructions can be issued only in monitor mode.

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

• A file is a collection of related information defined by

Operating System Concepts

• The I/O system consists of:

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

• The program that reads and interprets control

Its function is to get and execute the next

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

• Long-term scheduler (or job scheduler)

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Process Burst Time

• Waiting time for P1 = 0; P2 = 24; P3 = 27

Operating System Concepts

• Waiting time for P1 = 6; P2 = 0; P3 = 3

Operating System Concepts

Operating System Concepts

• Average waiting time = (0 + 6 + 3 + 7)/4 - 4

Operating System Concepts

• Average waiting time = (9 + 1 + 0 +2)/4 - 3

Operating System Concepts

• Can only estimate the length.

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Operating System Concepts

Process Burst Time