Monday, April 4, 2011 | By: Louella Marree Cariño

Operating System Case Study no. 6

Job and Process Status

The diagram shows how the operating system controls the execution of processes. It starts on the Hold State wherein the Job is accepted and placed on the queue. When the Job moves to Ready State, it means that the Job is waiting for the CPU. It is also the process the Job is queuing and preparing to execute when given the opportunity. And when the Job is selected, it is now in the state of Running State. In that state, it’s the process where Job is currently being executed. But then, it is not certain that the Job in the Running State would directly go to Finish. Since there are possibilities of interruptions and the unavailability of resources, the Job would be placed in the waiting queue. The CPU would still continue accepting Jobs from the Ready State and those Jobs in the waiting queue would remain in that state until the CPU is ready to execute those Jobs again. After giving signals that the Jobs in the Waiting queue are ready to be processed again, those Jobs would be moved to the Ready State and be executed on the Running State. If nothing else went wrong, the Jobs would be placed in finished indicating that the Jobs were processed successfully.

With these state processes it would be totally impossible of having transition between READY to WAITING and from WAITING to RUNNING.  There are no transitions between Ready and Waiting since the Job in the Ready State would always be placed in the Running State, and after detecting some interruptions or page faults, that would only be the time that the Job would be placed in Waiting State. Another thing is that, the CPU cannot detect interrupts in the Ready State since it is still preparing to be executed.

Between the states from Waiting to Running, it is also not possible to have transition since the Jobs to be executed should be preparing at the Ready State. Besides, it is still necessary for the Jobs in the Waiting queue to send signals for the Jobs to continue processing. And if the Jobs would be placed in the Ready queue, the Jobs could be executed once again. 

Operating System Case Study no. 5



Best fit memory allocation is the smallest partition fitting the requirements which makes the best use of memory space.  The illustration above shows the method of best fit memory allocation. In best fit, each job should find the smallest memory block into which the job will fit.

The first column is the memory divided into five blocks using fixed partition.
On the second column:
            Job 1 has 100k memory size, so it has to be allocated in a block that is not too small, and not too large than the memory size. Block 1 has 50k, so it is impossible to fit. Block 2 has 200k, though the memory size of Job 1 could fit, still it is too large. Block 3 has 70k, smaller than the memory size of Job 1. Block 4 has 115k, it is perfect for the memory size Job 1, but then, Job 1 must take a look at the remaining block just to be sure that the Block 4 is the best fit. Lastly, Block 5 has 15k, also smaller than the memory size of Job 1. With these, it is assumed that Block 4 with 115k memory size is the best fit for Job 1 which has 100k memory size.
            Job 2 has 5k memory size. With the sizes of the memory in each block, it can be seen that Job 2 could fit in any block except for Block 4 since Job 1 is allocated in this block. But then, the sizes of the memory of Block 1, 2, and 3 are too large for Job 2. And so, it is assumed that Block 5 with 15k memory size is the best fit for Job 2 which has 5k memory size.
            Job 3 has 35k memory size. The remaining blocks that have to be allocated are blocks 1, 2 and 3. These blocks have big enough memory size but then Block 2 and Block 3 are too large for Job 3. With these, Job 3 which has 35k memory size is allocated at Block 1 with 50k memory size.
            Job 4 has 15k memory size. Now, the remaining blocks are Block 2, and Block 3. And in these two blocks, Block 3 has smaller memory size, which means Block 3 with 70k memory size is the best fit for Job 4 which has 15k memory size.
            Job 5 has 23 k memory size, and the only block which has to be allocated is Block 2. So Job 5 with 23k memory size is allocated at Block 2 which has 200k memory size.




On the third column:
            Job 3 with 35k memory size has 2 turnarounds, which means it would still remain in Block 1. Job 5 with 23k memory size still has to remain in Block 2 since it has 2 turnarounds.
Job 4 has ended and it was replace by Job 7 with 25k memory size. Job 2 also ended and was replaced by Job 6 with 6k memory size.   

On the fourth column:
            Job 3 already ended, and so Block 1 is free and ready to be allocated by other jobs. Job 5 also ended and it was replaced by Job 9 with 88k memory size. Job 7 has also ended and was replaced by Job 8 with the memory of 100k. Job 6 also ends and Block 5 is also free and ready to be allocated. Job 8 was allocated at Block 3 since Block 2 is too large and the other blocks are too small. Same goes for Job 9, it was allocated at Block 2 since it would be the best fit for Job 9.

On the fifth column:
            Job 1 was finished on its third turnaround, and it was replaced by Job 10 with 100k memory size. Block 1 and Block 5 remained free and ready to be allocated. While Job 8, and Job 9 remained in their blocks since it is their second turnaround.

