Case Study #6

Given this diagram:

 

Why is it that there is no transition from READY to WAITING?

            Given the diagram above the is that for the definition that those jobs queued in the READY state are all ready in every aspect as of to be used by the CPU. While in the WAITING state are for those jobs that are still waiting external or peripheral devices that is needed by job before being acknowledged to be used by the CPU, so in the narrowest sense, after the jobs received the needed responses from the certain external and peripheral devices they can now be processed by the CPU. So by looking in the diagram it is possible that from the WAITING state, provided that jobs were able to receive the needed responses they can now be loaded to the READY state, on the other hand if while in the READY state a job encountered a failure from a required device which reults that the said job be unable to proceed, then being subjected in this kind of scenario the job is sent NOT in the WAITING state but back in the HOLD state. So only WAITING state to READY state has a transition but the transition of READY state to WAITING state is impossible.      

Why is it that there is no transition from WAITING to RUNNING?

            From the HOLD state, jobs are then loaded to the READY state and the jobs have to wait for the appropriate responses by the peripheral devices. If by then the responses are given then now the jobs can be loaded to the RUNNING state and if an I/O request page fault occurs then the process scheduler then needs to load it in the WAITING state instead of finishing the job. So if there is a transition from WAITING to RUNNING state clearly then it won’t be possible, for the jobs that encountered the said error was loaded to the WAITING state. It should be that after the error encountered jobs are loaded in WAITING state then waits for the signal to continue processing then only after that will the jobs be loaded back to the READY state. So why does the jobs that encountered error be loaded back to the READY state? For it is in the READY state that the jobs wait again for the responses of the I/O devices and then only after that the the process scheduler can select the jobs truly ready to be processed by the CPU. By bypassing the READY queue would make process management impossible.

Case Study #5

Load the following jobs into memory using fixed partition using the best-fit, first fit and worst-fit allocation method.

a. Job1 (100k)             f. Job6 (6k)

turnaround: 3              turnaround: 1

b. Job2 (10k)               g. Job7 (25k)

turnaround: 1              turnaround: 1

c. Job3 (35k)               h. Job8 (55k)

turnaround: 2              turnaround: 2

d. Job4 (15k)               i. Job9 (88k)

turnaround: 1              turnaround: 3

e. Job5 (23k)               j. Job10 (100k)

turnaround: 2              turnaround: 3

*turnaround – how long it will stay in the memory.

A. Best-Fit Allocation Method   

First of all what is best-fit? Best-fit is an allocation method that searches the entire table for the smallest memory block that will fit a certain job.

 

First Loading of Jobs

So in the situation above Job 1 with a memory size of 100k starts to search the table of memory blocks for the smallest block it can fit, and it found the appropriate block, which is Block 4 with a memory size of 115k, so Job 1 was loaded in Block 4 decreasing its unallocated space to 15k.  Next we have Job 2 which has 10k memory size, searches the whole table of memory block and finds its appropriate memory block which is Block 5 having 15k memory size, so Job 2 was loaded in Block 5 decreasing its unallocated space to 5k. Job 3 with 35k size of memory follows next searching the entire memory block table and finds that the most suitable memory block is Block 1 having 50k size of memory, thus Job 3 is loaded in Block 1 decreasing its unallocated space to 15k. Next is Job 4 and does the same thing checks the entire memory block and finds that the most suitable memory block is Block 3 having 70k size of memory, thus Job 4 is loaded in Block 3 decreasing its unallocated space to 55k. Next to find a memory block is Job 5 which has 23k size of memory, again searches the table for a memory black and finds the most suitable which is Block 2 having 200k size of memory, thus Job 5 is loaded to Block 2 decreasing its unallocated space to 177k.The remaining jobs can’t be anymore loaded and so is placed in the waiting/queue list. The current partition left the system with a total of 267 size of memory internally fragmented.

First unloading of Jobs (deallocation)

Because only Jobs 1, 3 & 5 have not yet finished there stay on the memory block they are in, only Jobs 2 & 4 are to deallocate their memory blocks.

