4.7 A multiprocessor with eight processors has 20attached tape drives. There is a large number of jobs submitted tothe system that each require a maxi

jernplate8

jernplate8

Answered question

2021-05-12

4.7 A multiprocessor with eight processors has 20attached tape drives. There is a large number of jobs submitted tothe system that each require a maximum of four tape drives tocomplete execution. Assume that each job starts running with onlythree tape drives for a long period before requiring the fourthtape drive for a short period toward the end of its operation. Alsoassume an endless supply of such jobs.
a) Assume the scheduler in the OS will not start a job unlessthere are four tape drives available. When a job is started, fourdrives are assigned immediately and are not released until the jobfinishes. What is the maximum number of jobs that can be inprogress at once? What is the maximum and minimum number of tapedrives that may be left idle as a result of this policy?
b) Suggest an alternative policy to improve tape driveutilization and at the same time avoid system deadlock. What is themaximum number of jobs that can be in progress at once? What arethe bounds on the number of idling tape drives?

Answer & Explanation

Nathalie Redfern

Nathalie Redfern

Skilled2021-05-14Added 99 answers

At most 20/4 =5 processes can be active at any one point in time. Since, at most one of those drives can be idle in each process, at most 5 drives could be idle. It is also possible that no drives are idle, as all processes are using their full complement at that point in time.
(b) Allocate the last drive for each process “upon demond”, thus, each process would start with 3 drives. This means that 20/3 =6 processes could be active at any time. The minimum number of drives available would still be 0, but the maximum would be 2.
Note that the fact that there could only be 2 drives indicates that a seventh process could not start, and there is no dead lock resulting.

Andre BalkonE

Andre BalkonE

Skilled2023-05-13Added 110 answers

a) In this scenario, each job requires a maximum of four tape drives to complete execution. The scheduler will not start a job unless there are four tape drives available. Once a job is started, it retains all four drives until it finishes. Let's analyze the situation.
Let N be the maximum number of jobs that can be in progress at once, and let D be the number of idle tape drives. Since each job requires four tape drives, we have the following equation:
4N20
This equation ensures that the total number of tape drives required by all the jobs in progress does not exceed the available tape drives. Solving for N:
N204
N5
Therefore, the maximum number of jobs that can be in progress at once is 5.
To determine the maximum number of idle tape drives, we need to consider the worst-case scenario where all jobs are in progress and require exactly four tape drives each. In this case, the number of idle tape drives, D, is given by:
D=20(4N)
D=20(4×5)
D=2020
D=0
So, the maximum number of idle tape drives is 0.
In this policy, the minimum number of idle tape drives would occur when there are no jobs in progress. In that case, D=20, indicating that all tape drives are idle.
b) To improve tape drive utilization and avoid system deadlock, we can implement a policy where jobs are allowed to start with fewer than four tape drives. This policy ensures that jobs can make progress even if all four tape drives are not immediately available.
Let's consider a policy where jobs can start with three tape drives. Once a job starts with three drives, it can request the fourth drive when it reaches the final phase of its execution. This policy ensures that a job can always make progress with at least three drives, reducing the chances of deadlock.
To calculate the maximum number of jobs that can be in progress at once, we'll assume that each job starts with three tape drives and requires the fourth drive later. Let N be the maximum number of jobs that can be in progress at once using this policy. We have the following equation:
3N20
Solving for N:
N203
N6.6
Since the number of jobs must be an integer, the maximum number of jobs that can be in progress at once using this policy is 6.
To determine the bounds on the number of idling tape drives, we consider the worst-case scenario where all six jobs are in progress and each job requires three tape drives initially. The number of idle tape drives, D, is given by:
D=20(3N)
D=20(3×6)
D=2018
D=2
So, the maximum number of idle tape drives is 2 using this policy.
The minimum number of idle tape drives would occur when there are no jobs in progress, similar to the previous policy. In that case, D=20, indicating that all tape drives are idle.
Therefore, the suggested alternative policy allows for a maximum of 6 jobs in progress at once, with a maximum of 2 idle tape drives.
Nick Camelot

Nick Camelot

Skilled2023-05-13Added 164 answers

