Code Monkey home page Code Monkey logo

csc1007-operating-system's Introduction

1. CSC1007 Operating System

1.1. Banker's Algorithm


Given six processes to be allocated and four resources types (A, B, C, D), the values of the allocation matrix of the processes for Allocation[6][4] and the values of the Max matrix of the processes is Max[6][4].

The user can input the total instances of each type, has the options to enter the allocation matrix and max matrix of the program. It shows the process of the whole safe state and unsafe state based on the calculation using Banker's Algorithm.

We have included some libraries, define some variable as well as function prototype.

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0

// Global variable
int noOfProcess;
int noOfResources;
int maxOfResources;
char resourcetype[] = {'A', 'B', 'C', 'D', 'E', 'F'};

//Function Prototype
void readResource(int total[], int noOfResources, int choice);
void readMax(int max[][noOfResources], int noOfProcess, int noOfResources, int total[]);
void readAllocation(int allocation[][noOfResources], int noOfProcess, int noOfResources, int max[][noOfResources]);
void calculateNeed(int allocation[][noOfResources], int max[][noOfResources], int need[][noOfResources], int noOfProcess, int noOfResources);
void calculateAvailable(int allocation[][noOfResources], int total[] ,int available[], int noOfProcess, int noOfResources);
void bankerAlgo(int max[][noOfResources], int need[][noOfResources], int available[], int flag[], int processIndex, int noOfProcess, int noOfResource);

1.1.1. Main Function for Banker's Algorithm


Description User can enter choice 1 for hardcoded and choice 2 for user input based on assignment question 1.

int main(){
    // Defining Variables 
    int choice;
    
    printf("Select Choice: \n1) Question 1  \n2) Question 1 with user input\n");
    printf("User Choice: ");
    scanf("%d", &choice);

    // Follows assignment requirement
    if (choice == 1){
        // Allocation and Max resources stated in the specification
        // initializing variables 
        noOfProcess = 6;
        noOfResources = 4;

        int allocation[6][4] = {{2, 1, 3, 3},
                                {2, 3, 1, 2},
                                {3, 3, 3, 1},
                                {2, 1, 3, 4},
                                {3, 2, 2, 5},
                                {2, 1, 2, 3}};
        int max[6][4] = {{7, 3, 4, 5},
                         {8, 6, 2, 5},
                         {9, 5, 5, 6},
                         {6, 4, 6, 5},
                         {8, 3, 2, 8},
                         {8, 3, 2, 3}};

        int need[noOfProcess][noOfResources];
        int available[noOfResources];
        int total[noOfResources];

        readResource(total, noOfResources, choice);
        calculateNeed(allocation, max, need, noOfProcess, noOfResources);
        calculateAvailable(allocation, total, available, noOfProcess, noOfResources);

        // Set each process flag to FALSE, indicating resources has not been allocated 
        // before calling Banker's Algorithm 
        int flag[noOfProcess];
        for (int i = 0; i < noOfProcess; i++){
            flag[i] = FALSE;
        }
        bankerAlgo(max, need, available, flag, 0, noOfProcess, noOfResources);
        // System is in safe state if Banker's Algorithm is able to run till completion
        printf("\n--- SYSTEM IS IN SAFE STATE ---\n");
    }
    // User is able to dymanically insert value of process and resources
    else if (choice == 2){

        printf("Enter the number of process(between 1-6): ");
        scanf("%d", &noOfProcess);
        
        if (noOfProcess < 1 || noOfProcess > 6){
            printf("Invalid number of process. \n");
            exit(0);
        }

        printf("Enter the number of resources(between 1-6): ");
        scanf("%d", &noOfResources);

        if (noOfResources < 1 || noOfResources > 6){
            printf("Invalid number of resources \n");
            exit(0);
        }

        // initializing variables 
        int allocation[noOfProcess][noOfResources];
        int max[noOfProcess][noOfResources];
        int need[noOfProcess][noOfResources];
        int available[noOfResources];
        int total[noOfResources];
        
        readResource(total, noOfResources, choice);
        readMax(max, noOfProcess, noOfResources, total);
        printf("\n");
        readAllocation(allocation, noOfProcess, noOfResources, max);
        calculateNeed(allocation, max, need, noOfProcess, noOfResources);
        calculateAvailable(allocation, total, available, noOfProcess, noOfResources);
        printf("\n");

        // Set each process flag to FALSE, indicating resources has not been allocated 
        // before calling Banker's Algorithm 
        int flag[noOfProcess];
        for (int i = 0; i < noOfProcess; i++){
            flag[i] = FALSE;
        }

        bankerAlgo(max, need, available, flag, 0, noOfProcess, noOfResources);
        // System is in safe state if Banker's Algorithm is able to run till completion
        printf("\n--- SYSTEM IS IN SAFE STATE ---\n");
        
    } else {
        printf("Entered Invalid option. \n");
        exit(0);
    }
}