Second loading of Jobs.

Now Job 6, with 6k size of memory can be loaded to the newly freed memory blocks, the suitable memory block is Block 5 which has 15k size of memory. So after loading Job 6 to Block 4 there is only 9k of unallocated space left. Job 7 also grabs the opportunity to load itself, having 25k size of memory it has found that Block 3 having 70k size of memory is suitable, after loading Job 7 to Block 3 the only left unallocated space is 45k.

Second unloading of Jobs (deallocation)

            Only Job 1 is still not done staying at its memory block for this is just his 2^nd turnaround and it has to 3 turnarounds. Jobs 3 & 5 are now to deallocate their memory blocks for they are done with their turnaround, same goes for Jobs 6 & 7 which are also to release the memory block they each hold.

Third loading of Jobs

            There are now four(4) memory blocks that are newly released, so Job 8 with a memory size of 55k, grabs the opportunity to load itself to Block 3 which has 70k and so the unallocated space was reduced to 15k. Job 9 which has 88k memory size loads itself to Block 4 which has 115k reducing the unallocated space to 27k. Job 10 which has 100k memory size, also find a suitable memory block, Block 2 which has 200k unallocated space. After loading Job 10 to Block 2 the unallocated space was reduced to 100k.

Third unloading of Jobs (deallocation)

            For Job 1 because it has finished its turnaround is the only to deallocate its memory block. Jobs 8, 9 & 10 are still to finish their turnaround.

Continuation: (finishing the remaining jobs that has turnaround)

            Since there are no more new jobs to load, the system is to continue processing the jobs remaining, which means the system has to continue until Jobs 8, 9 & 10 are able to finish their turnaround. After that the memory is blocks are back to its original free state.

Job 8 is now on its last turnaround while Jobs 9 & 10 is on their second turn around.

Fourth unloading of Jobs

            Job 8 is now to deallocate its memory block, Jobs 9 & 10 is now on their third and last turn around.

Fifth Unloading of Jobs

            Since now Jobs 9 & 10 has finished their turnarounds. They are to deallocate the memory blocks they are in. The whole memory block is free again.

____________________________________________________

B. First Fit:

This allocation is about first come first server it does not follow any particular guide as to which a job should be loaded either from the smallest or largest memory block.

First loading of jobs

            Job 1 of 100k memory is loaded to Block 2 of 200k memory, a 100k unallocated or free space is produced. Job 2 of 10k memory is loaded to Block 1 of 50k memory, a 40k unallocated or free space is produced. Job 3 of 35k memory is loaded to Block 3 of 70k memory, a 35k unallocated or free spaced is produced. Job 4 of 15k memory is loaded to Block 4 of 115k memory, a 100k unallocated or free space is produced. Job 5 of 23k memory CANNOT be loaded to Block 5 for there is not enough free memory to load the job. Job 6 of 6k memory CAN be loaded to Block 5 of 15k memory, a 9k unallocated or free space is produced.

First unloading of jobs 

           

            Jobs 1 & 3 are still not finished with their turnaround therefore only Jobs 2, 4 & 6 are to be deallocated.    

Second loading of jobs

            Job 5 of 23k memory, which was previously moved to queue can now find a block from the 2 memory blocks that was freed, Block 1 of 50k can support Job 5 and by loading the job this produced a 27 unallocated or free space. Job 7 of 25k memory can be loaded to Block 4 of 115k memory, creating a 90k unallocated or free space.

Second unloading of jobs

            Only Job 1 is left to finish its turnaround. Jobs 3, 4, 5 & 7 is to deallocate its memory blocks.

Third loading of jobs

             Job 8 of 55k memory will be loaded to Block 3 of 70k, a new 15k unallocated or free space is produced. Job 9 of 88k shall be loaded to Block 4 of 115k, a new 27k unallocated or free space is produced. Job 10 will have to wait since there is no other memory block that can support the loading of this Job.

