I/O System Management

keep track of which parts of memory are currently being used and by whom
deciding which processes (or parts thereof) and data to move into and out of memory
allocating and deallocating memory space as needed

virtual memory management is an essential part of most operating system

Storage Management

Posted on December 21, 2014 by admin

1. Storage Management

OS provides uniform, logical view of information storage

abstracts physical properties to logical storage unit (file)
each medium is controlled by device (i.e., disk drive, tape drive)

varying properties include access speed, capacity, data-transfer rate, access method (sequential or random)

File system management

files usually organized into directories
access control on most file systems to determine who can access what
OS activities include

creating and deleting files and directories
primitives to manipulate files and dirs
mapping files onto secondary storage
backup files onto stable (non-volatile) storage media

2. Storage-Device Hierarchy

3. Caching

Important principle, performed at many levels in a computer (in hardware, operating system, software)
Information in use copied from slower to faster storage temporarily
Faster storage (cache) checked first to determine if information is there

if it is, information used directly from the cache (first)
if not, data copied to cache and used there

Cache smaller than storage being cached

cache management important design problem
cache size and replacement policy

Process

Posted on December 21, 2014 by admin

1. Definition

Process: a program in execution

process execution must progress in sequential fashion

A program is a passive entity, whereas a process is an active entity with a program counter and a set of associated resources.
Each process has its own address space

Text section (text segment) contains the executable code

the program counter and CPU registers are part of the process context.

Data section (date segment) contains the global variables
Stack contains temporary data (local variables, return addresses…)
A process may contain a heap, which contains memory that is dynamically allocated at run-time

2. OS requirements for processes

OS must interleave the execution of several processes to maximize CPU usage while providing reasonable response time
OS must allocate resources to processes while avoiding deadlock
OS must support inter process communication and user creation of process.

3. A simple implementation of processes

The process index register contains the index into the process list of the currently executing process (B)
A process switch from B to A consist of storing (in memory) B’s context and loading (in CPU registers) A’s context
A data structure that provides flexibility (to add new features)

4. Process Creation

Principal events that cause process creation

system initialization
execution of a process creation system call by a running process
user request to create new process

Parent process creates child processes, which, in turn create other processes, forming a tree (hierarchy) of processes.
Issues

will the parent and child execute concurrently
how will the address space of the child be related to the parent?
will the parent and child share some resources?

5. An example Process

6. Process Creation in Unix

Each process has a process identifier (pid)
The parent executes fork() system call to spawn a child
The child process has a separate copy of the parent’s address space
Both the parent and the child continue execution at the instruction following the fork() system call
Typically, the child executes a system call like execlp() to load a binary file into memory

7. Example program with “fork”

8. Process Termination

process executes lat statement and asks the operating system to delete it (exit)

output data from child to parent (via wait or waitpid)
process’ resources are deallocated by operating system

parent may terminate execution of children processes

e.g., TerminationProcess() in Win32()

process may also terminate due to errors
cascading termination: when a system does not allow a child process to continue after the parent has terminated

9. Process States

Running states
Ready states
Blocked states
New state

os has performed the necessary actions to create process but has not yet admitted the process

Exit state

termination moves the process to this state
tables and other info are temporarily preserved for auxiliary program

10. Swapping/Suspending

Processes may need to be swapped out to disk

this is true even with virtual memory

2 new states

blocked suspend: blocked processes which have been swapped out to disk
ready suspend: ready processes which have been swapped out to disk

11. Process Scheduling

The operating system is responsible for managing the scheduling activities

a uniprocessor system can have only one running process at a time
the main memory cannot always accommodate all processes at run-time
The operating system will need to decide on which process to execute next (CPU scheduling), and which processes will be brought to the main memory (job scheduling)

12. Process Scheduling Queues

Job queue: set of all processes in the system
Ready queue: set of processes residing in the main memory, ready and waiting for CPU
Device queue: set of processes waiting for an I/O device
Process migration is possible among these queues

13. Schedulers

The processes may be first spooled to a mass-storage system, where they are kept for later execution
The long-term scheduler (or job scheduler)

selects processes from this pool and loads them into memory for execution
the long term scheduler, if it exists, will control the degree of multiplexing

