COM 321 OPERATING SYSTEM II LECTURE NOTES

History and Evolution of operating system

The evolution of operating systems is directly dependent on the development of computer
systems and how users use them. Here is a quick tour of computing systems through the
past fifty years in the timeline.

Operating Systems - Late 1950s

By the late 1950s Operating systems were well improved and started supporting following
usages:

 It was able to perform Single stream batch processing.

 It could use Common, standardized, input/output routines for device access.
 Program transition capabilities to reduce the overhead of starting a new job was added.
 Error recovery to clean up after a job terminated abnormally was added.
 Job control languages that allowed users to specify the job definition and resource
requirements were made possible.

Operating Systems - In 1960s

 1961: The dawn of minicomputers

 1962: Compatible Time-Sharing System (CTSS) from MIT
 1963: Burroughs Master Control Program (MCP) for the B5000 system
 1964: IBM System/360
 1960s: Disks became mainstream
 1966: Minicomputers got cheaper, more powerful, and really useful.
 1967-1968: Mouse was invented.
 1964 and onward: Multics
 1969: The UNIX Time-Sharing System from Bell Telephone Laboratories.

Supported OS Features by 1970s

 Multi User and Multi tasking was introduced.

 Dynamic address translation hardware and Virtual machines came into picture.
 Modular architectures came into existence.
 Personal, interactive systems came into existence.

And as the research and development work continues, we are seeing new operating
systems being developed and existing ones getting improved and modified to enhance the
overall user experience, making operating systems fast and efficient like never before.
Process

1|Page
A process is a sequence of computer instructions executing in an address space, with
access to the operating system services. An address space is an area of main memory
to which the process has exclusive access. The process consists of: the machine code
instructions in main memory, a data area and a stack in main memory, and the CPU’s
registers which the process uses while it is using the CPU.
System Calls
If the process can execute its instructions and read/write its data, but nothing else, how
does it actually do anything useful, like read from a file, get mouse movements etc.?
There needs to be a mechanism to allow a process to ask for
specificservicesfromtheoperatingsystem,withoutcompromisingtheprotected environment
that constrains the process. This is achieved by a special instruction built into the CPU:
the TRAP instruction. A process accesses the service softhe operatingsystem by using
the TRAP instruction, which passesexecution directlyfrom the process to the operating
system. Information placed in the CPU’s registers by the process tells the operating
system what service the process wants. This mechanism of obtaining services via a
TRAP instruction is known asasystemcall.
Eachoperatingsystemhasitsownsetofavailablesystemcalls.
Thesetofavailablesystemcallsisknown asthat operating system’s ApplicationProgram
Interfaceor API.
Process Control Block
There is a Process Control Block for each process, enclosing all the information about the
process. It is a data structure, which contains the following:

 Process State: It can be running, waiting etc.

 Process ID and the parent process ID.
 CPU registers and Program Counter. Program Counter holds the address of the next
instruction to be executed for that process.
 CPU Scheduling information: Such as priority information and pointers to scheduling
queues.
 Memory Management information: For example, page tables or segment tables.
 Accounting information: The User and kernel CPU time consumed, account numbers,
limits, etc.
 I/O Status information: Devices allocated, open file tables, etc.

2|Page
 Context Switching

1. Switching the CPU to another process requires saving the state of the old process
and loading the saved state for the new process. This task is known as a Context
Switch.
2. The context of a process is represented in the Process Control Block (PCB) of a
process; it includes the value of the CPU registers, the process state and memory-
management information. When a context switch occurs, the Kernel saves the context
of the old process in its PCB and loads the saved context of the new process scheduled
to run.
3. Context switch time is pure overhead, because the system does no useful work
while switching. Its speed varies from machine to machine, depending on the memory
speed, the number of registers that must be copied, and the existence of special
instructions(such as a single instruction to load or store all registers). Typical speeds
range from 1 to 1000 microseconds.
4. Context Switching has become such a performance bottleneck that programmers are
using new structures(threads) to avoid it whenever and wherever possible.

Process Synchronization
Process Synchronization means sharing system resources by processes in such a way
that, concurrent access to shared data is handled thereby minimizing the chance of
inconsistent data. Maintaining data consistency demands mechanisms to ensure

