File Allocation Strategies


File allocation strategies refer to the methods used by operating systems to manage the allocation of disk space to files. Here are some common file allocation strategies:

Contiguous Allocation:
In this scheme, each file occupies a contiguous set of blocks on the disk.
For example, if a file requires n blocks and is given a block b as the starting location, then the blocks assigned to the file will be: b, b+1, b+2, …, b+n-1.
Advantages:
  • Supports both sequential and direct accesses.
  • Direct access to the kth block of the file (which starts at block b) can easily be obtained as (b+k). This is extremely fast since the number of seeks is minimal due to contiguous allocation of file blocks.
Disadvantages:
  • Suffers from both internal and external fragmentation.
  • Inefficient in terms of memory utilization.
  • Increasing file size is difficult because it depends on the availability of contiguous memory at a particular instance.
Linked Allocation:
  • Each file is a linked list of disk blocks that need not be contiguous.
  • Disk blocks can be scattered anywhere on the disk.
  • The directory entry contains a pointer to the starting and ending file block.
  • Each block contains a pointer to the next block occupied by the file.
Advantages:
  • Very flexible in terms of file size.
  • File size can be increased easily since the system does not have to look for a contiguous chunk of memory.
  • Does not suffer from external fragmentation.
Disadvantages:
  • Because the file blocks are distributed randomly on the disk, a large number of seeks are needed to access every block individually. This makes linked allocation slower.
  • Does not support random or direct access. We cannot directly access the blocks of a file. A block k of a file can be accessed by traversing k blocks sequentially (sequential access) from the starting block of the file via block pointers. Pointers required in the linked allocation incur some extra overhead.
Indexed Allocation:
  • Addresses the limitations of both contiguous and linked allocation methods.
  • Each file has its own index block, which is an array of disk-block addresses.
  • The index block serves as a lookup table for accessing the different blocks of a file.
  • The directory contains the address of the index block.
Advantages:
  • Efficient for random access.
  • Does not suffer from external fragmentation.
Disadvantages:
  • Requires additional index blocks, which increases overhead.
In summary, each method has its own trade-offs, and the choice depends on the specific system requirements and workload.

Below is a simple C program that demonstrates the implementation of the contiguous file allocation scheme. 
//****************************************************
//C program - contigious file allocation
//****************************************************
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define the maximum number of blocks (assuming 100 blocks)
#define MAX_BLOCKS 100

// Structure to represent a file
struct File {
    char filename[20];
    int start_block;
    int num_blocks;
};

// Function to allocate contiguous blocks for a file
void allocateContiguous(struct File* file, int startBlock, int numBlocks) {
    strcpy(file->filename, "my_file.txt");
    file->start_block = startBlock;
    file->num_blocks = numBlocks;
}

int main() {
    struct File myFile;

    // Allocate contiguous blocks starting from block 10
    allocateContiguous(&myFile, 10, 5);

    // Display file details
    printf("File Name: %s\n", myFile.filename);
    printf("Start Block: %d\n", myFile.start_block);
    printf("Number of Blocks: %d\n", myFile.num_blocks);

    return 0;
}
File Name: my_file.txt
Start Block: 10
Number of Blocks: 5

Below is a simple C program that demonstrates the implementation of the linked file allocation scheme. In this example, we’ll create a linked list of blocks to represent file allocation.

//****************************************************
//C program - linked file allocation
//****************************************************
#include <stdio.h>
#include <stdlib.h>

// Define the maximum number of blocks (assuming 100 blocks)
#define MAX_BLOCKS 100

// Structure to represent a block
struct Block {
    int block_number;
    struct Block* next;
};

// Function to allocate a new block
struct Block* allocateBlock(int blockNumber) {
    struct Block* newBlock = (struct Block*)malloc(sizeof(struct Block));
    newBlock->block_number = blockNumber;
    newBlock->next = NULL;
    return newBlock;
}