Third unloading of jobs

            Job 1 is now to deallocate its memory blocks after finishing its 3 turnaround. Jobs 8 and 9 is still undergoing there turnaround therefor they WILL NOT deallocate their memory blocks.

Fourth loading of jobs 

            Job 10 which has 100k memory size will be loaded to Block 2 of 200k, a new 100k unallocated or free space is produced. Jobs 8 & 9 is having their first turnaround.

Fourth unloading

            Job 8 is to deallocate its memory block for it is finished doing its turnaround. Job 9 is having its last turnaround. Job 10 is having its second turnaround.

(Since there are no more jobs left to be loaded the system must continue to finish the previous job that has been loaded.)

Fifth unloading

            Job 9 is to deallocate its memory block for it has finished doing it turnaround. Job 10 is on its last turnaround.

Sixth unloading

            Job 10 is to deallocate its memory block for it has finished doing its turnaround.

____________________________________________________

C.Worst-fit

Allocates the largest free memory block to a job.

Allocating:

Job 1 of 100k memory is to be loaded to Block 2 of 200k memory, resulting to a 100k remaining free space. Job 2 of 10k memory is to be loaded to Block 4 of 115k memory, resulting to a 105k remaining free space. Job 3 of 35k memory is to be loaded to Block 3 of 70k memory, resulting to a 35k remaining free space. Job 4 of 15k memory is to be loaded to Block 1 of 50k memory resulting to 36k remaining free space. Job 5 is moved to queue because the remaining memory block is not enough to load the said Job. Job 6 of 6k memory is to be loaded to Block 5 of 15k memory, resulting to a 9k remaining free space.

Deallocating:

Jobs 1 & 3 are not to be deallocated since they are not still done with their turnaround. Jobs 2, 4 and 6 are now able to deallocate their memory blocks.

Allocating:

Job 5 of 23k memory is to be loaded to Block 4 of 115k memory, resulting to a 92k remaining free space. Job 7 of 25k memory is to be loaded to Block 1 of 50k memory, resulting to a 25k remaining free space. The remaining jobs are too large for the remaining memory blocks to support so they are placed in a queue list.

Deallocating:

Job 1 & 5 is still to finish their turnaround while Job 3 finished its turnaround therefor is about to be deallocated. Job 7 also finished its job so deallocation is also its destiny.

Allocating:

Job 8 of 55k memory is to be loaded to Block 3 of 77k memory, resulting to a 22k remaining free space. The remaining jobs cannot be loaded for there are no available memory blocks to support them.

Deallocating:

Jobs 1 & 5 are to deallocate their memory blocks for they are finished with their turnaround. Job 8 has still one turnaround left.

Allocating:

Job 9 of 88k memory is to be loaded to Block 2 of 200k memory, resulting to 112k remaining space. Job 10 of 100k memory is also to be loaded to Block 4 of 115k memory, resulting to 15k remaining free space.

Deallocating:

Job 8 is to deallocate its memory blocks for it has finished its turnaround. Jobs 9 & 10 are still doing turnarounds. Jobs 9 & 10 are still on their second turnaround.