3|Page
synchronized execution of cooperating processes. A cooperating process is one that
can affect or be affected by other processes executing in the system. Suppose that we
wanted to provide a solution to the consumer-producer problem that fills all the buffers.
We can do so by having an integer count that keeps track of the number of full buffers.
Initially, count is set to 0. It is incremented by the producer after it produces a new buffer
and is decremented by the consumer after it consumes a buffer.
Process Synchronization was introduced to handle problems that arose while multiple
process execute. Some of the problems are discussed below.

Producer-Consumer Problem
The classic example for studying cooperating processes is the Producer-Consumer
problem.

One or more producer processes is “producing” data. This data is stored in a buffer to
be “consumed” by one or more consumer processes. The buffer may be:
• Unbounded – We assume that the producer can continue producing items and storing
them in the buffer at all times. However, the consumer must wait for an item to be
inserted into the buffer before it can take one out for consumption.
• Bounded – The producer must also check to make sure there is space available in the
buffer. Bounded Buffer, buffer size n For simplicity, we will assume the objects being
produced and consumed are int values. This solution leaves one buffer entry empty at
all times:

Producer

while (true) {

/* produce an item and put in nextProduced */

while (count == BUFFER_SIZE)
; // do nothing
buffer [in] = nextProduced;

4|Page
 in = (in + 1) % BUFFER_SIZE;
count++;
}

Consumer

while (true) {
while (count == 0)
; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count--;
/* consume the item in nextConsumed
}

Race condition

 count++ could be implemented as

register1 = count
register1 = register1 + 1
count = register1
 count-- could be implemented as

register2 = count
register2 = register2 - 1
count = register2
 Consider this execution interleaving with “count = 5” initially:

S0: producer execute register1 = count {register1 = 5}

S1: producer execute register1 = register1 + 1 {register1 = 6}
S2: consumer execute register2 = count {register2 = 5}
S3: consumer execute register2 = register2 - 1 {register2 = 4}
S4: producer execute count = register1 {count = 6 }
S5: consumer execute count = register2 {count = 4}

Notice that we have arrived at the incorrect state “counter ==4” recording that there are
four full buffers, when, in fact, there are five full buffers. If we reversed the order of the
statements at S4 and S5, we would arrive at the incorrect state “counter ==6”.

5|Page
We would arrive at this incorrect state because we allowed both processes to
manipulate the variable counter concurrently. A situation like this, where several
processes access and manipulate the same data concurrently and the outcome of the
execution depends on the particular order in which the access takes place, is called a
race condition

To guard against the race condition above, we need to ensure that only one process at
a time can be manipulating the variable counter. To make such a guarantee, we require
some form of synchronization of the processes. Such situations occur frequently in
operating systems as different parts of the system manipulate resources and we want
the changes not to interfere with one another.

Critical-Section Problem
A Critical Section is a code segment that accesses shared variables and has to be
executed as an atomic action. It means that in a group of cooperating processes, at a
given point of time, only one process must be executing its critical section. If any other
process also wants to execute its critical section, it must wait until the first one finishes.

Solution to Critical Section Problem

A solution to the critical section problem must satisfy the following three conditions :

1. Mutual Exclusion

6|Page
Out of a group of cooperating processes, only one process can be in its critical section
at a given point of time.

2. Progress

If no process is executing in its critical section, and some processes wish to enter their
critical sections, then only those processes that are not executing in their remainder
section can participate in the decision on which will enter its critical section next, and
this selection cannot be postpone indefinitely.

3. Bounded Waiting

There exists a bound on the number of times that other processes are allowed to enter
their critical sections after a process has made a request to enter its critical section and
before that request is granted.
a. Peterson’s Solution
 Two process solution
 Assume that the LOAD and STORE instructions are atomic; that is, cannot be
interrupted.
 The two processes share two variables:
 int turn;
 Boolean flag[2]

 The variable turn indicates whose turn it is to enter the critical section.
 The flag array is used to indicate if a process is ready to enter the critical section.
flag[i] = true implies that process Pi is ready!
do {
flag[i] = TRUE;
turn = j;
while (flag[j] && turn == j);
critical section
flag[i] = FALSE;
remainder section
} while (TRUE);
Limitation
- Ensures mutual exclusion and avoids starvation, but works only for two
processes.

7|Page
 - It does not satisfy the progress requirement, since it requires strict alteration of
processes in the execution of the critical section. For example, if turn ==0 and p 1
is ready to enter its critical section, p1 cannot do so, even though p0 may be in
remainder section.

b. Synchronization Hardware
Many systems provide hardware support for critical section code. The critical section
problem could be solved easily in a single-processor environment if we could disallow
interrupts to occur while a shared variable or resource is being modified.
In this manner, we could be sure that the current sequence of instructions would be
allowed to execute in order without pre-emption. Unfortunately, this solution is not
feasible in a multiprocessor environment.
Disabling interrupt on a multiprocessor environment can be time consuming as the
message is passed to all the processors. This message transmission lag, delays entry
of threads into critical section and the system efficiency decreases.

c. Mutex Locks
As the synchronization hardware solution is not easy to implement from everyone, a
strict software approach called Mutex Locks was introduced. In this approach, in the
entry section of code, a LOCK is acquired over the critical resources modified and used
inside critical section, and in the exit section that LOCK is released. A mutex lock has a
boolean variable available whose value indicates if the lock is available or not. If the
lock is available, a call to acquire() succeeds, and the lock is then considered
unavailable. A process that attempts to acquire an unavailable lock is blocked until the
lock is released.
As the resource is locked while a process executes its critical section hence no other
process can access it.
The definition of acquire() is as follows:
acquire() { while (!available)
; /* busy wait */
available = false;;
}
do {

8|Page
 acquire lock
critical section
release lock
remainder section
} while (TRUE);
The definition of release() is as follows:
release() {
available = true;
}
The main disadvantage of the implementation given here is that it requires busy
waiting. While a process is in its critical section, any other process that tries to enter its
critical section must loop continuously in the call to acquire(). In fact, this type of mutex
lock is also called a spinlock because the process “spins” while waiting for the lock to
become available.