1.1.2. Function for Banker's Algorithm


This is the calculation part for our Banker's Algorithm

// Function for Banker's Algorithm 
void bankerAlgo(int max[][noOfResources], int need[][noOfResources], int available[], int flag[], int processIndex, int noOfProcess, int noOfResources){ 
    int counterFlag = 0;
    // Base Case 
    // Check if all the process has been allocated resources
    for (int i = 0; i < noOfProcess; i ++){
        if (flag[i] == TRUE){
            counterFlag += 1;
        }
    }
    // If all process flag are TRUE; function will terminate
    if (counterFlag == noOfProcess){
        return;
    }
    // Recursive Case
    else {
        // Unsafe Safe: The available resource is not able to satisfy any of the process request
        if (processIndex > noOfProcess){
            printf("--- SYSTEM IS IN UNSAFE STATE ---\n");
            printf("Available instances: ");
            // display the number of available resource
            for (int i = 0; i < noOfResources; i++){
                printf("%d ", available[i]);
            }
            // display the number of resources needed by the processes that has not receive the max resources 
            printf("\n\nNEEDED INSTANCES FOR UNALLOCATED PROCESSES \n");
            for (int i = 0; i < noOfProcess; i++){
                if (flag[i] == FALSE){
                    printf("Process %d: ", i);
                    for (int j = 0; j < noOfResources; j++){
                        printf("%d ", need[i][j]);
                    }
                    printf("\n");
                }
            }
            exit(0);
        } else {
            int availableCounter = 0;
            // counter for (available - need) condition
            for (int resourceIndex = 0; resourceIndex < noOfResources; resourceIndex++){
                if (available[resourceIndex] - need[processIndex][resourceIndex] >= 0){
                    availableCounter += 1;
                }
            }
            // Check if there's enough available resource to satisfy process need
            // Check if the process flag is in FALSE state
            if ((availableCounter == noOfResources) && (flag[processIndex] == FALSE)){
                for (int resourceIndex = 0; resourceIndex < noOfResources; resourceIndex++){
                    available[resourceIndex] -= need[processIndex][resourceIndex];
                }
                flag[processIndex] = TRUE;

                // Display available resource after allocating resource to the process
                printf("Available Instance after Allocation to process P%d: [", processIndex);
                for (int i = 0; i < noOfResources; i++){
                     printf("%d, ", available[i]);
                }
                printf("]\n");

                // Process return all held resource back to the system
                for (int resourceIndex = 0; resourceIndex < noOfResources; resourceIndex++){
                    available[resourceIndex] += max[processIndex][resourceIndex];
                }

                // Display available resources after the process return the resource to the system
                printf("Available Instance after Retrieving resource from process P%d: [", processIndex);
                for (int i = 0; i < noOfResources; i++){
                     printf("%d, ", available[i]);
                }
                printf("]\n");

                // Continue to call itself recursive until all process flag is set to TRUE
                bankerAlgo(max, need, available, flag, 0, noOfProcess, noOfResources);
            } else {
                // Check not enough available rsource or process state is set to TRUE
                // increment process Index and call itself recursivly
                bankerAlgo(max, need, available, flag, processIndex + 1, noOfProcess, noOfResources);
            }
        }
    }
}

1.1.3. Read the total instances of resources


Description This function ask the users to enter the total number of instances and check if the number of instances hits the minimum requirement for the resources for question 1 hardcoded part.

//Functon to read the total instance of resources 
void readResource(int total[], int noOfResources, int choice){
    for (int i = 0; i < noOfResources; i++){
        printf("Enter total number of instances %c: ", resourcetype[i]);
        scanf("%d", &total[i]);
        // Resource needs to be a positive number
        if (total[i] < 0){
                printf("Minimum number of instance for resource %c must be a positive number \n", resourcetype[i]);
                exit(0);
        }
        if (choice == 1){
            int check[4] = {14,11,14,18};
            // Resource A, B, C, D needs to be larger than 14, 11, 14, 18 respectively 
            if (total[i] < check[i]){
                printf("Minimum number of instance for resource %c must be %d or above \n", resourcetype[i], check[i]);
                exit(0);
            }
        }
    }   
    printf("\n");
}

1.1.4. Read the max instances of the process needs


