Operating Systems and Basics

OS is system software, which may be viewed as collection of software consisting of procedures for operating the computer & providing an environment for execution of programs. It’s an interface between user & computer.

Types of Processing:

1. Serial Processing
2. Batch Processing
3. Multiprogramming.

Types of OSs:

1. Batch OS
2. Multiprogramming OS

Ø Multitasking/Multiprocessing
Ø Multiuser OS
Ø Time Sharing OS
Ø Real Time OS

3. Network OS
4. Distributed OS

OS Structure:

1. Layered Structure

2. Kernel Structure

Ø Create & Delete process

Ø Processor scheduling, mem mgmt & I/O mgmt.

Ø Process synchronization.

Ø IPC help

3. Virtual Machine

4. Client Server model

Process Management

Process Status: New, ready to run, running, suspended, sleep, wait, terminate.

Types of Scheduler:

1. Long term/Job Scheduler
2. Medium term/
3. Short term/ CPU Scheduler
Processes can be either CPU bound or I/O bound.

Scheduling performance criteria:

CPU utilisation

Throughput
Turnaround time
Waiting time
Response Time

Scheduling Algorithms:

Preemptive
First-come-first served

Non-Preemptive

Shortest-job-first
Round Robin.
Priority based scheduling
Multi-level Queue

Processing the interrupt to switch the CPU to another process requires saving all the registers for the old process & then loading the registers for new process is known as Context Switching.

Synchronization & IPC

The shared storage may be in main memory or it may be a shared file. Each process has a segment of code, critical Section, which accessed shared memory or files. Some way of making sure that if one process is executing in its critical section, other process will be excluded from doing the same thing is known as Mutual Exclusion. Hardware support is available for mutual exclusion called “Test & set instruction”, it is designed to allow only one process among several concurrent processes to enter in its critical section.

Semaphore: It’s a synchronization tool, it’s a variable which accepts non-negative integer values and except for initialization may be accessed and manipulated through two primitive functions wait() & signal().

Disadvantages :

1. Semaphores are unstructured.
2. Semaphores do not support data abstraction.

Alternative to Semaphores:

1. Critical region
2. Conditional critical region
3. Monitors
4. Message Passing

Reason for Deadlock:

1. Mutual exclusion
2. Hold & wait
3. No preemption
4. Circular condition.

Memory Management

In a single process, system memory is protected through hardware mechanism such as dedicated register called Fence register.

In a multi programming, memory can be allocated either Statically or Dynamically. Partition information is stored in partition Description Table. Two strategies are used to allocate memory to ready process are First Fit & Best Fit.

Loading program into memory by relocating load or linker in a static allocation is known as Static relocation. In Dynamic method, run time mapping of virtual address into physical address with support of some hardware mechanism such as base register & limit registers. Protection is served by using Limit registers to restrict the program to access memory location, sharing is achieved by using dedicated common partition.

Static allocation does not support data structures like stack & queues. It limits degree of multi programming.

Compaction is a process of collecting free space in to a single large memory chunk to fit the available process. It is not done, bcoz it occupies lot of CPU time. It is only supported in Mianframe & SuperComputers

Paging is a memory management technique that permits a program’s memory to be non-contiguous into physical memory, thus allowing a program to be allocated physical memory whenever is required. This is done by Virtual Address, later these address are converted to physical address.

Memory is divided into number of fixed size blocks called Frames. The virtual address space or logical memory of a process is also broken into blocks of the same size called pages. When a program is to be run, its pages are loaded into any frame from the disk. Mapping is done thru Page Map Table which contains the base address of each page in physical memory. Hardware support is given to paging using Page Map Table Register (PMRT) which will be pointing to beginning of the PMT. Look side memory or Content addressable memory is used to overcome the problem of PMT.

Address translation is done by Associative Memory which will convert virtual to physical address by page & offset values by looking into PMT.

Segmentation is Memory management scheme its sophisticated form Address translation. It is done by Segment table, which is a important component in segmented system. Segment accessing supported by Segment Table Base register (STBR). Protection is enforced by Segment table Limit register (STLR).

Virtual memory is memory management technique which splits the process into small chunks called Overlay. First overlay will can next overlay before quitting the CPU, the remaining overlays will be on Hard disk, the swapping is done by OS. Advantages:

1. What ever the size program, memory can be allocated easily.
2. Since the swapping is done between main & secondary memory, the CPU utilization & throughput will be increased.
3. It reduces the external fragmentation & Increases the program execution speed.

In Demand paging, pages are loaded only on demand, not in advance, its same as paging with swapping feature.

Page fault occurs due to missing of page in the main memory, it means that the program is referring the address of the page which is not brought into memory.

File Management

Some systems support a single uniform set of file manipulation features for both file & I/O device management, this feature is known as Device Independent I/O or Device Independence. Printer is a one of a such example.

File organization may be

1. Byte Sequenced in which OS does not impose any structure on the file organization.

2. Record Sequenced, it’s a sequence of fixed sized records, arbitrary records read or written, but records can’t be inserted or deleted in middle of the file.

3. ISAM files are inserted in disc blocks which will have keys to inserted, its look like a tree of blocks.,

Responsibility of File Management.

1. Mapping of logical file address to physical disk address
2. Management of disk space & allocation - deallocation.
3. Keeping track of all files in system
4. Support for protection & sharing of files.

Method to access the file organized in hierarchical form. Absolute pathname & relative pathname. File & directory searching is done using

1. Linear List organization which takes O(n) comparisons to locate a file.
2. Hashing Technique
3. Balanced binary tree which takes O(log n) comparisons to locate file, it always provides sorted list files which will increase the efficiency.

Collection of tracks on all surfaces that are at the same distance is called a Cylinder.

Disk Space Management Methods:

1. Linked list

2. Bit Map

Disk allocation Methods

1. Contiguous: It supports both Sequential & Direct Accessing. Allocation is done using First Fit & Best Fit methods.

2. Linked List

Advantages:
Simple
No disk Compaction.

Disadvantages

It doesn’t support direct accessing since blocks are scattered over the disk.
Slow direct accessing of any disk block
Space requirement for pointers
Reliability

3. Indexed

Uses Index Block to support direct accessing.
Problem with same can be solved by Multiple Level indexing, indirect blocks, double indirect block.

Advantages

No external fragmentation
Efficient random access
Indexing of free space is done with Bitmap
Can keep the index of bad blocks.

Disk Scheduling

1. First come first served (FCFS)

2. Shortest Seek Time First

3. Scan Scheduling also called Elevator Algorithm