Notes OS

Q.1 - Explain Free Space Management in details.

Ans:
There is a system software in an operating system that manipulates and keeps track
of free spaces to allocate and de-allocate memory blocks to files, this system is
called a "file management system in an operating system". There is a "free space
list" in an operating system that maintains the record of free blocks.
When a file is created, the operating system searches the free space list for the
required space allocated to save a file. While deletion a file, the file system frees the
given space and adds this to the "free space list".

Methods of Free Space Management in OS

It is not easy work for an operating system to allocate and de-allocate memory
blocks (managing free space) simultaneously. The operating system uses various
methods for adding free space and freeing up space after deleting a file. There are
various methods using which a free space list can be implemented. We are going to
explain them below-

Bitmap
A bit vector is the most frequently used method to implement the free space list. A bit
vector is also known as a "Bit map"
. It is a series or collection of bits in which each bit represents a disk block. The
values taken by the bits are either 1 or 0. If the block bit is 1, it means the block is

Notes OS 1
 empty and if the block bit is 0, it means the block is not free. It is allocated to some
files. Since all the blocks are empty initially so, each bit in the bit vector represents 0.

Advantages of Bit vector method :

1. Simple and easy to understand.

2. Consumes less memory.

3. It is efficient to find free space.

Disadvantages of Bit vector method :

1. The operating system goes through all the blocks until it finds a free block. (block
whose bit is 0).

2. It is not efficient when the disk size is large.

Linked List :
A linked list is another approach for free space management in an operating
system. In it, all the free blocks inside a disk are linked together in a "linked list".
These free blocks on the disk are linked together by a pointer. These pointers of the
free block contain the address of the next free block and the last pointer of the list
points to null which indicates the end of the linked list. This technique is not enough
to traverse the list because we have to read each disk block one by one which
requires I/O time.

Advantage of the Linked list :

1. In this method, available space is used efficiently.

2. As there is no size limit on a linked list, a new free space can be added easily.

Disadvantages :

1. In this method, the overhead of maintaining the pointer appears.

2. the Linked list is not efficient when we need to reach every block of memory.

Grouping :

Notes OS 2
 The grouping technique is also called the "modification of a linked list
technique". In this method, first, the free block of memory contains the addresses of
the n-free blocks. And the last free block of these n free blocks contains the
addresses of the next n free block of memory and this keeps going on. This
technique separates the empty and occupied blocks of space of memory.

Advantage of the Grouping method :

1. By using this method, we can easily find addresses of a large number of free
blocks easily and quickly.

Disadvantage :

1. We need to change the entire list if one block gets occupied.

Counting :
In memory space, several files are created and deleted at the same time. For which
memory blocks are allocated and de-allocated for the files. Creation of files occupy
free blocks and deletion of file frees blocks. When there is an entry in the free space,
it consists of two parameters- "address of first free disk block (a pointer)" and " a
number 'n' ".

Advantages :

1. In this method, a bunch of free blocks take place fastly.

2. The list is smaller in size.

Disadvantage :

1. In the counting method, the first free block stores the rest free blocks, so it
requires more space.

Conclusion
File management system in an operating system is used to keep track of free
spaces to allocate and de-allocate memory blocks to files.

These space blocks are manipulated when there is a creation or deletion of a file
in our system.

Notes OS 3
 Q.2 - Explain File Allocation Methods in details.
Ans: Whenever a hard disk is formatted, a system has many small areas called
blocks or sectors that are used to store any kind of file. File allocation methods are
different ways by which the operating system stores information in memory blocks,
thus allowing the hard drive to be utilized effectively and the file to be accessed.
Below are the types of file allocation methods in the Operating System.

Types of File Allocation Methods in Operating

System.
Contiguous File allocation

Linked File Allocation

Indexed File Allocation

Contiguous File Allocation.

First, let's understand the meaning of contiguous, here contiguous means adjacent
or touching. Now let's understand what is contiguous file allocation.

What is Contiguous File allocation?

In contiguous file allocation, the block is allocated in such a manner that all the
allocated blocks in the hard disk are adjacent.

