Assignment Question - PGDCA

Questions-1.  Consider the following set of processes, with the length of the CPU burst time given in milliseconds.

The processes are assumed to have arrived in the order P1, P2, P3, P4 and P5 and all of them have arrived at time 0.

a. Draw corresponding Gantt charts illustrating the execution of these processes using FCFS, SJF, SRTN, Priority based scheduling/even-driven scheduling and Round Robin (quantum=2) scheduling algorithms.

b. What is the turnaround time of each process for each of the scheduling algorithm in (a)?

c. What is the waiting time of each process for each of the scheduling algorithm in (a)?

d. Which of the schedules in (a) results in minimal average waiting time (overall processes)?

Answer :

Process Information

(a) Gantt Charts

1. First Come First Serve (FCFS) Scheduling

In FCFS, processes are scheduled in the order they arrive.

• Gantt Chart:

2. Shortest Job First (SJF) Scheduling

In SJF, the process with the shortest burst time is executed next. All processes arrive at time 0, so we sort them by burst time.

• Order of Execution: $P3\to P5\to P2\to P4\to P1$

• Gantt Chart:

3. Shortest Remaining Time Next (SRTN) Scheduling

SRTN is a preemptive version of SJF. Whenever a new process arrives, it can preempt the running process if it has a shorter remaining time.

• Execution: $P3\to P5\to P2\to P4\to P1$

  • P3 (executes fully)
  • P5 (executes fully)
  • P2 (executes fully)
  • P4 (executes fully)
  • P1 (executes fully)

• Gantt Chart:

4. Priority-Based Scheduling

In priority scheduling, the process with the highest priority (lowest number) is selected first.

• Order of Execution (based on priority): $P2\to P3\to P5\to P1\to P4$

• Gantt Chart:

5. Round Robin Scheduling (Quantum = 2)

In Round Robin, processes are given a fixed time quantum (2 ms here). If a process isn't finished within that quantum, it's moved to the back of the queue.

• Order of Execution (Rotating based on time quantum of 2):

(b) Turnaround Time (TAT)

Turnaround time is calculated as:

$\text{Turnaround Time}=\text{Completion Time}-\text{Arrival Time}$

• For each scheduling algorithm, calculate when each process finishes.

1. FCFS:

2. SJF:

3. SRTN:

4. Priority-Based:

5. Round Robin (Quantum = 2):

(c) Waiting Time (WT)

Waiting time is calculated as:

$\text{Waiting Time}=\text{Turnaround Time}-\text{Burst Time}$

1. FCFS:

2. SJF:

3. SRTN:

4. Priority-Based:

5. Round Robin (Quantum = 2):

(d) Minimal Average Waiting Time

• To find the minimal average waiting time, we compute the average for each algorithm:

1. FCFS:

2. SJF:

3. SRTN:

4. Priority-Based:

5. Round Robin:

Questions -2. Consider the following page-reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 

How many page faults would occur for the following replacement algorithms, assuming three frames? Remember all frames are initially empty. a. FIFO replacement b. LRU replacement c. Optimal Mention the merits and demerits of each of the above algorithms.

Answer :

To determine the number of page faults for the given page-reference string using three different page replacement algorithms (FIFO, LRU, and Optimal), let's analyze each algorithm step by step.

Page-Reference String

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

a. FIFO (First-In, First-Out) Replacement

In FIFO, the oldest page is replaced first.

• Frames: Initially empty: []
• Step by Step:
  1. Page 1: Fault → [1]
  2. Page 2: Fault → [1, 2]
  3. Page 3: Fault → [1, 2, 3]
  4. Page 4: Fault → [2, 3, 4] (1 replaced)
  5. Page 2: Hit → [2, 3, 4]
  6. Page 1: Fault → [3, 4, 1] (2 replaced)
  7. Page 5: Fault → [4, 1, 5] (3 replaced)
  8. Page 6: Fault → [1, 5, 6] (4 replaced)
  9. Page 2: Fault → [5, 6, 2] (1 replaced)
  10. Page 1: Fault → [6, 2, 1] (5 replaced)
  11. Page 2: Hit → [6, 2, 1]
  12. Page 3: Fault → [2, 1, 3] (6 replaced)
  13. Page 7: Fault → [1, 3, 7] (2 replaced)
  14. Page 6: Fault → [3, 7, 6] (1 replaced)
  15. Page 3: Hit → [3, 7, 6]
  16. Page 2: Fault → [7, 6, 2] (3 replaced)
  17. Page 1: Fault → [6, 2, 1] (7 replaced)
  18. Page 2: Hit → [6, 2, 1]
  19. Page 3: Fault → [2, 1, 3] (6 replaced)
  20. Page 6: Fault → [1, 3, 6] (2 replaced)

Total Page Faults (FIFO): 12

b. LRU (Least Recently Used) Replacement

In LRU, the least recently used page is replaced.

• Frames: Initially empty: []
• Step by Step:
  1. Page 1: Fault → [1]
  2. Page 2: Fault → [1, 2]
  3. Page 3: Fault → [1, 2, 3]
  4. Page 4: Fault → [2, 3, 4] (1 replaced)
  5. Page 2: Hit → [2, 3, 4]
  6. Page 1: Fault → [3, 4, 1] (2 replaced)
  7. Page 5: Fault → [4, 1, 5] (3 replaced)
  8. Page 6: Fault → [1, 5, 6] (4 replaced)
  9. Page 2: Fault → [5, 6, 2] (1 replaced)
  10. Page 1: Fault → [6, 2, 1] (5 replaced)
  11. Page 2: Hit → [6, 2, 1]
  12. Page 3: Fault → [2, 1, 3] (6 replaced)
  13. Page 7: Fault → [1, 3, 7] (2 replaced)
  14. Page 6: Fault → [3, 7, 6] (1 replaced)
  15. Page 3: Hit → [3, 7, 6]
  16. Page 2: Fault → [7, 6, 2] (3 replaced)
  17. Page 1: Fault → [6, 2, 1] (7 replaced)
  18. Page 2: Hit → [6, 2, 1]
  19. Page 3: Fault → [2, 1, 3] (6 replaced)
  20. Page 6: Fault → [1, 3, 6] (2 replaced)