d. Semaphores
In 1965, Dijkstra proposed a new and very significant technique for managing
concurrent processes by using the value of a simple integer variable to synchronize the
progress of interacting processes. This integer variable is called semaphore. So it is
basically a synchronizing tool and is accessed only through two low standard atomic
operations, wait and signal designated by P() and V() respectively.
The classical definition of wait and signal are :

 Wait : decrement the value of its argument S as soon as it would become non-
negative.
 Signal : increment the value of its argument, S as an individual operation.

We can use semaphores to solve various synchronization problems. For example,

consider two concurrently running processes: P1 with a statement S1 and P2 with a
statement S2. Suppose we require that S2 be executed only after S1 has completed.
We can implement this scheme readily by letting P1 and P2 share a common
semaphore synch, initialized to 0.
In process P1, we insert the statements.
S1;
signal(synch);
In process P2, we insert the statements
wait(synch);
S2;

9|Page
Because synch is initialized to 0, P2 will execute S2 only after P1 has invoked
signal(synch), which is after statement S1 has been executed.
Properties of Semaphores

1. Simple
2. Works with many processes
3. Can have many different critical sections with different semaphores
4. Each critical section has unique access semaphores
5. Can permit multiple processes into the critical section at once, if desirable.

Types of Semaphores
Semaphores are mainly of two types:

1. Binary Semaphore

It is a special form of semaphore used for implementing mutual exclusion, hence it is

often called Mutex. A binary semaphore is initialized to 1 and only takes the value 0 and
1 during execution of a program.

2. Counting Semaphores

These are used to implement bounded concurrency. Counting semaphores can be used
to control access to a given resource consisting of a finite number of instances. The
semaphore is initialized to the number of resources available. Each process that wishes
to use a resource
performs a wait() operation on the semaphore (thereby decrementing the count). When
a process releases a resource, it performs a signal() operation (incrementing the count).
When the count for the semaphore goes to 0, all resources are being used. After that,
processes that wish to use a resource will block until the count becomes greater than 0.
Limitations of Semaphores

1. Priority Inversion is a big limitation os semaphores.

2. Their use is not enforced, but is by convention only.
3. With improper use, a process may block indefinitely. Such a situation is called
Deadlock. We will be studying deadlocks in details in coming lessons.

Classical Problems of Synchronization

In this section we will discuss about various classic problem of synchronization.
Semaphore can be used in other synchronization problems besides Mutual Exclusion.