Result:
- The maximum number of jobs that can be in progress at once is 19.
- The maximum number of idle tape drives is 0.
Explanation:
a) Let's solve part (a) first.
We have a multiprocessor system with eight processors and 20 attached tape drives. Each job requires a maximum of four tape drives to complete execution. Jobs start running with three tape drives and require the fourth tape drive only towards the end.
The maximum number of jobs that can be in progress at once is limited by the number of available tape drives. Since each job requires four tape drives, we can divide the total number of tape drives by four to find the maximum number of jobs.
Maximum number of jobs=204=5
Therefore, the maximum number of jobs that can be in progress at once is 5.
To find the maximum number of idle tape drives, we need to consider a scenario where all five jobs are in progress simultaneously. In this case, each job is using four tape drives, resulting in a total of 5×4=20 tape drives being used.
Since we initially had 20 tape drives, in this scenario, there are no idle tape drives.
Now, let's consider the minimum number of idle tape drives. The minimum number of idle tape drives occurs when all available tape drives are utilized except for one. This scenario happens when there are four jobs in progress, each using four tape drives, resulting in a total of 4×4=16 tape drives being used.
Since we initially had 20 tape drives, the minimum number of idle tape drives is 2016=4.
Therefore, the maximum number of jobs that can be in progress at once is 5, and the maximum number of idle tape drives is 0, while the minimum number of idle tape drives is 4.
b) Now, let's suggest an alternative policy to improve tape drive utilization and avoid system deadlock.
One possible alternative policy is to use a dynamic allocation approach. Instead of requiring four tape drives to be available before starting a job, we can allow jobs to start with three tape drives and allocate the fourth tape drive whenever it becomes available.
This policy ensures that jobs can start execution as soon as three tape drives are available, increasing overall system throughput.
To determine the maximum number of jobs that can be in progress at once using this policy, we need to consider the number of tape drives available when the system is fully utilized. In this case, each job uses three tape drives initially, and the remaining tape drives are allocated as soon as they become available.
The maximum number of jobs can be calculated as:
Maximum number of jobs=Total tape drivesIdle tape drives after all jobs started=201=19
Therefore, the maximum number of jobs that can be in progress at once using this alternative policy is 19.
The bounds on the number of idling tape drives can be calculated by considering the scenario where all 19 jobs are in progress simultaneously. Each job uses three tape drives initially, so the total number of tape drives used is 19×3=57.
Since we initially had 20 tape drives, the number of idle tape drives is 2057=37.
However, negative idle tape drives are not meaningful in this context. Therefore, we can say that the minimum number of idle tape drives is 0.
Mr Solver

Mr Solver

Skilled2023-05-13Added 147 answers

Step 1:
a) To determine the maximum number of jobs that can be in progress at once and the maximum and minimum number of tape drives that may be left idle, we can analyze the given scenario.
Let's assume N represents the maximum number of jobs that can be in progress at once.
Since each job requires a maximum of four tape drives, in order for a job to start, there must be at least four tape drives available. Therefore, the maximum number of jobs that can be in progress at once is equal to the maximum number of sets of four tape drives that can be formed from the available 20 tape drives.
The number of sets of four tape drives that can be formed from k available tape drives is given by the combination formula (k4).
Therefore, we have:
(k4)N
Solving this inequality for k, we can find the maximum number of tape drives required to support N jobs:
(k4)N
k!4!(k4)!N
k(k1)(k2)(k3)4·3·2·1N
k(k1)(k2)(k3)24N
Now, we need to find the maximum and minimum number of tape drives that may be left idle as a result of this policy.
To maximize the number of idle tape drives, we need to minimize the number of tape drives used for the maximum number of jobs. We can achieve this by setting k to the maximum value that satisfies the inequality above. Thus, we have:
kmax(kmax1)(kmax2)(kmax3)24=N
To minimize the number of idle tape drives, we need to maximize the number of tape drives used for the minimum number of jobs. We can achieve this by setting k to the minimum value that satisfies the inequality above. Thus, we have:
kmin(kmin1)(kmin2)(kmin3)24=N
Step 2:
b) Now, let's suggest an alternative policy to improve tape drive utilization and avoid system deadlock. One possible approach is to allow jobs to start even if there are fewer than four tape drives available. In this case, a job would start with the available number of tape drives and acquire additional tape drives as they become available.
To calculate the maximum number of jobs that can be in progress at once using this alternative policy, we need to consider the scenario where only three tape drives are available initially for each job. Let's assume M represents the maximum number of jobs that can be in progress at once under this alternative policy.
Since each job requires a maximum of four tape drives, we need to ensure that the total number of tape drives required by M jobs is not greater than the number of available tape drives.
Therefore, we have the following inequality:
3M20
Solving this inequality for M, we find the maximum number of jobs that can be in progress at once:
3M20
M203
The bounds on the number of idling tape drives can be determined based on the maximum and minimum number of jobs that can be in progress at once under the alternative policy.
When M jobs are in progress simultaneously, each job initially starts with three tape drives. As more tape drives become available, the jobs can acquire the additional drives. Therefore, the maximum number of idle tape drives will occur when all jobs have acquired their fourth tape drive.
To calculate the maximum number of idle tape drives, we subtract the total number of tape drives required by the M jobs from the total number of available tape drives:
Maximum number of idle tape drives=20(3M)
On the other hand, the minimum number of idle tape drives will occur when only one job is in progress, utilizing the maximum number of tape drives. In this case, there will be no idle tape drives.
Therefore, under the alternative policy, the maximum number of jobs that can be in progress at once is 203 (rounding down to the nearest integer), and the bounds on the number of idle tape drives are as follows:
Maximum number of idle tape drives: 20(3×203)
Minimum number of idle tape drives: 0

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?