Total Page Faults (LRU): 12

c. Optimal Replacement

In Optimal, the page that will not be used for the longest time in the future is replaced.

• Frames: Initially empty: []
• Step by Step:
  1. Page 1: Fault → [1]
  2. Page 2: Fault → [1, 2]
  3. Page 3: Fault → [1, 2, 3]
  4. Page 4: Fault → [2, 3, 4] (1 replaced; will not be used again)
  5. Page 2: Hit → [2, 3, 4]
  6. Page 1: Fault → [3, 4, 1] (2 replaced; used in future)
  7. Page 5: Fault → [4, 1, 5] (3 replaced; used in future)
  8. Page 6: Fault → [1, 5, 6] (4 replaced)
  9. Page 2: Fault → [5, 6, 2] (1 replaced; used in future)
  10. Page 1: Fault → [6, 2, 1] (5 replaced)
  11. Page 2: Hit → [6, 2, 1]
  12. Page 3: Fault → [2, 1, 3] (6 replaced)
  13. Page 7: Fault → [1, 3, 7] (2 replaced)
  14. Page 6: Fault → [3, 7, 6] (1 replaced)
  15. Page 3: Hit → [3, 7, 6]
  16. Page 2: Fault → [7, 6, 2] (3 replaced)
  17. Page 1: Fault → [6, 2, 1] (7 replaced)
  18. Page 2: Hit → [6, 2, 1]
  19. Page 3: Fault → [2, 1, 3] (6 replaced)
  20. Page 6: Fault → [1, 3, 6] (2 replaced)

Total Page Faults (Optimal): 9

Summary of Page Faults

• FIFO: 12 faults
• LRU: 12 faults
• Optimal: 9 faults

Merits and Demerits

FIFO (First-In, First-Out)

• Merits:
  • Simple to implement and understand.
  • No need for future knowledge of references.
• Demerits:
  • Can lead to Belady's anomaly (more frames can cause more faults).
  • Does not consider page usage frequency.

LRU (Least Recently Used)

• Merits:
  • Better performance than FIFO in many cases.
  • Intuitive, as it considers the recent usage pattern.
• Demerits:
  • More complex to implement, requiring tracking of page usage.
  • High overhead due to the need to maintain usage order.

Optimal

• Merits:
  • Provides the best possible performance (fewest page faults).
  • Useful as a benchmark for evaluating other algorithms.
• Demerits:
  • Requires future knowledge of reference strings, which is impractical in real systems.
  • Not implementable in a standard operating environment.

Questions-4.  Write a program in C to implement Banker’s Algorithm to avoid Deadlock. Also explain the code briefly.

<!--[if gte mso 9]><xml> </xml><![endif]--><!--[if gte mso 9]><xml> Normal 0 false false false EN-US X-NONE X-NONE </xml><![endif]--><!--[if gte mso 9]><xml> </xml><![endif]--><!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin-top:0in; mso-para-margin-right:0in; mso-para-margin-bottom:8.0pt; mso-para-margin-left:0in; line-height:107%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri",sans-serif; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} </style> <![endif]-->

Program to Implement Banker’s Algorithm in C

The Banker's Algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra. It tests whether a safe sequence exists when a process requests a resource, thereby preventing deadlock.

Here is the code for implementing the Banker's Algorithm:

#include

void
calculateNeed(int need[][10], int max[][10], int allot[][10], int P, int R) {

    // Calculate the need matrix

    for (int i = 0; i < P>

        for (int j = 0; j < R>

            need[i][j] = max[i][j] -
allot[i][j];

        }

    }

}

int
checkSafe(int processes[], int avail[], int max[][10], int allot[][10], int P,
int R) {

    int need[10][10];

    calculateNeed(need, max, allot, P, R);

    int finish[10] = {0}; 

    int safeSeq[10];  

    int work[10];

    for (int i = 0; i < R>

        work[i] = avail[i];

    }

    int count = 0;

    while (count < P>

        int found = 0;

        for (int p = 0; p < P>

            if (finish[p] == 0) {

                int j;

                for (j = 0; j < R>

    

        
			


			


    


                    

                Previous Post
                

                    

                        

                            
                                Shape and Arrangement Puzzles – Complete Reasoning Notes & 50 MCQs                            
                        
                    
                
            
        
                    

                Next Post
                

                    

                        

                            
                                Represent (-55.25)10 and (0.03125)10 in IEEE 754 single precision format.                            
                        
                    
                
            
        
    


 
   




    

    

        Advertisement
    








    

        
        Why This Content Matters
    

    

        This content is prepared to help students and competitive-exam aspirants
        understand important topics, revise key information, and strengthen their
        exam preparation.
    

    

        
Quickly revise important facts and concepts
        
Improve General Knowledge and exam awareness
        
Support preparation for competitive and government exams
        
Build a consistent and effective study routine
    



			



		


	

    


        
        

            
        

        
        


            
                
                About the Author
            

            

                Quizer Team
                
            

            

                The Quizer Team creates exam-focused educational content, current affairs, general knowledge, study notes, and preparation resources to help students and competitive-exam aspirants learn, practice, and stay updated.            

            

                
                    
                    Educational Content
                

                
                    
                    Exam Focused
                

                
                    
                    Learning Resources