10 | P a g e
Below are some of the classical problem depicting flaws of process synchronization in
systems where cooperating processes are present.
We will discuss the following three problems:

1. Bounded Buffer (Producer-Consumer) Problem

2. The Readers Writers Problem
3. Dining Philosophers Problem

Bounded Buffer Problem

Bounded buffer problem, which is also called producer consumer problem, is one of the
classic problems of synchronization. Let's start by understanding the problem here, before
moving on to the solution and program code.

Problem Statement
There is a buffer of n slots and each slot is capable of storing one unit of data. There are
two processes running, namely, producer and consumer, which are operating on the
buffer.

Bounded Buffer Problem

A producer tries to insert data into an empty slot of the buffer. A consumer tries to remove
data from a filled slot in the buffer. As you might have guessed by now, those two
processes won't produce the expected output if they are being executed concurrently.
There needs to be a way to make the producer and consumer work in an independent
manner.

Here's a Solution

11 | P a g e
One solution of this problem is to use semaphores. The semaphores which will be used
here are:

 m, a binary semaphore which is used to acquire and release the lock.

 empty, a counting semaphore whose initial value is the number of slots in the buffer,
since, initially all slots are empty.
 full, a counting semaphore whose initial value is 0.

At any instant, the current value of empty represents the number of empty slots in the buffer
and full represents the number of occupied slots in the buffer.

The Producer Operation

The pseudocode of the producer function looks like this:

do {
// produce an item in nextp
wait (empty);
wait (mutex);
// add the item to the buffer
signal (mutex);
signal (full);
} while (TRUE);

 Looking at the above code for a producer, we can see that a producer first waits until
there is atleast one empty slot.
 Then it decrements the empty semaphore because, there will now be one less empty
slot, since the producer is going to insert data in one of those slots.
 Then, it acquires lock on the buffer, so that the consumer cannot access the buffer until
producer completes its operation.
 After performing the insert operation, the lock is released and the value of full is
incremented because the producer has just filled a slot in the buffer.

The Consumer Operation

The pseudocode for the consumer function looks like this:

do {
wait (full);
wait (mutex);
// remove an item from buffer to nextc
signal (mutex);
signal (empty);

12 | P a g e
 // consume the item in nextc
} while (TRUE);

 The consumer waits until there is atleast one full slot in the buffer.
 Then it decrements the full semaphore because the number of occupied slots will be
decreased by one, after the consumer completes its operation.
 After that, the consumer acquires lock on the buffer.
 Following that, the consumer completes the removal operation so that the data from one
of the full slots is removed.
 Then, the consumer releases the lock.
 Finally, the empty semaphore is incremented by 1, because the consumer has just
removed data from an occupied slot, thus making it empty.

The Readers Writers Problem

Reader’s writer problem is another example of a classic synchronization problem. There are
many variants of this problem, one of which is examined below.

The Problem Statement

There is a shared resource which should be accessed by multiple processes. There are two
types of processes in this context. They are reader and writer. Any number of readers can
read from the shared resource simultaneously, but only one writer can write to the shared
resource. When a writeris writing data to the resource, no other process can access the
resource. A writer cannot write to the resource if there are non zero number of readers
accessing the resource at that time.

The Solution
From the above problem statement, it is evident that readers have higher priority than
writer. If a writer wants to write to the resource, it must wait until there are no readers
currently accessing that resource.
Here, we use one mutex m and a semaphore w. An integer variable read_count is used to
maintain the number of readers currently accessing the resource. The variable read_count is
initialized to 0. A value of 1 is given initially to m and w.
Instead of having the process to acquire lock on the shared resource, we use the mutex m to
make the process to acquire and release lock whenever it is updating
the read_count variable.
The code for the writer process looks like this:

do {
wait (wrt) ;

// writing is performed

13 | P a g e
 signal (wrt) ;
} while (TRUE);
And, the code for the reader process looks like this:

do {
wait (mutex) ;
readcount ++ ;
if (readcount == 1)
wait (wrt) ;
signal (mutex)

// reading is performed
wait (mutex) ;
readcount - - ;
if (readcount == 0)
signal (wrt) ;
signal (mutex) ;
} while (TRUE);
Dining Philosophers Problem
The dining philosophers problem is another classic synchronization problem which is used
to evaluate situations where there is a need of allocating multiple resources to multiple
processes