On the sixth column:
            Job 8 ended, so Block 3 is free. Job 9 still remained since it has to finish its last turnaround. Job 10 also remained. And the remaining blocks are free.

On the seventh column:
            Job 9 ended, and Block 2 is free. But still, Job 10 has to remain to finish its last turnaround.

On the eighth column:
            Job 10 finished its turnaround and all the blocks are free and ready to be allocated again.

First fit allocation method is the first partition fitting the requirements and faster in making allocations. The illustration above displays the method of first fit memory allocation. In first fit, the jobs should allocate the first free block in which their memory will fit even if it means leading to memory waste.
The first column is the memory divided into five blocks using fixed partition.
On the second column:
            Job 1 has 100k memory size. Since Block 1 has smaller memory size and Block 2 has enough memory, then Job 1 was allocated at Block 2. Next is Job 2 with 10k memory size. And because Block 1 has enough memory for Job 2, Job 2 was allocated at Block 1. Job 3 has 35k memory size. Block 1 and Block 2 has already been allocated with Job 1 and Job 2, therefore, Job 3 was allocated in Block 3 since it can hold the memory size of Job 3. Job 4 with 15k memory size has been allocated in Block 4 which has 115k memory size. Since the remaining block for the first turnaround has a memory of 15k, Job 5 could not fit on the said block. And so, Job 5 is on the waiting queue, and Job 6 was allocated in Block 5 since it only has 9k memory size.

On the third column:
            Job 5 replaced Job 2 in Block 1. Job 1 and Job 3 remained while Job 7 replaced Job 4 on Block 4. Job 6 finished its turnaround, and Block 5 is free.
           
On the fourth column:
            Job 5 still remained in Block 1 as well as Job 1 in Block 2. Job 3 already ended, and was immediately replaced with Job 8 with 55k memory size. Job 7 also ends and was replaced with Job 9 in Block 4. Still, Block 5 remained free.

On the fifth column:
            Job 5 finished the job and so, Block 1 is free. Job 1 was finished on its third turnaround, and it was replaced by Job 10 with 100k memory size. Block 5 remained free while Job 8 and Job 9 remained in their blocks since it is their second turnaround.

On the sixth column:
            Job 8 ended, so Block 3 is free. Job 9 still remained since it has to finish its last turnaround. Job 10 also remained. And the remaining blocks are free.

On the seventh column:
            Job 9 ended, and Block 4 is free. But still, Job 10 has to remain to finish its last turnaround.

On the eighth column:
            Job 10 finished its turnaround and all the blocks are free and ready to be allocated again.

 Worst fit allocation method allocates largest free available block to new job. The illustration above manifests the method of worst fit memory allocation. In worst fit, the jobs should allocate the largest available block, which is a total opposite of best fit.
The first column is the memory divided into five blocks using fixed partition.
On the second column:
            Job 1 has 100k memory size. Since Block 1 has smaller memory size and Block 2 has enough memory, then Job 1 was allocated at Block 2. Next is Job 2 with 10k memory size. Since the Block with biggest memory had been allocated, Job 2 proceeded to the next Block that is smaller than Block 2 and larger than other blocks, which is Block 4. Job 3 came next with 35k memory size. Aside from Block 2 and Block 4, Block 3 also has a large memory; therefore, Job 3 allocated Block 3. The free blocks are Block 1 and Block 5, since Job 4 would not fit in Block 5, Job 4 allocated Block 1. Since the remaining block for the first turnaround has a memory of 15k, Job 5 could not fit on the said block. And so, Job 5 is on the waiting queue, and Job 6 was allocated in Block 5 since it only has 9k memory size.

On the third column:
            Job 5 replaced Job 2 in Block 4. Job 1 and Job 3 remained while Job 7 replaced Job 4 on Block 1. Job 6 finished its turnaround, and Block 5 is free.
           
On the fourth column:
            Job 5 still remained in Block 4 as well as Job 1 in Block 2. Job 3 already ended, and was immediately replaced with Job 8 with 55k memory size. Job 7 also ends, so Block 1 is free. Still, Block 5 remained free.

On the fifth column:
            Job 1 was finished on its third turnaround, and it was replaced by Job 9 with 88k memory size. Job 8 remained in its block and Job 5 in Block 4 was replaced by Job10. Block 1 and Block 5 remained free.

On the sixth column:
            Job 8 ended, so Block 3 is free. Job 9 still remained. Job 10 also remained. And the remaining blocks are free.

On the seventh column:
            . Job 9 and Job 10 still remained since it has to finish its last turnaround. While the remaining blocks are free.
On the eighth column:
            Job 9 and Job 10 finished its turnaround and all the blocks are free and ready to be allocated again.


Operating System Case Study no. 4