System using the fixed partitions memory allocation scheme

1. Solution Manual Understanding Operating Systems 7th Edition Ann McHoes

2. Complete downloadable file at:

a. Use the first-fit algorithm to indicate which memory blocks are allocated to each of the three arriving jobs. ANS: Job A is allocated to Block 1, Job B is allocated to Block 2, Job C is waiting

b. Use the best-fit algorithm to indicate which memory blocks are allocated to each of the three arriving jobs. ANS: Job A is allocated to Block 1, Job B is allocated to Block 3, Job C is allocated to Block 2

Indicate which memory blocks are allocated to each of the three arriving jobs, and explain in your own words what advantages the next-fit algorithm could offer. ANS: (Job A is allocated to Block 2, Job B is allocated to Block 3, Job C is allocated to Block 4, Job D is waiting because it doesn’t fit into Block 1)

9. Worst-fit is an allocation algorithm that allocates the largest free block to a new job. It is the opposite of the best-fit algorithm. Compare it to next-fit conditions given in Exercise 8 and explain in your own words what advantages the worst-fit algorithm could offer. ANS: Job A is allocated to Block 2, Job B is allocated to Block 4, Job C is allocated to Block 3, Job D is waiting because it doesn’t fit into Block 1, As an alternative, ask students to try the best-fit with this data and all four jobs will fit into the four available memory blocks.

b. If the memory block has 3K in fragmentation, calculate the size of the memory block.

ANS: 46080 (3*1024 = 3072) + (42*1024 = 43008) = 46080

ANS: 5130240 (10*1024 = 10240) + (5000*1024 = 5120000) = 5130240

c. Is the resulting fragmentation internal or external? Explain your reasoning. ANS: Look for a fundamental understanding of the differences between internal and external fragmentation.

15. In a system using the dynamic partition memory allocation scheme, given the following situation (and using decimal form): After Job C of size 70K is loaded into a partition resulting in 7K of fragmentation, calculate the size (in bytes) of its partition ANS: 71680 (70*1024 = 71680) and identify the type of fragmentation that is caused? (External fragmentation) Explain your answer. (Students should show their calculations and explain how they know that the fragmentation is between partitions.)

Advanced Exercises

60 K

Job 4 requires 15K and a block that large is not yet available. Therefore, compaction is needed.

j = 1

DO-WHILE there are active jobs

IF free-partition-size(k) > active job-size(j)

THEN compaction-case = 2

beginning = 0

DO-WHILE beginning not = active job-size(j)

difference = difference - free-partition-size(k)

IF difference < 0

END-IF

END-IF

IF compaction‑case = 0

THEN "Compaction is not possible"

18. Given the memory configuration in the figure below, answer the following questions. At this point, Job 4 arrives requesting a block of 100K.

a. Can Job 4 be accommodated? Why or why not?

f. An instruction that is part of Job 3 was originally loaded into memory location 80K. What is its new location after compaction?

g. If an instruction was originally loaded into memory location 110K, what is its new location after compaction?

-20480 (-20K) 2

-30720 (-30K) 3

g. Its location is: 110K - 30K = 80K (or 81920)

h. That value does not change. The true address is computed when execution occurs.

ii. Input Procedure: where all data is submitted.

iii. Time Procedure: where the system clock is updated to indicate how long it took to process all jobs and where the time to run a job (job clock) is updated.

A policy has to be developed to handle the conflict of which job will be served first: the one in the waiting queue or the incoming one. A related policy must be defined to determine whether no more incoming jobs will be accepted until the ones in the waiting queue are served or the system will flip-flop between incoming and waiting jobs.

The data for the jobs is best stored into a table with columns indicating: job size, job time to run, waiting time and status (new, running, waiting, too big or done). The data for the memory blocks is best stored into a table with columns indicating: block size, status (busy or free), number of jobs currently using block, counter for number of times block has been used.

03 08 329 done 00 08

04 02 203 done 00 02

09 07 393 running 00

10 06 689 running 01

15 10 022 new

16 07 754 new

21 07 754 new

22 02 271 new