Problem Statement
Consider there are five philosophers sitting around a circular dining table. The dining table
has five chopsticks and a bowl of rice in the middle as sh
At any instant, a philosopher is either eating or thinking. When a philosopher wants to eat,
he uses two chopsticks - one from their left and one from their right. When a philosopher
wants to think, he keeps down both chopsticks at their original place.

Here's the Solution

From the problem statement, it is clear that a philosopher can think for an indefinite amount
of time. But when a philosopher starts eating, he has to stop at some point of time. The
philosopher is in an endless cycle of thinking and eating.
An array of five semaphores, stick[5], for each of the five chopsticks.
The code for each philosopher looks like:

do {
wait ( chopstick[i] );

14 | P a g e
 wait ( chopStick[ (i + 1) % 5] );

// eat
signal ( chopstick[i] );
signal (chopstick[ (i + 1) % 5] );

// think
} while (TRUE);
When a philosopher wants to eat the rice, he will wait for the chopstick at his left and picks
up that chopstick. Then he waits for the right chopstick to be available, and then picks it too.
After eating, he puts both the chopsticks down.
But if all five philosophers are hungry simultaneously, and each of them pickup one
chopstick, then a deadlock situation occurs because they will be waiting for another
chopstick forever. The possible solutions for this are:

 A philosopher must be allowed to pick up the chopsticks only if both the left and right
chopsticks are available.
 Allow only four philosophers to sit at the table. That way, if all the four philosophers pick
up four chopsticks, there will be one chopstick left on the table. So, one philosopher can
start eating and eventually, two chopsticks will be available. In this way, deadlocks can
be avoided.

Threads
Thread is an execution unit which consists of its own program counter, a stack, and a set of
registers. Threads are also known as Lightweight processes. Threads are popular way to
improve application through parallelism. The CPU switches rapidly back and forth among
the threads giving illusion that the threads are running in parallel.
As each thread has its own independent resource for process execution, multpile processes
can be executed parallely by increasing number of threads.

15 | P a g e
Types of Thread
There are two types of threads:

1. User Threads
2. Kernel Threads

User threads, are above the kernel and without kernel support. These are the threads that
application programmers use in their programs.
Kernel threads are supported within the kernel of the OS itself. All modern OSs support
kernel level threads, allowing the kernel to perform multiple simultaneous tasks and/or to
service multiple kernel system calls simultaneously.

Multithreading Models
The user threads must be mapped to kernel threads, by one of the following strategies:

 Many to One Model

 One to One Model
 Many to Many Model

Many to One Model

 In the many to one model, many user-level threads are all mapped onto a single kernel
thread.
 Thread management is handled by the thread library in user space, which is efficient in
nature.

16 | P a g e
One to One Model
 The one to one model creates a separate kernel thread to handle each and every user
thread.
 Most implementations of this model place a limit on how many threads can be created.
 Linux and Windows from 95 to XP implement the one-to-one model for threads.

Many to Many Model

 The many to many model multiplexes any number of user threads onto an equal or
smaller number of kernel threads, combining the best features of the one-to-one and
many-to-one models.
 Users can create any number of the threads.
 Blocking the kernel system calls does not block the entire process.
 Processes can be split across multiple processors.

17 | P a g e
Thread Libraries
Thread libraries provide programmers with API for creation and management of threads.
Thread libraries may be implemented either in user space or in kernel space. The user
space involves API functions implemented solely within the user space, with no kernel
support. The kernel space involves system calls, and requires a kernel with thread library
support.

Three types of Thread libraries

1. POSIX Pitheads, may be provided as either a user or kernel library, as an extension to
the POSIX standard.
2. Win32 threads, are provided as a kernel-level library on Windows systems.
3. Java threads: Since Java generally runs on a Java Virtual Machine, the implementation
of threads is based upon whatever OS and hardware the JVM is running on, i.e. either
Pitheads or Win32 threads depending on the system.

Benefits of Multithreading

1. Responsiveness
2. Resource sharing, hence allowing better utilization of resources.
3. Economy. Creating and managing threads becomes easier.
4. Scalability. One thread runs on one CPU. In Multithreaded processes, threads can be
distributed over a series of processors to scale.
5. Context Switching is smooth. Context switching refers to the procedure followed by CPU
to change from one task to another.