int main() {
    struct Block* head = NULL;
    struct Block* current = NULL;

    // Allocate blocks for a file (e.g., file with block numbers 10, 20, 30)
    head = allocateBlock(10);
    current = head;
    current->next = allocateBlock(20);
    current = current->next;
    current->next = allocateBlock(30);

    // Display the allocated blocks
    printf("Allocated blocks: ");
    current = head;
    while (current != NULL) {
        printf("%d ", current->block_number);
        current = current->next;
    }
    printf("\n");

    // Clean up (free memory)
    current = head;
    while (current != NULL) {
        struct Block* temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}

Allocated blocks: 10 20 30 

Indexed allocation is a file allocation method where each file has an associated index block that contains pointers to the actual data blocks on the disk. Let’s create a simple implementation in C for indexed allocation.
//****************************************************
//C program - indexed  file allocation
//****************************************************
#include <stdio.h>
#include <stdlib.h>

#define MAX_BLOCKS 100

// Structure to represent an index block
struct IndexBlock {
    int data_blocks[MAX_BLOCKS];
};

// Function to initialize an index block
void initializeIndexBlock(struct IndexBlock* indexBlock) {
    for (int i = 0; i < MAX_BLOCKS; ++i) {
        indexBlock->data_blocks[i] = -1; // Initialize with -1 (invalid block)
    }
}

// Function to allocate a data block for a file
int allocateDataBlock(struct IndexBlock* indexBlock, int blockNumber) {
    for (int i = 0; i < MAX_BLOCKS; ++i) {
        if (indexBlock->data_blocks[i] == -1) {
            indexBlock->data_blocks[i]=blockNumber;
            return 1; // Successfully allocated
        }
    }
    return 0; // No free space in the index block
}

// Function to read data from a file
void readData(struct IndexBlock* indexBlock, int fileBlockNumber) {
        int flag=0;
       for(int i=0;i<MAX_BLOCKS;i++) 
       {
         if (indexBlock->data_blocks[i] != -1 && fileBlockNumber==indexBlock->data_blocks[i]) 
           { printf("Reading data from block %d\n", indexBlock->data_blocks[i]);
            flag=1;
            
            }
         }
         
          if(flag==0)  printf("Block %d is not allocated.\n", fileBlockNumber);
     
    
}

int main() {
    struct IndexBlock indexBlock;
    initializeIndexBlock(&indexBlock);

    // Allocate data blocks for a file (example)
    allocateDataBlock(&indexBlock, 5);
    allocateDataBlock(&indexBlock, 8);
    allocateDataBlock(&indexBlock, 12);

    // Read data from specific file blocks (example)
    readData(&indexBlock, 5);
    readData(&indexBlock, 8);
    readData(&indexBlock, 10); // Not allocated
    
    return 0;
}
Reading data from block 5
Reading data from block 8
Block 10 is not allocated.

Comments

Post a Comment

Popular posts from this blog

CSL 204 OPERATING SYSTEM LAB KTU IV SEM CSE

About Me Syllabus Scheme Program List Linux Basics 1. Linux History and GNU 2. Linux Basic Features and Architecture 3. How to Install Linux 4. Install Linux Inside Windows using WSL 5. Free software 6. Linux Chronology 7 .Package Management 8 .Compile and install from source 9 .Important Directories 10. File Permissions 11. Special Permissions 12 .Shell 13. Bash shell in windows 10 14 .Basic Linux command for beginners 15. Input Output Redirection  16. Directory Commands 17. File Commands 18 .Communication Commands 19. Information Commands  20 .IO Commands   21 .Process Management Commands 22. Account Administration Commands 23. Pipes and Filters  24. Top 100 commands to learn.         Familiarization of Basic  Linux Commands- ls, mkdir, rmdir , rm, cat, cp, mv , chmod          User and Group management- useradd, userdel,groupadd,groupdel, passwd           Familiarization of basic  ...
Read more

FCFS and SJF

Image
CPU Scheduling in Operating Systems: In the context of operating systems, CPU scheduling involves determining which process (or task) should be executed next by the central processing unit (CPU). The goal is to maximize CPU utilization, minimize waiting time, and ensure fair allocation of resources. Various scheduling algorithms are used to achieve these objectives. First-Come-First-Serve (FCFS) Scheduling: Definition: FCFS is the simplest CPU scheduling algorithm. It is non-preemptive, meaning once a process starts executing, it cannot be interrupted until completion. Processes are placed in a queue based on their arrival time. The process that arrives first gets executed first. Execution Order : Processes are executed in the order they arrive. The process at the front of the queue is selected for execution. Advantages: Easy to implement. Minimal overhead. Disadvantages: Often results in long waiting times. Leads to the convoy effect (where a long process holds up other processes). Sh...
Read more

Banker's Algorithm- Deadlock Detection

The Banker's Algorithm is a deadlock avoidance algorithm used in operating systems to prevent deadlocks in a system with limited resources. It was developed by Edsger Dijkstra in 1965. The algorithm ensures that the system will allocate resources in such a way that it will avoid deadlock, even if resources are requested in an arbitrary order. Let's break down the Banker's Algorithm into steps: 1. System Initialization: At the beginning, the system must know the total number of resources of each type and the maximum demand of each process. It also needs to keep track of the currently available resources of each type. 2. Allocation: When a process requests resources, the system must check if granting those resources would put it in an unsafe state (i.e., could potentially lead to a deadlock). If the request can be granted without causing an unsafe state, the resources are allocated. Otherwise, the process must wait until the requested resources can be safely allocated. Safety...
Read more