This function ask the users to enter the number of MAX allocation instances for the resources in the process and check if the number of instances allocate to the resources is more than the one they defined earlier on.

// Function to read the max instances a process needs
void readMax(int max[][noOfResources], int noOfProcess, int noOfResources, int total[]){
    for (int i = 0; i < noOfProcess; i++){
        printf("Enter number of MAX allocation instances for resources in process %d\n", i+1);
        for (int j = 0; j < noOfResources; j++){
            printf("Resource %c: ", resourcetype[j]);
            scanf("%d", &max[i][j]);
            // the max number of instance must be a positive number
            if (max[i][j] < 0){
                printf("Process instance number must be a positive number \n");
                exit(0);
            }
            // the max number of instance a process needs cannot be more than the total number of instance
            if (max[i][j] > total[j]){
                printf("Process instance number cannot be more than the number of total instance. \n");
                exit(0);
            }
        }
    }
}

1.1.5. Read the allocation resources for a process


This function ask the users to enter the number of allocation instances for resources in the process and check if the allocateed resources is more than the number of resources.

// Function to read the allocation resource for a process
void readAllocation(int allocation[][noOfResources], int noOfProcess, int noOfResources, int max[][noOfResources]){
    for (int i = 0; i < noOfProcess; i++){
        printf("Enter number of allocation instances for resources in process %d\n", i+1);
        for (int j = 0; j < noOfResources; j++){
            printf("Resource %c: ", resourcetype[j]);
            scanf("%d", &allocation[i][j]);
            // the allocation number of instance must be a positive number
            if (allocation[i][j] < 0){
                printf("Process instance number must be a positive number \n");
                exit(0);
            }
            // the allocation resource cannot be more than the number of resources
            if (allocation[i][j] > max[i][j]){
                printf("Process Allocation value cannot be more than process Max value. \n");
                exit(0);
            }
        }
    }
}

1.1.6. Calculate need matrix


This function calculates the need matrix

// Function to calculate Need matrix
// Need = Allocation - Need
void calculateNeed(int allocation[][noOfResources], int max[][noOfResources], int need[][noOfResources], int noOfProcess, int noOfResources){
    for (int i = 0; i < noOfProcess; i++){
        for (int j = 0; j < noOfResources; j++){
            need[i][j] = max[i][j] - allocation[i][j];
        }
    }
}

1.1.7. Calculate the available vector


This function calculate the available vector and check if the total number of allocated instances is more than the total number of instances.

// Function to calculate available vector
void calculateAvailable(int allocation[][noOfResources], int total[] ,int available[], int noOfProcess, int noOfResources){
    int totalAllocation[noOfResources];
    for (int i = 0; i < noOfResources; i++){
        totalAllocation[i] = 0;
    }
    for (int i = 0; i < noOfResources; i++){
        for (int j = 0; j < noOfProcess; j++){
            totalAllocation[i] += allocation[j][i];
        }
    }
    // Total number of allocated instances cannot be more than the total number of instances
    for (int i = 0; i < noOfResources; i++){
        available[i] = total[i] - totalAllocation[i];
        if(available[i] < 0){
            printf("Total Allocation of Instances cannot be more then total instances. \n");
            exit(0);
        }
    }
}

1.2. Memory Management in Operating System


Given with 12 memory partitions available: 160 KB, 350 KB, 650 KB, 80 KB, 410 KB, 50 KB, 720 KB, 905 KB, 570 KB, 130 KB, 260 KB, and 830 KB (in order). We would use the different algorithms to allocate 10 input processes with different sizes (in order).


1.2.1. Main Function for Memory Management


Function to allow user to enter the options and execute the functions.

//Libaries
#include <stdio.h>
#include "Q2.h"

//Main function
int main()
{
    int choice;
    bool exit_condition = true;
    printf("\nDynamic memory Allocation demonstration program\n");
    getMaxSize();
    getMinSize();
    getInput();
    while (exit_condition)
    {
        printf("\nPlease Enter one of the options: 1.First-fit, 2.Best-fit, 3.Worst-fit 4.Exit\n");
        scanf("%d", &choice);

        switch (choice)
        {
        case 1:
            firstFit();
            break;
        case 2:
            bestFit();
            break;
        case 3:
            worstFit();
            break;
        case 4:
            exit_condition = false;
            break;
        default:
            printf("Invalid options entered.\n");
        }
    }
    return 0;
}

1.2.2. Biggest Partition Size


Function to get the biggest partition size