Multithreading Issues

18 | P a g e
Thread Cancellation
Thread cancellation means terminating a thread before it has finished working. There can
be two approaches for this, one is Asynchronous cancellation, which terminates the
target thread immediately. The other is Deferred cancellation allows the target thread to
periodically check if it should be cancelled.

Signal Handling
Signals are used in UNIX systems to notify a process that a particular event has occurred.
Now in when a Multithreaded process receives a signal, to which thread it must be
delivered? It can be delivered to all, or a single thread.

fork() System Call

fork() is a system call executed in the kernel through which a process creates a copy of
itself. Now the problem in Multithreaded process is, if one thread forks, will the entire
process be copied or not?

Security Issues
Yes, there can be security issues because of extensive sharing of resources between
multiple threads.
There are many other issues that you might face in a multithreaded process, but there are
appropriate solutions available for them.

Introduction to File System

A file is a named collection of related information that is recorded on secondary storage
such as magnetic disks, magnetic tapes and optical disks. In general, a file is a
sequence of bits, bytes, lines or records whose meaning is defined by the files creator
and user.
The file system provides the mechanism for on-line storage of and access to both data and
programs residing on the disks. A file is a collection of related information defined by its
creator. The files are mapped by the operating system onto physical devices. Files are
normally organized into directories for ease of use.

File Structure
A file has various kinds of structure. Some of them can be :

 Simple Record Structure with lines of fixed or variable lengths.

 Complex Structures like formatted document or reloadable load files.
 No Definite Structure like sequence of words and bytes etc.

19 | P a g e
Attributes of a File
Following are some of the attributes of a file :

 Name . It is the only information which is in human-readable form.

 Identifier. The file is identified by a unique tag(number) within file system.
 Type. It is needed for systems that support different types of files.
 Location. Pointer to file location on device.
 Size. The current size of the file.
 Protection. This controls and assigns the power of reading, writing, executing.
 Time, date, and user identification. This is the data for protection, security, and usage
monitoring.

File Type
File type refers to the ability of the operating system to distinguish different types of file
such as text files source files and binary files etc. Many operating systems support
many types of files. Operating system like MS-DOS and UNIX have the following types
of files:
Ordinary files

 These are the files that contain user information.

 These may have text, databases or executable program.
 The user can apply various operations on such files like add, modify, delete or
even remove the entire file.
Directory files

 These files contain list of file names and other information related to these files.
Special files

 These files are also known as device files.

 These files represent physical device like disks, terminals, printers, networks,
tape drive etc.
These files are of two types −
 Character special files − data is handled character by character as in case of
terminals or printers.

 Block special files − data is handled in blocks as in the case of disks and
tapes.

20 | P a g e
File Access Methods
The way that files are accessed and read into memory is determined by Access methods.
Usually a single access method is supported by systems while there are OS's that support
multiple access methods

1. Sequential Access

 Data is accessed one record right after another is an order.

 Read command cause a pointer to be moved ahead by one.
 Write command allocate space for the record and move the pointer to the new End Of
File.
 Such a method is reasonable for tape.

2. Direct Access

 This method is useful for disks.

 The file is viewed as a numbered sequence of blocks or records.
 There are no restrictions on which blocks are read/written, it can be done in any order.
 User now says "read n" rather than "read next".
 "n" is a number relative to the beginning of file, not relative to an absolute physical disk
location.

3. Indexed Sequential Access

 It is built on top of Sequential access.

 It uses an Index to control the pointer while accessing files.

Directory

Information about files is maintained by Directories. A directory can contain multiple files. It
can even have directories inside of them. In Windows we also call these directories as
folders.
Following is the information maintained in a directory :

 Name: The name visible to user.

 Type: Type of the directory.
 Location: Device and location on the device where the file header is located.
 Size: Number of bytes/words/blocks in the file.
 Position: Current next-read/next-write pointers.
 Protection: Access control on read/write/execute/delete.
 Usage: Time of creation, access, modification etc.

21 | P a g e
 Mounting: When the root of one file system is "grafted" into the existing tree of another
file system its called Mounting.

Space Allocation
Files are allocated disk spaces by operating system. Operating systems deploy
following three main ways to allocate disk space to files.

 Contiguous Allocation
 Linked Allocation
 Indexed Allocation