The short-term scheduler (or CPU scheduler)

selects from among ready processes, and allocates the CPU to one of them
unlike the long-term scheduler, the short-term scheduler is invoked very frequently

14. CPU and I/O burts

CPU-I/O burst cycle

process execution consist of a cycle of CPU execution and I/O wait

I/O bound process

sends more time doing I/O than computations, many short CPU bursts

CPU-bound process

sends more time doing computation, few very long CPU bursts

Instruction Execution

Posted on December 21, 2014 by admin

1. Instruction Execution

While executing a program, the CPU

fetches the next instruction from memory (loading into IR)
decodes it to determine its type and operands
executes it

May take multiple clock cycles to execute an instruction
Example:

LOAD R1, #3
LOAD R2, M2
STORE M3, R4
ADD R1, R2, R3

Each CPU has a specific set of instructions that it can execute (instruction-set architecture)

2. Registers

General registers (data/address)
Program Counter (PC): contains the memory address of the next instruction to be fetched
Stack Pointer (PC): points to the top of current stack in memory. T

the stack contains one frame for each procedure that has been entered but not yet exited

Program Status Word (PSW): contains the condition code bits and various other control bits.
Note: when time multiplexing the CPU, the operating system will often stop the running program to (re)start another one. In these cases, it must save the “state information” (e.g., value of the registers)

3. Computer-System Operation

I/O devices and CPU can execute concurrency
Each device controller has local buffer(s).
CPU moves data from/to main memory to/from local buffers.
I/O is from/to device to/from local buffer of controller
The device driver is special operating software that interacts with the device controller
Typically, the device controller informs CPU that it has finished its operation by causing an interrupt.

4. Instruction Cycle with Interrupts

5. Classes of Interrupts

I/O interrupts: generated by an I/O controller, to signal normal completion of an operation or to signal a variety of error conditions
Timer Interrupts: generated by a timer within the processor. This allows the operating system to perform certain functions on a regular basis.
Hardware Failure Interrupts: generated by a failure (e.g., power failure or memory parity error).
Traps (Software Interrupts): generated by some condition that occurs as a result of an instruction execution

error
user request for an operating system service

6. Interruption Mechanism

Interrupt transfers control to the interrupt service routine generally through the interrupt vector (e.g., Interl) which contains the addresses of all the service routines. (Alternatively, the machine has a status register or cause register that holds the reason for the interrupt – MIPS architecture)
Interrupt Service Routines (ISRs): separate segments of code determine what action should be taken for each type of interrupt
Once the interrupt has been serviced by the ISR, the control is returned to the interrupted program. Need to save the “process state” (register, PC, …) before ISR takes over.

7. Basic Interrupt Processing

the interrupt is issued
processor finishes execution of current instruction
processor signals acknowledgement of interrupt
processor pushes PSW and PC onto control stack
processor loads new PC value through the interrupt vector
ISR saves remainder of the process state information
ISR executes
ISR restores process state information
Old PSW and PC values are restored from the control stack

8. I/O Structure

After I/O starts, control returns to user program only upon I/O completion

wait instruction idles the CPU until the next interrupt
wait loop (contention for memory access)
at most one I/O request is outstanding at a time, no simultaneous I/O processing

After I/O starts, control returns to user program without waiting for I/O completion

system call: request to the operating system to allow user to wait for I/O completion
device-status table contains entry for each I/O device indicating its type address, and state
operating system indexes into I/O devices table to determine device status and to modify table entry to include interrupt

9. Dual-Mode Operation

Operating system must protect itself and all other programs (and their data) from any malfunctioning program
Provide hardware support to differentiate between at least two modes of operations

user mode: execution done on behalf of a user
kernel mode: (also monitor mode or system mode): execution done on behalf of operating system.

Mode bit added to computer hardware to indicate the current mode

kernel: 0
user: 1

When an interrupt occurs hardware switches to kernel mode
Privileged instructions can be issued only in kernel mode

10. Transition form user to kernel mode

Introduction to Operating Systems

Posted on December 21, 2014 by admin

1. What is an Operating System

A program that acts as an intermediary between the user of a computer and the computer hardware
Operating system goals

Convenience: make the computer system convenient to use
Efficiency: Manage the computer system resources in an efficient manner