Assuming a file needs 'n' number of blocks in the disk and the file begins with a
block at position 'x', the next blocks to be assigned to it will be x+1,x+2,x+3,...,x+n-
1 so that they are in a contiguous manner.

Advantages and Disadvantages

Advantages

It is very easy to implement.

Notes OS 4
 There is a minimum amount of seek time.

The disk head movement is minimum.

Memory access is faster.

It supports sequential as well as direct access.

Disadvantages

At the time of creation, the file size must be initialized.

As it is pre-initialized, the size cannot increase. As

Due to its constrained allocation, it is possible that the disk would fragment
internally or externally.

Linked File Allocation.

What is Linked File Allocation?
The Linked file allocation overcomes the drawback of contiguous file allocation. Here
the file which we store on the hard disk is stored in a scattered manner according to
the space available on the hard disk. Now, you must be thinking about how the OS
remembers that all the scattered blocks belong to the same file. So as the name
linked File Allocation suggests, the pointers are used to point to the next block of the
same file, therefore along with the entry of each file each block also stores the
pointer to the next block.

Advantages and Disadvantages

Advantages

There is no external fragmentation.

The directory entry just needs the address of starting block.

The memory is not needed in contiguous form, it is more flexible than contiguous
file allocation.

Disadvantages

It does not support random access or direct access.

Notes OS 5
 If pointers are affected so the disk blocks are also affected.

Extra space is required for pointers in the block.

Indexed File Allocation.

What is Indexed File Allocation?
The indexed file allocation is somewhat similar to linked file allocation as indexed file
allocation also uses pointers but the difference is here all the pointers are put
together into one location which is called index block. That means we will get all the
locations of blocks in one index file. The blocks and pointers were spread over the
memory in the Linked Allocation method, where retrieval was accomplished by
visiting each block sequentially. But here in indexed allocation, it becomes easier
with the index block to retrieve.

Advantages and Disadvantages

Advantages

It reduces the possibilities of external fragmentation.

Rather than accessing sequentially it has direct access to the block.

Disadvantages

Here more pointer overhead is there.

If we lose the index block we cannot access the complete file.

It becomes heavy for the small files.

It is possible that a single index block cannot keep all the pointers for some large
files.

To resolve this issue, we can use the following approaches:

1. Linked scheme

2. Multilevel Index

3. Combined Scheme

Notes OS 6
 Q.3 - Explain Disk Structure and Disk Scheduling Algorithms in
Details

What is Disk Scheduling Algorithms in OS?

"Disk Scheduling Algorithms" in an operating system can be referred to as a
manager of a grocery store that manages all the incoming and outgoing requests for
goods of that store. He keeps a record of what is available in-store, what we need
further, and manages the timetable of transaction of goods.
The 'Disk Structure in OS' is made in such a way that there are many layers of
storage blocks on the disk. And when we need to access these data from disk, we
initialize a 'request' to the system to give us the required data. These requests are
done on a large scale. So, there is a large number of input and output requests
coming to the disk. The operating system manages the timetable of all these
requests in a proper algorithm. This is called as "Disk Scheduling Algorithm in OS".
This algorithm helps OS to maintain an efficient manner in which input-output
requests can be managed to execute a process. It manages a proper order to deal
with sequential requests to the disk and provide the required data. Since multiple
requests are approaching the disk, this algorithm also manages the upcoming
requests of the future and does a lining up of requests.

Important terms related to disk scheduling

There are many terms that we need to know for a better understanding of Disk
Scheduling. We are going to have a brief look at each of them one by one:

1. Seek Time: As we know, the data may be stored on various blocks of disk. To
access these data according to the request, the disk arm moves and find the
required block. The time taken by the arm in doing this search is known as "Seek
Time".

2. Rotational Latency: The required data block needs to move at a particular

position from where the read/write head can fetch the data. So, the time taken in
this movement is known as "Rotational Latency". This rotational time should be
as less as possible so, the algorithm that will take less time to rotate will be
considered a better algorithm.