Contiguous Allocation

 Each file occupies a contiguous address space on disk.

 Assigned disk address is in linear order.
 Easy to implement.
 External fragmentation is a major issue with this type of allocation technique.

Linked Allocation

 Each file carries a list of links to disk blocks.

 Directory contains link / pointer to first block of a file.
 No external fragmentation
 Effectively used in sequential access file.
 Inefficient in case of direct access file.

Indexed Allocation

 Provides solutions to problems of contiguous and linked allocation.

 A index block is created having all pointers to files.
 Each file has its own index block which stores the addresses of disk space
occupied by the file.
 Directory contains the addresses of index blocks of files
Secondary Storage and Disk Scheduling Algorithms
Secondary storage devices are those devices whose memory is non volatile, meaning, the
stored data will be intact even if the system is turned off. Here are a few things worth noting
about secondary storage.

 Secondary storage is also called auxiliary storage.

 Secondary storage is less expensive when compared to primary memory like RAMs.

22 | P a g e
 The speed of the secondary storage is also lesser than that of primary storage.
 Hence, the data which is less frequently accessed is kept in the secondary storage.
 A few examples are magnetic disks, magnetic tapes, removable thumb drives etc.

Magnetic Disk Structure

In modern computers, most of the secondary storage is in the form of magnetic disks.
Hence, knowing the structure of a magnetic disk is necessary to understand how the data in
the disk is accessed by the computer.

Structure of a magnetic disk

A magnetic disk contains several platters. Each platter is divided into circular
shaped tracks. The length of the tracks near the centre is less than the length of the tracks
farther from the centre. Each track is further divided into sectors, as shown in the figure.
Tracks of the same distance from centre form a cylinder. A read-write head is used to read
data from a sector of the magnetic disk.
The speed of the disk is measured as two parts:

 Transfer rate: This is the rate at which the data moves from disk to the computer.
 Random access time: It is the sum of the seek time and rotational latency.

Seek time is the time taken by the arm to move to the required track. Rotational latency is
defined as the time taken by the arm to reach the required sector in the track.

23 | P a g e
Even though the disk is arranged as sectors and tracks physically, the data is logically
arranged and addressed as an array of blocks of fixed size. The size of a block can
be 512 or 1024 bytes. Each logical block is mapped with a sector on the disk, sequentially.
In this way, each sector in the disk will have a logical address.

Disk Scheduling Algorithms

On a typical multiprogramming system, there will usually be multiple disk access requests at
any point of time. So those requests must be scheduled to achieve good efficiency. Disk
scheduling is similar to process scheduling. Some of the disk scheduling algorithms are
described below.

First Come First Serve

This algorithm performs requests in the same order asked by the system. Let's take an
example where the queue has the following requests with cylinder numbers as follows:
98, 183, 37, 122, 14, 124, 65, 67
Assume the head is initially at cylinder 56. The head moves in the given order in the queue
i.e., 56→98→183→...→67.

Shortest Seek Time First (SSTF)

Here the position which is closest to the current head position is chosen first. Consider the
previous example where disk queue looks like,
98, 183, 37, 122, 14, 124, 65, 67
Assume the head is initially at cylinder 56. The next closest cylinder to 56 is 65, and then
the next nearest one is 67, then 37, 14, so on.

24 | P a g e
SCAN algorithm
This algorithm is also called the elevator algorithm because of it's behavior. Here, first the
head moves in a direction (say backward) and covers all the requests in the path. Then it
moves in the opposite direction and covers the remaining requests in the path. This
behavior is similar to that of an elevator. Let's take the previous example,
98, 183, 37, 122, 14, 124, 65, 67
Assume the head is initially at cylinder 56. The head moves in backward direction and
accesses 37and 14. Then it goes in the opposite direction and accesses the cylinders as
they come in the path.

25 | P a g e
Operating system security
Security refers to providing a protection system to computer system resources such as
CPU, memory, disk, software programs and most importantly data/information stored in
the computer system. If a computer program is run by an unauthorized user, then
he/she may cause severe damage to computer or data stored in it. So a computer
system must be protected against unauthorized access, malicious access to system
memory, viruses, worms etc. some forms of security are as follows:

 Authentication
 One Time passwords
 Program Threats
 System Threats
 Computer Security Classifications