//Get Biggest Partition size.
void getMaxSize()
{
    int partitionCount = sizeof(memoryPartitions) / sizeof(memoryPartitions[0]);
    Max = memoryPartitions[0];
    int count;
    for (count = 1; count < partitionCount; count++)
    {
        if (memoryPartitions[count] > Max)
        {
            Max = memoryPartitions[count];
        }
    }
}

1.2.3. Smallest Partition Size


Gettign the smallest partition size for the worst fit algorithm.

Function to get the smallest partition size

//Get Smallest Partition size.
void getMinSize()
{
    int partitionCount = sizeof(memoryPartitions) / sizeof(memoryPartitions[0]);
    Min = memoryPartitions[0];
    int count;
    for (count = 1; count < partitionCount; count++)
    {
        if (memoryPartitions[count] < Min)
        {
            Min = memoryPartitions[count];
        }
    }
}

1.2.4. User Input


User can input 10 process sizes to allow the system to compute the different algorithms.

Function to allow user to input

//Input Function
void getInput()
{
    int count;
    printf("\nMaximum Partition Size avaliable: %d KB\n", Max);
    for (count = 0; count < 10; count++)
    {
        printf("Enter size of processes: %d in KB\n", count + 1);
        scanf("%d", &userInput[count]);

        if (userInput[count] > Max)
        {
            printf("The size of procees entered exceeded the Maximum avaliable partition of: %d KB, Please re-enter\n", Max);
            count--;
        }
    }

    printf("\nProcess No. \tProcess Size\n");
    for (count = 0; count < 10; count++)
    {
        printf("\t%d \t%d KB\n", count + 1, userInput[count]);
    }
}

1.2.5. Reset Partition Size


User can re-select their options for algorithm, the function will reset the partition size.

Function to reset the partition size to the original size

//Reset Memory partition function.
void resetPartition()
{
    memoryPartitions[0] = 160;
    memoryPartitions[1] = 350;
    memoryPartitions[2] = 650;
    memoryPartitions[3] = 80;
    memoryPartitions[4] = 410;
    memoryPartitions[5] = 50;
    memoryPartitions[6] = 720;
    memoryPartitions[7] = 905;
    memoryPartitions[8] = 570;
    memoryPartitions[9] = 130;
    memoryPartitions[10] = 260;
    memoryPartitions[11] = 830;
}
//End

1.2.6. First Fit Algorithm


First Fit Algorithm is to allocate the process size to the first suitable block size.

Function to allocate the memory partitions

void firstFit()
{
    int processID, processSize, partitionID, partitionSize, count = 0;
    int assign = -1;
        
    //Match all process to suitable memory partition
    for (processID = 0; processID < 10; processID++){
        processSize = userInput[processID];
        for (partitionID = 0; partitionID < 12; partitionID++){
            partitionSize = memoryPartitions[partitionID];
                
            //assign memory partiton to process.
            if (partitionSize >= processSize){
                    assignPartitions[processID] = partitionSize;
                    partitionSize -= processSize;
                    assign = partitionID;
                    break;
                }
                //do not need to display if partition is not allocated
                else{
                    assignPartitions[processID] = 0;
                } 
            }

            //Check if memorypartition is assigned to a process. if so empty it from array.
            if (assign >= 0){
                memoryPartitions[assign] = 0;
            }
            else{
                unassignProcess[processID] = 0;
            }
        }

        //Print allocated process
        printf("\nAllocated Process");
        printf("\nProcess No.\tProcess Size.\tAllocated Memory Size.\n");
        for (processID = 0; processID < 10; processID++)
        {
            if (assignPartitions[processID] != 0)
            {
                printf("%d \t\t%d KB \t\t%d KB\n", processID + 1, userInput[processID], assignPartitions[processID]);
            }
        }

        //Print unallocated process
        printf("\nUnallocated Process");
        printf("\nProcess No.\tProcess Size.\n");
        for (processID = 0; processID < 10; processID++)
        {
            if (assignPartitions[processID] == 0)
            {
                printf("%d \t\t%d KB\n", processID + 1, userInput[processID]);
            }
        }

        //Print available memory parition.
        printf("\nAvaliable Memory Partition");
        printf("\nParition Size.\n");
        for (count = 0; count < 12; count++)
        {
            if (memoryPartitions[count] != 0)
            {
                printf("%d KB\n", memoryPartitions[count]);
            }
        }

    //Reset memoryPartition array to default state at start.
    resetPartition();
}

1.2.7. Best Fit Algorithm


Best Fit Algorithm is to allocate the process size to the smallest

Function to allocate the memory partitions

