Scribd Logo
Upload

Welcome to Scribd!

  • 25 views

    CSL 331 Algorithms

    Uploaded by

    Mohammed Ashiq
    The document describes four experiments involving CPU scheduling algorithms, the banker's algorithm for deadlock avoidance, and page replacement algorithms. Experiment 1 simulates FCFS, SJF, round robin, and priority scheduling algorithms. Experiment 2 implements the banker's algorithm to check for safe states and handle resource requests. Experiment 3 simulates FIFO, LRU, and LFU page replacement algorithms. Pseudocode is provided for the algorithms in each experiment.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CSL 331 Algorithms

    Uploaded by

    Mohammed Ashiq
    25 views5 pages
    The document describes four experiments involving CPU scheduling algorithms, the banker's algorithm for deadlock avoidance, and page replacement algorithms. Experiment 1 simulates FCFS, SJF, round robin, and priority scheduling algorithms. Experiment 2 implements the banker's algorithm to check for safe states and handle resource requests. Experiment 3 simulates FIFO, LRU, and LFU page replacement algorithms. Pseudocode is provided for the algorithms in each experiment.

    Original Title

    Csl 331 Algorithms

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes four experiments involving CPU scheduling algorithms, the banker's algorithm for deadlock avoidance, and page replacement algorithms. Experiment 1 simulates FCFS, SJF, round robin, and priority scheduling algorithms. Experiment 2 implements the banker's algorithm to check for safe states and handle resource requests. Experiment 3 simulates FIFO, LRU, and LFU page replacement algorithms. Pseudocode is provided for the algorithms in each experiment.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    25 views5 pages

    CSL 331 Algorithms

    Uploaded by

    Mohammed Ashiq
    The document describes four experiments involving CPU scheduling algorithms, the banker's algorithm for deadlock avoidance, and page replacement algorithms. Experiment 1 simulates FCFS, SJF, round robin, and priority scheduling algorithms. Experiment 2 implements the banker's algorithm to check for safe states and handle resource requests. Experiment 3 simulates FIFO, LRU, and LFU page replacement algorithms. Pseudocode is provided for the algorithms in each experiment.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    EXPERIMENT 1 : Simulate the following non preemptive CPU sheduling

    algorithms to find turnaround time and waiting time.


    a) FCFS b) SJF c) Round Robin(preemtive) d)Priority

    1.FIRST COME FIRST SERVE SCHEDULING

    AIM:
    Write a program for First Come First Serve Scheduling

    ALGORITHM:
    Step 1: Start
    Step 2: Enter the number of processors.
    Step 3: Enter the processes name, arrival time and burst time.
    Step 4: Make the waiting time of the first process as the arrival of the first process.
    Step 5: Calculate the waiting time of each process ie burst time – arrival time.
    Step 6: Calculate the turnaround time of each process ie waiting time + burst time
    Step7: Calculate average waiting time by adding waiting time of each process and divide by the
    total number of processes and also display it.
    Step 8: Calculate the average turnaround time and display it.
    Step 9: Call function display ()
    Step 10: Stop.
    display ( )
    Step 1: Start.
    Step 2: Display the process name.
    Step 3: Display waiting time under their respective processes.
    Step 4: Repeat step 2 and 3 for all processes.
    Step 5: Stop.

    2. SHORTEST JOB FIRST SCHEDULING

    AIM:
    Write a program for Shortest Job First Scheduling

    ALGORITHM:
    Step 1: Start
    Step 2: Enter the number of processors.
    Step 3: Enter the processes name, and burst time.
    Step 4: Sort processes in ascending order of the burst time, if they arrive within the
    burst time of the previous processes
    Step 5: Calculate the average turnaround time and display it.
    Step 6: Call function display ( ).
    Step 7: Stop.
    display ( )
    Step 1: Start.
    Step 2: Display the process name.
    Step 3: Display waiting time under their respective processes.
    Step 4: Repeat step 2 and 3 for all processes.
    Step 5: Stop

    3.PRIORITY SCHEDULING
    AIM:
    Write a program to perform priority scheduling

    ALGORITHM:
    Step 1: Start
    Step 2: Enter the number of processors.
    Step 3: Enter the processes name, priority and burst time.
    Step 4: Sort processes in ascending order of the priority.
    Step 5: Calculate and display the average waiting time and turnaround time.
    Step 7: Call function display()
    Step 10: Stop.
    display ( )
    Step 1: Start.
    Step 2: Display the process name.
    Step 3: Display waiting time under their respective processes.
    Step 4: Repeat step 2 and 3 for all processes.
    Step 5: Stop.

    4.ROUND ROBIN SCHEDULING

    AIM:
    Write a program to perform Round Robin scheduling

    ALGORITHM:
    Step 1: Start
    Step 2: Enter the number of processors.
    Step 3: Enter the time slice.
    Step 4: If burst time < time slice, then execute process completely, go to step 7
    Step 5: Execute the process upto the time slice and save the remaining burst time and
    start the next process.
    Step 6: Calculate and display the average waiting time and turnaround time.
    Step 7: Call function display()
    Step 8: Stop.
    display ( )
    Step 1: Start.
    Step 2: Display the process name.
    Step 3: Display waiting time under their respective processes.
    Step 4: Repeat step 2 and 3 for all processes.
    Step 5: Stop

    EXPERIMENT 2 : Implement the bankers algorithm for dead lock avoidance

    AIM:
    Write a program to implement the bankers algorithm for deadlock avoidance.

    ALGORITHM:
    Step 1: Start the program.
    Step 2: Get the values of resources and processes.
    Step 3: Get the avail value.
    Step 4: After allocation find the need value.
    Step 5: Check whether its possible to allocate.
    Step 6: If it is possible then the system is in safe state.
    Step 7: Else system is not in safety state.
    Step 8: If the new request comes then check that the system is in safety.
    Step 9: If not if we allow the request.
    Step 10: Stop the program.

    Safety Algorithm:
    Step 1: Work and Finish be the vector of length m and n respectively, Work=Available and
    Finish[i] =False.
    Step 2: Find an i such that both
    Finish[i] =False
    Need<=Work
    If no such I exists go to step 4.
    Step 3: work=work+Allocation, Finish[i] =True;
    Step 4: if Finish[1]=True for all I, then the system is in safe state.
    Resource request algorithm:
    Let Request i be request vector for the process Pi, If request i=[j]=k, then process Pi wants k
    instances of resource type Rj.
    Step 1: if Request<=Need I go to step 2. Otherwise raise an error condition.
    Step 2: if Request<=Available go to step 3. Otherwise Pi must since the resources are
    available.
    Step 3: Have the system pretend to have allocated the requested resources to process Pi by
    modifying the state as follows;

    Available=Available-Request I;
    Allocation I =Allocation +Request I;
    Need i=Need i-Request I;

    EXPERIMENT 3 : Simulate the following page replacement algorithms


    a) FIFO b) LRU c) LFU

    a) FIFO

    AIM:
    Write a program to implement FIFO page replacement algorithm.

    ALGORITHM:
    Step 1. Start to traverse the pages.

    • Step 2. If the memory holds fewer pages, then the capacity else goes to step 5.
    • Step 3. Push pages in the queue one at a time until the queue reaches its maximum capacity
    or all page requests are fulfilled.
    • Step 4. If the current page is present in the memory, do nothing.
    • Step 5. Else, pop the topmost page from the queue as it was inserted first.
    • Step 6. Replace the topmost page with the current page from the string.
    • Step 7. Increment the page faults.
    • Step 8. Stop
    b) LRU

    AIM:
    Write a program to implement LRU page replacement algorithm.

    ALGORITHM:

    Let capacity be the number of pages that


    memory can hold. Let set be the current
    set of pages in memory.

    1- Start traversing the pages.


    i) If set holds less pages than capacity.
    a) Insert page into the set one by one until
    the size of set reaches capacity or all
    page requests are processed.
    b) Simultaneously maintain the recent occurred
    index of each page in a map called indexes.
    c) Increment page fault
    ii) Else
    If current page is present in set, do nothing.
    Else
    a) Find the page in the set that was least
    recently used. We find it using index array.
    We basically need to replace the page with
    minimum index.
    b) Replace the found page with current page.
    c) Increment page faults.
    d) Update index of current page.

    2. Return page faults.

    c)LFU

    AIM:

    Write a program to implement LFU page replacement algorithm.

    ALGORITHM:
    Step-1 : Initialize count as 0.
    Step-2 : Create a vector / array of size equal to memory capacity.
    Create a map to store frequency of pages
    Step-3 : Traverse elements of pages[]
    Step-4 : In each traversal:
    if(element is present in memory):
    remove the element and push the element at the end
    increase its frequency
    else:
    if(memory is full)
    remove the first element and decrease frequency of 1st element
    Increment count
    push the element at the end and increase its frequency
    Compare frequency with other pages starting from the 2nd last page
    Sort the pages based on their frequency and time at which they arrive
    if frequency is same, then, the page arriving first must be placed first

    You might also like