Authentication
Authentication refers to identifying each user of the system and associating the
executing programs with those users. It is the responsibility of the Operating System to
create a protection system which ensures that a user who is running a particular
program is authentic. Operating Systems generally identifies/authenticates users using
following three ways −
 Username / Password − User need to enter a registered username and
password with Operating system to login into the system.

26 | P a g e
  User card/key − User need to punch card in card slot, or enter key generated by
key generator in option provided by operating system to login into the system.
 User attribute - fingerprint/ eye retina pattern/ signature − User need to pass
his/her attribute via designated input device used by operating system to login
into the system.
One Time passwords
One-time passwords provide additional security along with normal authentication. In
One-Time Password system, a unique password is required every time user tries to
login into the system. Once a one-time password is used, then it cannot be used again.
One-time password are implemented in various ways.
 Random numbers − Users are provided cards having numbers printed along
with corresponding alphabets. System asks for numbers corresponding to few
alphabets randomly chosen.
 Secret key − User are provided a hardware device which can create a secret id
mapped with user id. System asks for such secret id which is to be generated
every time prior to login.
 Network password − Some commercial applications send one-time passwords
to user on registered mobile/ email which is required to be entered prior to login.
Program Threats
Operating system's processes and kernel do the designated task as instructed. If a
user program made these process do malicious tasks, then it is known as Program
Threats. One of the common example of program threat is a program installed in a
computer which can store and send user credentials via network to some hacker.
Following is the list of some well-known program threats.
 Trojan Horse − Such program traps user login credentials and stores them to
send to malicious user who can later on login to computer and can access
system resources.
 Trap Door − If a program which is designed to work as required, have a security
hole in its code and perform illegal action without knowledge of user then it is
called to have a trap door.
 Logic Bomb − Logic bomb is a situation when a program misbehaves only
when certain conditions met otherwise it works as a genuine program. It is
harder to detect.
 Virus − Virus as name suggest can replicate themselves on computer system.
They are highly dangerous and can modify/delete user files, crash systems. A
virus is generatlly a small code embedded in a program. As user accesses the

27 | P a g e
 program, the virus starts getting embedded in other files/ programs and can
make system unusable for user
System Threats
System threats refers to misuse of system services and network connections to put
user in trouble. System threats can be used to launch program threats on a complete
network called as program attack. System threats creates such an environment that
operating system resources/ user files are misused. Following is the list of some well-
known system threats.
 Worm − Worm is a process which can choked down a system performance by
using system resources to extreme levels. A Worm process generates its
multiple copies where each copy uses system resources, prevents all other
processes to get required resources. Worms processes can even shut down an
entire network.
 Port Scanning − Port scanning is a mechanism or means by which a hacker
can detects system vulnerabilities to make an attack on the system.
 Denial of Service − Denial of service attacks normally prevents user to make
legitimate use of the system. For example, a user may not be able to use
internet if denial of service attacks browser's content settings.
Computer Security Classifications
As per the U.S. Department of Defense Trusted Computer System's Evaluation Criteria
there are four security classifications in computer systems: A, B, C, and D. This is
widely used specifications to determine and model the security of systems and of
security solutions. Following is the brief description of each classification.

S.N. Classification Type & Description

1 Type A
Highest Level. Uses formal design specifications and verification
techniques. Grants a high degree of assurance of process security.

2 Type B
Provides mandatory protection system. Have all the properties of a class
C2 system. Attaches a sensitivity label to each object. It is of three types.
 B1 − Maintains the security label of each object in the system. Label
is used for making decisions to access control.

28 | P a g e
  B2 − Extends the sensitivity labels to each system resource, such as
storage objects, supports covert channels and auditing of events.
 B3 − Allows creating lists or user groups for access-control to grant
access or revoke access to a given named object.

3 Type C
Provides protection and user accountability using audit capabilities. It is of
two types.
 C1 − Incorporates controls so that users can protect their private
information and keep other users from accidentally reading /
deleting their data. UNIX versions are mostly Cl class.
 C2 − Adds an individual-level access control to the capabilities of a
Cl level system.

4 Type D

Lowest level. Minimum protection. MS-DOS, Window 3.1 fall in this

category.

29 | P a g e