“The one program running at all times on the computer” is the kernel. Everything else is either a system program or an application program.

2. OS Features needed for multiprogramming

Job Scheduling: must choose the processes that will be brought to memory
Memory Management: must allocate the memory to several jobs
CPU Scheduling: must choose among several jobs ready to run

3. Parallel System

Multiprocessor systems with more than one CPU in close communication
Tightly coupled system

processors share memory and a clock;
communication usually takes place through the shared memory

Advantage of parallel system

increased throughput
economy of scale
increased reliability

4. Distributed Systems

Distributed the computation among several physical processors
Loosely coupled system

each processor has its own local memory
processors communicate with one another through various communication lines

Advantage of distributed systems

resource and load sharing
reliability
communications

Average Age of Renewal Process

Posted on December 12, 2014 by admin

1. Definition

Let $S_n$ be the n-th renewal
Then $S_{N(t)}$ = time of the last renewal (prior to time t)
Let $A(t) = t - S_{N(t)}$

$A(t)$ is called the age of the renewal process
Interpretation: A(t) is the time since last renewal

2. Average Age of Renewal Process

What is $R_n$ ? $R_n = int^{S_n}_{S_{n-1}} A(t) dt$
$R_n$ is the area under the curve for one cycle
so $E(R_n)) = E[(X_n)^2/2] = E[X^2_n]/2$
Thus the long-run average of the process is

$frac{E[R_n]}{E[X_n]} = frac{E[X^2_n]}{2E[X_n]}$

Renewal-Reward Process

Posted on December 11, 2014 by admin

1. Definition

let $N(t)$ be a renewal process
Let $R_n$ = reward earned at $n$ -th renewal
Assume $R_n$ are i.i.d, but can depend on $X_n$ (length of the $n$ -th cycle)

Then $R(t) = sum^{N(t)}_{n=1} R_n$ is a renewal reward process.

Intuitive explanation: $R(t)$ = cumulative reward earned up to time t

2. Renewal Reward Theorem

Proposition 7.3

$lim_{t to infty} frac{R(t)}{t} = frac{E[R_n]}{E[X_n]}$
$lim_{t to infty} frac{E[R(t)]}{t} = frac{E[R_n]}{E[X_n]}$

Provided $E[R_n] < infty, E[X_n] < infty$

3. Example: Inventory Problem

Problem:

Solution:

Reversible Markov Chain

Posted on December 11, 2014 by admin

1. Definition

Let $X_1, X_2, cdots$ be a Markov chain with transition probabilities $P_{ij}$ .

$P_{ij} = Pr{X_{n+1} = j| X_n = i}$

E.g. A sample realization is 1, 2, 3, 4, 5

Let $X_n, x_{n-1}, cdots$ be the same sequence in reverse, i.e. $cdots, 5, 4, 3, 2, 1, cdots$

Let $Q_{ij}$ be the transition probabilities of the reversed process. That is
$Q_{ij} = Pr{X_{n-1} = j |X_n = i}$
= $frac{Pr{X_{n-1} =j, X_n = i}}{Pr{X_n = i}}$
= $frac{Pr{X_{n-1} = j} Pr{X_n =i | X_{n-1} = j}}{Pr{X_n = i}}$
= $frac{Pr{X_{n-1} = j} P_{ji}}{Pr{X_n = i}}$

2. Conclusion

In the steady state, assuming the limiting probabilities exist, we have
$Q_{ij} = frac{pi_j P_{ji}}{pi_i}$ or $pi_i Q_{ij} = pi_j Q_{ji}$

The above equation is saying that the rate of transmissions from i to j in the reversed chain is equal to the rate of transitions from j to i in the forward chain.

A DTMC is time reversible if $Q_{ij} = P_{ij}$

Lisa Tech Blog

My security road

Monthly Archives: December 2014

I/O System Management

File Management

Memory Management

Storage Management

Process

Instruction Execution

Introduction to Operating Systems

Average Age of Renewal Process

1. Definition

2. Average Age of Renewal Process

Renewal-Reward Process

1. Definition

2. Renewal Reward Theorem

3. Example: Inventory Problem

Reversible Markov Chain

1. Definition

2. Conclusion