//Bestfit function
void bestFit()
{
    int processID, processSize, partitionID, partitionSize, smallID, differences, count = 0;

    //Match all process to memory partition
    for (processID = 0; processID < 10; processID++)
    {
        int assign = -1;
        getMaxSize();
        int smallest = Max;
        processSize = userInput[processID];

        //Find the best-fit memory partition to process size
        for (partitionID = 0; partitionID < 12; partitionID++)
        {
            partitionSize = memoryPartitions[partitionID];
            //Check if memory partition been allocated
            if (partitionSize != 0)
            {
                differences = partitionSize - processSize;

                //Check if difference is negative.
                if (differences >= 0)
                {
                    //assign memory partiton to process.
                    if (differences < smallest)
                    {
                        smallest = differences;
                        assignPartitions[processID] = partitionSize;
                        assign = partitionID;
                    }
                }
            }
        }

        //Check if memorypartition is assigned to a process. if so empty it from array.
        if (assign >= 0)
        {
            memoryPartitions[assign] = 0;
        }
        else
        {
            unassignProcess[processID] = 0;
        }
    }

    //print allocated process
    printf("\nAllocated Process");
    printf("\nProcess No.\tProcess Size.\tAllocated Memory Size.\n");
    for (processID = 0; processID < 10; processID++)
    {
        if (unassignProcess[processID] != 0)
        {
            printf("%d \t\t%d KB \t\t%d KB\n", processID + 1, userInput[processID], assignPartitions[processID]);
        }
    }

    //Print Unallocated Process
    printf("\nUnallocated Process");
    printf("\nProcess No.\tProcess Size.\n");
    for (processID = 0; processID < 10; processID++)
    {
        if (unassignProcess[processID] == 0)
        {
            printf("%d \t\t%d KB\n", processID + 1, userInput[processID]);
        }
    }

    //Print Avliable memory parition.
    printf("\nAvaliable Memory Partition");
    printf("\nParition Size.\n");
    for (count = 0; count < 12; count++)
    {
        if (memoryPartitions[count] != 0)
        {
            printf("%d KB\n", memoryPartitions[count]);
        }
    }

    //Reset memoryPartition array to default state at start.
    resetPartition();
}

1.2.8. Worst Fit Algorithm


Worst Fit Algorithm is to allocate the process size to the largest block size first.

Function to allocate the memory partitions

//Worstfit function
void worstFit(){
    int processID, processSize, partitionID, partitionSize, smallID, differences, count = 0;

    //Match all process to memory partition
    for (processID = 0; processID < 10; processID++)
    {
        int assign = -1;
        getMinSize();
        int largest = Min;
        processSize = userInput[processID];

        //Find the best-fit memory partition to process size
        for (partitionID = 0; partitionID < 12; partitionID++)
        {
            partitionSize = memoryPartitions[partitionID];
            //Check if memory partition been allocated
            if (partitionSize != 0)
            {
                differences = partitionSize - processSize;

                //Check if difference is negative.
                if (differences >= 0)
                {
                    //assign memory partiton to process.
                    if (differences > largest)
                    {
                        largest = differences;
                        assignPartitions[processID] = partitionSize;
                        assign = partitionID;
                    }
                }
            }
        }

        //Check if memorypartition is assigned to a process. if so empty it from array.
        if (assign >= 0)
        {
            memoryPartitions[assign] = 0;
        }
        else
        {
            unassignProcess[processID] = 0;
        }
    }

    //print allocated process
    printf("\nAllocated Process");
    printf("\nProcess No.\tProcess Size.\tAllocated Memory Size.\n");
    for (processID = 0; processID < 10; processID++)
    {
        if (unassignProcess[processID] != 0)
        {
            printf("%d \t\t%d KB \t\t%d KB\n", processID + 1, userInput[processID], assignPartitions[processID]);
        }
    }

    //Print Unallocated Process
    printf("\nUnallocated Process");
    printf("\nProcess No.\tProcess Size.\n");
    for (processID = 0; processID < 10; processID++)
    {
        if (unassignProcess[processID] == 0)
        {
            printf("%d \t\t%d KB\n", processID + 1, userInput[processID]);
        }
    }

    //Print Avliable memory parition.
    printf("\nAvaliable Memory Partition");
    printf("\nParition Size.\n");
    for (count = 0; count < 12; count++)
    {
        if (memoryPartitions[count] != 0)
        {
            printf("%d KB\n", memoryPartitions[count]);
        }
    }

    //Reset memoryPartition array to default state at start.
    resetPartition();
}

csc1007-operating-system's People

Contributors

jzxr avatar tsuisauchi avatar jyongg avatar junhaowg avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.