in Operating System
8,714 views
5 votes
5 votes

Consider a job scheduling problem with 4 jobs $J_1, J_2, J_3$ and $J_4$ with corresponding deadlines: $(d_1, d_2, d_3, d_4) = (4, 2, 4, 2)$. Which of the following is not a feasible schedule without violating any job schedule?

  1. $J_2, J_4, J_1, J_3$
  2. $J_4, J_1, J_2, J_3$
  3. $J_4, J_2, J_1, J_3$
  4. $J_4, J_2, J_3, J_1$
in Operating System
by
2699 3558 3939
8.7k views

Subscribe to GO Classes for GATE CSE 2022

2 Answers

11 votes
11 votes
 
Best answer

TO OPTIMIZE AND TO GET A FEASIBLE SOLUTION WE HAVE TO FINISH ALL THE JOBS WITH IN THEIR DEAD LINE.

SINCE THE DEADLINE OF J2 AND J4 ARE 2.SO THEY MUST BE COMPLETED BY 2.SO WE CAN SCHEDULE ANY ONE 

THAT IS J2 OR J4..

IN OPTION C,D J4 IS SCHEDULED FIRST AND THEN J2 AND

IN OPTION A, FIRST J2 THEN J4             SO WE CAN ABLE TO SCHEDULE OTHER 2 JOBS

NOW CONSIDER OPTION B

J4 IS SCHEDULED AND NEED TO BE COMPLETED ....BY 2  ---NO PROBLEM

J1 IS SCHEDULED AND NEED TO BE COMPLETED ....BY 4     --NO PROBLEM

BUT NOW AS J2 SHOULD COME BEFORE TIME 2..BUT WE SCHEDULED J1....SO J2 CANT BE SCHEDULED

LEADS TO A UNFEASIBLE  SOL.

 

selected by
by
21 55 133

5 Comments

Very good explanation.
1
1
nice explanation
1
1
edited by
What does it mean that J2 and J4 should be completed by 2?

If we assign J4 at time 1 and assign J2 at time 2 than how will both of them be completed by time 2?
0
0
its assuming run time is 1 unit only .. start from 0 --1--2--3--4 now schedule them
0
0

Option B

 J4     J1    

      1             2              3           4

 

now we can’t scheduled J2 bcz deadline up to 2 already full

0
0
0 votes
0 votes

Option A: 2,2,4,4. No problem.

Option B: 2,4,2,4. The third job in this sequence had to be completed under 2 time units. But it took 3 time units. This isn't an optimal solution, hence the answer.

Option C: 2,2,4,4. No problem.

Option D: 2,2,4,4. No problem.

by
4 8 39
Answer:

Related questions