(There are no more jobs to be loaded therefor the system will continue to finish the previous loaded Jobs 9 and 10 and after 3 turnarounds will be deallocated.

Deallocating:

            Jobs 9 & 10 are still not able to deallocate for there are still not finished with their turnarounds. They are currently on their third and last turnaround.

Deallocating:

            Finally Jobs 9 & 10 are now able to deallocate their memory blocks. The memory blocks are back to its original free state.

Case Study #4

Load the following jobs into memory using dynamic partition and relocatable dynamic partition:

(The memory size is 220k with allocated OS for 15k). 

  

Dynamic Partition: 

a. Job1 (100k)             f. Job6 (6k)

turnaround: 3              turnaround: 1

b. Job2 (10k)               g. Job7 (25k)

turnaround: 1              turnaround: 1

c. Job3 (35k)               h. Job8 (55k)

turnaround: 2              turnaround: 2

d. Job4 (15k)               i. Job9 (88k)

turnaround: 1              turnaround: 3

e. Job5 (23k)               j. Job10 (100k)

turnaround: 2              turnaround: 3

^ - indicates on what turnaround the job is already in.

Relocatable Dynamic Partition:

 

a. Job1 (100k)             f. Job6 (6k)

turnaround: 3              turnaround: 1

b. Job2 (10k)               g. Job7 (25k)

turnaround: 1              turnaround: 1

c. Job3 (35k)               h. Job8 (55k)

turnaround: 2              turnaround: 2

d. Job4 (15k)               i. Job9 (88k)

turnaround: 1              turnaround: 3

e. Job5 (23k)               j. Job10 (100k)

turnaround: 2              turnaround: 3

^ - indicates on what turnaround the job is already in.

The O.S. takes 15k size of memory out of the 220k which makes the new default over all memory size to 205k.

Jobs 1, 2, 3, 4, 5 & 6 were loaded to the memory and took an over all memory size of 204k leaving 16k size of memory free.

Jobs 1, 3 & 5 just started their first turnaround.

The 16k free memory cannot store any jobs remaining thus it will remain as a free memory size.

 

Jobs 2, 4 & 6 are finished and freed a total of 47k size of memory that has been Internally Fragmented.

Jobs 1, 3 & 5 are about to finish their first turnaround.

The total memory taken is 173k.

Jobs 1, 3 & 5 are relocated for the remaining freed but internally fragmented memory to be combined to be able to support the remaining jobs.

Still the total memory taken is 173k.

Jobs 1, 3 & 5 have started their second turnaround.

A new job, which is Job 7 with a 25k size of memory, will be loaded to the freed 47k.

Thus the remaining freed memory becomes 22k.

The total memory taken is now 173 + 25 = 198k.

Job 1 has finished its 2^nd turnaround and is getting ready for its 3^rd turnaround, Jobs 3 & 5 also finished its 2^nd turnaround and is going to deallocate the memories they are occupying, same goes for Job 7 which is also to deallocate its memory.

The deallocated memory of Jobs 3, 5 & 7 added to the already freed memory which is 22k sums up to a new total unallocated memory which is 105k

The total memory taken is now 115k

Job 1 has started its 3^rd and last turnaround before it deallocates its occupied memory.

With an unallocated space memory of 105k, now we are able to load Job 8 with a memory size of 55k, so now the remaining unallocated space is 50k.

The total used memory is 170k.

Job 8 had its first turnaround and is relocated to combine the past internally fragmented memory size of 100k to be combined with the previous unallocated memory of 50k.

The total used space is 70k.

The 2^nd and the last turnaround of Job 8 with a memory of 55k, before it deallocates.

Job 9 which has a memory size of 88k, was also loaded to the unallocated memory size of 150k decreasing the free space to 62k.

The total used space is 158k.

So Job 8 deallocated its memory size of 55k and was later combined to the previous unallocated memory size of 62k to increase the unallocated size to 117k.

The total used space goes down to 88k.

Job 9 is currently at its 2^nd turnaround while a new job was loaded, Job 10 which has 100k as its memory size added with the 15k memory of the O.S. and 88k memory size of Job 9, it increased the memory consumption to 203k, leaving 17k as unallocated space.

The total used space is 203k.

There was no deallocation done since neither of Job 9 or 10 was done of their turnaround.

Still both jobs consumed 203k of memory size and have an unallocated space of 17k.

Job 9 did its 3^rd and last turnaround and has deallocated the memory size it has used, which is 88k, thus adding to the previous and unallocated space 17k increasing it to 105k.

Job 10 is currently at its 2^nd turnaround.

Total memory used is 115k.

Job 10 is currently at its 3^rd turnaround.

No changes in the memory request for there are no deallocation

Job 10 is done with its final turnaround and has deallocated the memory size it has used.

Job 10’s memory size of 100k is now added to the previous unallocated space 105 and has increased it up to 205k.

Since there are no more jobs to be loaded except for the Operating System memory allotted, then the total memory used is 15k.