Question:
Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time.
\[
A (0, 10), \, B (2, 6), \, C (4, 3), \, D (6, 7).
\]
Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?
Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time.
\[
A (0, 10), \, B (2, 6), \, C (4, 3), \, D (6, 7).
\]
Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?
Show Hint
When solving CPU scheduling problems, use tables to calculate Completion Time, Turnaround Time, and Waiting Time for each process. Apply the appropriate algorithm rules, such as preemption in SRTF and non-preemption in NP-SJF.
Updated On: Jan 23, 2025
- SRTF = 6, NP-SJF = 7
- SRTF = 6, NP-SJF = 7.5
- SRTF = 7, NP-SJF = 7.5
- SRTF = 7, NP-SJF = 8.5
Hide Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
Non-Preemptive SJF Scheduling:
\[
\begin{array}{|c|c|c|c|c|c|}
\hline
Process & Arrival Time & Burst Time & Completion Time & Turnaround Time & Waiting Time
\hline A & 0 & 10 & 10 & 10 & 0
B & 2 & 6 & 19 & 17 & 11
C & 4 & 3 & 13 & 9 & 6
D & 6 & 7 & 26 & 20 & 13
\hline \end{array} \] The total average waiting time for NP-SJF is: \[ \text{Average Waiting Time} = \frac{0 + 11 + 6 + 13}{4} = \frac{30}{4} = 7.5. \] Preemptive SRTF Scheduling: \[ \begin{array}{|c|c|c|c|c|c|} \hline Process & Arrival Time & Burst Time & Completion Time & Turnaround Time & Waiting Time
\hline A & 0 & 10 & 26 & 26 & 16
B & 2 & 6 & 11 & 9 & 3
C & 4 & 3 & 7 & 3 & 0
D & 6 & 7 & 18 & 12 & 5
\hline \end{array} \] The total average waiting time for SRTF is: \[ \text{Average Waiting Time} = \frac{16 + 3 + 0 + 5}{4} = \frac{24}{4} = 6. \] Note: Turnaround Time is calculated as: \(\text{Completion Time} - \text{Arrival Time}\). Waiting Time is calculated as: \(\text{Turnaround Time} - \text{Burst Time}\). Final Answer: \[ \boxed{\text{(2) SRTF = 6, NP-SJF = 7.5}} \]
\hline A & 0 & 10 & 10 & 10 & 0
B & 2 & 6 & 19 & 17 & 11
C & 4 & 3 & 13 & 9 & 6
D & 6 & 7 & 26 & 20 & 13
\hline \end{array} \] The total average waiting time for NP-SJF is: \[ \text{Average Waiting Time} = \frac{0 + 11 + 6 + 13}{4} = \frac{30}{4} = 7.5. \] Preemptive SRTF Scheduling: \[ \begin{array}{|c|c|c|c|c|c|} \hline Process & Arrival Time & Burst Time & Completion Time & Turnaround Time & Waiting Time
\hline A & 0 & 10 & 26 & 26 & 16
B & 2 & 6 & 11 & 9 & 3
C & 4 & 3 & 7 & 3 & 0
D & 6 & 7 & 18 & 12 & 5
\hline \end{array} \] The total average waiting time for SRTF is: \[ \text{Average Waiting Time} = \frac{16 + 3 + 0 + 5}{4} = \frac{24}{4} = 6. \] Note: Turnaround Time is calculated as: \(\text{Completion Time} - \text{Arrival Time}\). Waiting Time is calculated as: \(\text{Turnaround Time} - \text{Burst Time}\). Final Answer: \[ \boxed{\text{(2) SRTF = 6, NP-SJF = 7.5}} \]
Was this answer helpful?
0
0
Top Questions on Lexical analysis
- Consider a 32-bit system with a 4 KB page size and page table entries of size 4 bytes each. Assume \(1 \, \text{KB} = 2^{10} \, \text{bytes}\). The OS uses a 2-level page table for memory management, with the page table containing an outer page directory and an inner page table. The OS allocates a page for the outer page directory upon process creation. The OS uses demand paging when allocating memory for the inner page table, i.e., a page of the inner page table is allocated only if it contains at least one valid page table entry.
An active process in this system accesses \(2000\) unique pages during its execution, and none of the pages are swapped out to disk. After it completes the page accesses, let \(X\) denote the minimum and \(Y\) denote the maximum number of pages across the two levels of the page table of the process. The value of \(X + Y\) is ............- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of 5 milliseconds, 500 sectors/track, 512-byte sectors. A file has content stored in 3000 sectors located randomly on the disk. Assuming average rotational latency, the total time (in seconds, rounded off to 2 decimal places) to read the entire file from the disk is ............
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider a multi-threaded program with two threads \(T1\) and \(T2\). The threads share two semaphores: \(s1\) (initialized to 1) and \(s2\) (initialized to 0). The threads also share a global variable \(x\) (initialized to 0). The threads execute the code shown below. \begin{verbatim} // code of T1 // code of T2 wait(s1); wait(s1); x = x+1; x = x+1; print(x); print(x); wait(s2); signal(s2); signal(s1); signal(s1); \end{verbatim} Which of the following outcomes is/are possible when threads \(T1\) and \(T2\) execute concurrently?
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider an array \(X\) that contains \(n\) positive integers. A subarray of \(X\) is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of \(X\) that contains at most two distinct integers. The code has two missing expressions labelled \((P)\) and \((Q)\). \begin{verbatim} int first=0, second=0, len1=0, len2=0, maxlen=0; for (int i=0; i<n; i++) { if (X[i] == first) { len2++; len1++; } else if (X[i] == second) { len2++; len1 = (P); second = first; } else { len2 = (Q); len1 = 1; second = first; } if (len2>maxlen) { maxlen = len2; } first = X[i]; } \end{verbatim} Which one of the following options gives the CORRECT missing expressions?
- GATE CS - 2024
- Compiler Design
- Lexical analysis
- Consider a process \(P\) running on a CPU. Which one or more of the following events will always trigger a context switch by the OS that results in process \(P\) moving to a non-running state (e.g., ready, blocked)?}
- GATE CS - 2024
- Compiler Design
- Lexical analysis
View More Questions
Questions Asked in GATE CS exam
- The number of distinct minimum-weight spanning trees of the following graph is ............ \begin{center} \includegraphics[width=0.5\textwidth]{59.png} \end{center}
- GATE CS - 2024
- Syntax Directed Translation
- Consider the following augmented grammar, which is to be parsed with an SLR parser. The set of terminals is \(\{a, b, c, d, \#, @\}\). \[ S' \rightarrow S \quad S \rightarrow SS \, | \, Aa \, | \, bAc \, | \, BC \, | \, bBa \quad A \rightarrow d\# \quad B \rightarrow @ \] Let \(I_0 = \text{CLOSURE}(\{S' \rightarrow \cdot S\}\). The number of items in the set \(GOTO(I_0, S)\) is ............
- GATE CS - 2024
- Syntax Directed Translation
- Let \(Z_n\) be the group of integers \(\{0, 1, 2, \dots, n - 1\}\) with addition modulo \(n\) as the group operation. The number of elements in the group \(Z_2 \times Z_3 \times Z_4\) that are their own inverses is ............
- GATE CS - 2024
- Indexed Address
- Let \(L_1\) be the language represented by the regular expression \(b^*ab^*(ab^*ab^*)^*\) and \(L_2 = \{ w \in (a + b)^* \mid |w| \leq 4 \\), where \(|w|\) denotes the length of string \(w\). The number of strings in \(L_2\) which are also in \(L_1\) is ............}
- GATE CS - 2024
- Miscellaneous
- A processor uses a 32-bit instruction format and supports byte-addressable memory access. The ISA of the processor has 150 distinct instructions. The instructions are equally divided into two types, namely R-type and I-type, whose formats are shown below. R-type Instruction Format: \begin{center} \setlength{\tabcolsep}{15pt} % Adjust column spacing \renewcommand{\arraystretch}{1.5} % Adjust row spacing \begin{tabular}{|c|c|c|c|c|} \hline OPCODE & UNUSED & DST Register & SRC Register1 & SRC Register2
\hline \end{tabular} \end{center} \vspace{0.5cm} I-type Instruction Format: \begin{center} \setlength{\tabcolsep}{15pt} % Adjust column spacing \renewcommand{\arraystretch}{1.5} % Adjust row spacing \begin{tabular}{|c|c|c|c|} \hline OPCODE & DST Register & SRC Register & \# Immediate Value/Address
\hline \end{tabular} \end{center} In the OPCODE, 1 bit is used to distinguish between I-type and R-type instructions, and the remaining bits indicate the operation. The processor has 50 architectural registers, and all register fields in the instructions are of equal size. Let \(X\) be the number of bits used to encode the UNUSED field, \(Y\) be the number of bits used to encode the OPCODE field, and \(Z\) be the number of bits used to encode the immediate value/address field. The value of \(X + 2Y + Z\) is ............- GATE CS - 2024
- Indexed Address
View More Questions