What is Job Sequencing in Operating System?
Job sequencing is one of the crucial methods that is followed in the scheduling of the tasks in the operating system. An operating system is a program that manages the computer's resources, primarily allocating these tasks, among other programs. Some of the examples of Operating systems are Windows, macOS, Linux, etc.
The operating system is a crucial element for the computer system which provides many functionalities such as Security, Managing files and Jobs/tasks, I/O management, Communication, Accounting, Resource allocations, and many more.
Among the above-discussed functionalities, the most important one is Job sequencing; this is used to allocate sequences to the tasks that are to be performed whenever they are needed by the system or the machine. The tasks are arranged in an order where they are followed by one after another. These tasks contain crucial information to finish an objective assigned by the computer. In Job sequencing, each task is created to fulfil a certain objective, calculations, etc. These are called by the computer whenever they are necessary.
The main objective of Job sequencing is to arrange the jobs based on the outcomes they can produce and the time they have. This is called Job sequencing with deadlines. Where the tasks have a given time slot, the tasks must only complete their execution in the given time slot only. There are two types of approaches we use to execute the job sequencing, the Greedy method approach and the other is Dynamic programming approach. Each approach has its own advantages and disadvantages.
The Greedy approach works in such a way that the jobs are arranged in the order of their deadlines or profits. There are two ways. The first way is based on their deadlines, the order in which these are arranged based on their deadlines are in ascending order, or the order in which the deadlines are less. Because it will be easy to solve these in the least time required, another way is the dynamic programming way; the jobs are divided into subproblems and are calculated individually and then combined together to produce the final output.
These approaches depend on the requirement and the jobs with the deadlines; it is the user’s choice to choose from the approaches. Now let us understand the job sequencing with an example.
Job number | J1 | J2 | J3 | J4 | J5 |
Deadline | 4 | 1 | 5 | 3 | 2 |
Profit | 20 | 30 | 10 | 5 | 40 |
This is given job schedule and we have to choose an approach to solve the given problem, which gives the best profits in less time. We will choose the approach where we consider the deadlines first. This helps us to complete the tasks with lesser time.
Job number | J2 | J5 | J4 | J1 | J3 |
Deadline | 1 | 2 | 3 | 4 | 5 |
Profit | 30 | 40 | 5 | 20 | 10 |
Now we have arranged this into the order of the deadlines and the jobs are associated with some profits which they get when they complete the task within the deadline.
We have to calculate the total profit keeping in view that the deadlines play the important part in the chosen approach. The next step is to arrange these in the order which they will be first executed considering the deadlines.
- The Job 2 is first scheduled and then it will be completed in time 1.
- Job 5 is second in the list so; Job 5 is executed next after Job 2 which will be completed at time 3. Including the deadline which is 2.
- Job 4 is third which is scheduled at time 3 and is completed at time 4.
- Job 1 is fourth which will be scheduled at time 4 and will be completed at time 8.
- Job 3 is the last among all and is scheduled at time 8, after the execution of job 1. Job 3 is completed at time13.
We have arranged the jobs on their deadlines, now we have to calculate the profit from these jobs. The profits are also calculated based on the chosen approach in our case the priority is the early deadlines, we will choose the profits based on those jobs.
The profit will be: 30+40+5+20+10 = 105.
Now let us solve the problem in another approach from the greedy method, where we first consider the profits, we get.
Job number | J1 | J2 | J3 | J4 | J5 |
Deadline | 4 | 1 | 5 | 3 | 2 |
Profit | 20 | 30 | 10 | 5 | 40 |
The given problem, now arrange the jobs based on their profits in decreasing order.
Job number | J5 | J2 | J1 | J3 | J4 |
Deadline | 2 | 1 | 4 | 5 | 3 |
Profit | 40 | 30 | 30 | 10 | 5 |
Now that we have arranged them in decreasing order, calculate the jobs in the order the are scheduled.
- Job 5 will be scheduled at time 0 and is completed in time 2.
- Job 2 is scheduled at time 2 and is completed at time 4.
- Job 1 is scheduled at time 4, and is completed at time 8.
- Job 3 is scheduled at time 8 and is completed at time 13.
- Job 4 is scheduled at time 16 and will be completed at time 16.
We have also got the completion time of the above tasks and none of the tasks are completed after the allocated time frame. Calculate the profits.
Profits: 40 + 30 + 20 + 10 + 5 = 105
This way the Job sequencing is calculated and is completed based on the various approaches which are best suitable depending on the situation.