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. Shell Programming 1. Shell Script 2. Arithmetic Expressions 3. Special Shell Variables 4. Shell Script for getting important info 5. if and case statement 6. looping statements while,until,for 7. Menu driven Programs 8. GUI Menus 9. Functions in scripts 10. String Handling 11. Command line arguments in scripts
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

Shared Memory Inter-Process Communication ( IPC)

Shared memory Inter-Process Communication (IPC) in Linux allows processes to communicate by sharing a region of memory. This method is efficient because it avoids the overhead of copying data between processes. Here's how shared memory IPC is typically done in Linux: Create a Shared Memory Segment: To use shared memory IPC, you need to create a shared memory segment. This is done using the shmget() system call, which allocates a new shared memory segment or obtains the identifier of an existing one. You specify the size of the shared memory segment and some permissions. Attach the Shared Memory Segment: Once you have obtained the identifier for the shared memory segment, you need to attach it to the address space of your process. This is done using the shmat() system call. This call returns the address of the shared memory segment in your process's address space. Accessing the Shared Memory: After attaching the shared memory segment to your process's address space, you c
Read more