Notes OS 7
 3. Transfer Time: When a request is made from the user side, it takes some time
to fetch these data and provide them as output. This taken time is known as
"Transfer Time".

4. Disk Access Time: It is defined as the total time taken by all the above
processes. Disk access time = (seek time + rotational latency time + transfer
time)

5. Disk Response Time: The disk processes one request at a single time. So, the
other requests wait in a queue to finish the ongoing process of request. The
average of this waiting time is called "Disk Response Time".

6. Starvation: Starvation is defined as the situation in which a low-priority job

keeps waiting for a long time to be executed. The system keeps sending high-
priority jobs to the disk scheduler to execute first.

Types of Disk Scheduling Algorithm in OS

We have various types of Disk Scheduling Algorithms available in our system. Each
one has its own capabilities and weak points.

1. FCFS disk scheduling algorithm-

It stands for 'first-come-first-serve'. As the name suggests, the request which comes
first will be processed first and so on. The requests coming to the disk are arranged
in a proper sequence as they arrive. Since every request is processed in this
algorithm, so there is no chance of 'starvation'.

Advantages:

Notes OS 8
 1. Implementation is easy.

2. No chance of starvation.

Disadvantages:

1. 'Seek time' increases.

2. Not so efficient.

2. SSTF disk scheduling algorithm-

It stands for 'Shortest seek time first'. As the name suggests, it searches for the
request having the least 'seek time' and executes them first. This algorithm has less
'seek time' as compared to FCFS Algorithm.

Advantages:

1. In this algorithm, disk response time is less.

2. More efficient than FCFS.

Disadvantages:

1. Less speed of algorithm execution.

2. Starvation can be seen.

3. SCAN disk scheduling algorithm:

In this algorithm, the head starts to scan all the requests in a direction and reaches
the end of the disk. After that, it reverses its direction and starts to scan again the
requests in its path and serves them. Due to this feature, this algorithm is also
known as the "Elevator Algorithm".

Advantages:

1. Implementation is easy.

2. Requests do not have to wait in a queue.

Disadvantage:

1. The head keeps going on to the end even if there are no requests in that
direction.

Notes OS 9
 4. C-SCAN disk scheduling algorithm:
It stands for "Circular-Scan". This algorithm is almost the same as the Scan disk
algorithm but one thing that makes it different is that 'after reaching the one end and
reversing the head direction, it starts to come back. The disk arm moves toward the
end of the disk and serves the requests coming into its path. After reaching the end
of the disk it reverses its direction and again starts to move to the other end of the
disk but while going back it does not serve any requests.

Advantages:

1. The waiting time is uniformly distributed among the requests.

2. Response time is good in it.

Disadvantages:

1. The time taken by the disk arm to locate a spot is increased here.

2. The head keeps going to the end of the disk.

5. LOOK the disk scheduling algorithm:

In this algorithm, the disk arm moves to the 'last request' present and services them.
After reaching the last requests, it reverses its direction and again comes back to the
starting point. It does not go to the end of the disk, in spite, it goes to the end of
requests.

Advantages:

1. Starvation does not occur.

2. Since the head does not go to the end of the disk, the time is not wasted
here.

Disadvantage:

1. The arm has to be conscious to find the last request.

6. C-LOOK disk scheduling algorithm:

The C-Look algorithm is almost the same as the Look algorithm. The only difference
is that after reaching the end requests, it reverses the direction of the head and

Notes OS 10
 starts moving to the initial position. But in moving back, it does not serve any
requests.

Advantages:

1. The waiting time is decreased.

2. If there are no requests till the end, it reverses the head direction
immediately.

3. Starvation does not occur.

4. The time taken by the disk arm to find the desired spot is less.

Disadvantage:

1. The arm has to be conscious about finding the last request.

Conclusion:
The Disk Scheduling Algorithm in OS is used to manage input and output
requests to the disk.

Disk Scheduling is important as multiple requests are coming to disk

simultaneously and it is also known as the "Request Scheduling Algorithm"

Notes OS 11