Bit Vector in Operating System

What is Bit vector?

Bit vector is one of the most important methods used in the free space management of operating system. Free space management which is used by the operating system leads the free space in the hard disk that’s why we call it free space management. OS generally leads a free space list to keep the track of free space disk. Free space list contains all disk blocks which are not allocated to any file or directory.

What is Bit?

Bit is also known as unit of information used in computing which can have only one of two values either 1 or 0.

Bit vector also known as bitmap is generally used to implement the free space list. In this method, every block symbolizes of a bit (0 or 1). Condition 1, when a block has bit 0 means block is allocated. Condition 2, when block have 1 bit which means block is free or no memory allocation. It refers to the special type of indexing which use bitmaps. This method is generally used for big databases.

1. A bit vector size is identical to the number of disks blocks is used.
2. If i^th block is free then the bit vector value at i^th location will be 0, otherwise 1.
3. Memory requirements for storing the bit vectors also increase with the increase in size of the disk.

Advantages of Bit vector

Advantages of bit vector are as follows:

1. It is simple and easy to understand.
2. It consumes less memory.
3. It is well organized to find free spaces.

Disadvantages of Bit vector

Disadvantages of bit vector are as follows:

1. OS goes through all the blocks until it finds a free block.
2. To find free block, OS may need to search the whole bit vector.
3. It requires some special hardware support in some conditions.

Need of Bitmap

Now, we take an example to explain the working of bitmap. Assume that there is a company which holds an employee table with entries like empno, empname, designation, income etc. As we all know employees in any organization are hired once in a year which means the table is less updated and endure static most of the time. But the columns will always concurrent used in queries to retrieve data like: no of female candidates in the company and many more. In this situation, we need a method which is known as a file organization method which is capable enough to provide quick results. But any of the traditional file organization method is not that fast to provide quick results. Therefore, we switch better method of storing and retrieving data known as bitmap indexing.

Applications

The bitmap has number of applications in areas where the space as well as the efficiency is at premium. Most commonly, they are used to represent a simple group of Boolean flags or an ordered sequence of Boolean values.

1. They are used for the priority queues, where the bit at index k is set if and only if k is in the queue.
2. They are also used for the allocation of memory pages, disk sectors etc. In such cases term bitmap may also use. This term is generally used to refer to raster images which use multiple bit or pixel.
3. Bloom filter which is one of the most important type of application of bitmaps. It is used to store the huge sets in small space in exchange for a small probability. It is also possible to build probabilistic hash tables based on bit arrays which accepts false positive or negatives.
4. They are also a useful abstraction for examining the streams of compressed data, which often contain element that occupy portions of bytes or are not byte aligned, for example the compressed human coding representation of a single 8-bit character can be anywhere from 1 to 255 bits along.
5. Bit maps and operations on them are also important for developing the succinct data structures, which is close to the minimum amount applicable space. In this context, operations like searching the n^th bit up to the certain position become important.