Prev Next

Archive for February 2011

A Post Without Image

Process State and its Transition







The Central Processing Unit (CPU) executes a large number of programs. While its main concern is the execution of user programs, the CPU is also needed for other system activities. These activities are called processes. In general, a process will need certain resources such as the CPU time, memory, files, I/O devices and etc. to accomplish its task. As a process executes, it changes state. The state of a process is defined by its current activity. In the diagram above, each process may be in one of the following states: hold state, ready state, waiting state, running state, and finished state.

As shown in the diagram, there is no transition happen from the READY STATE to WAITING STATE as well as from WAITING STATE to RUNNING STATE. Why?


READY STATE to WAITING STATE

There is no transition happen from the READY STATE to WAITING STATE. The reason is, the process that stays at the waiting state is the process that has been block at its running state. When a process blocks, logically it cannot continue, typically because the process is waiting for an input or response from any peripheral devices required for its execution. The process on this state is unable to run until some external event happens. In general, the process is waiting for some event to happen such as an I/O completion before it can proceed. Then if there is, there will be a signal issued from the waiting state to ready state to inform that the process is ready to be executed. On the other hand, the process on the ready state is waiting to be assigned to a processor. But for instance, if the process in the ready state cannot proceed due to its failure of device required, it should be sent back to the hold state, not in the waiting state. The process will be sent to waiting state only if the process is waiting for an event from its peripheral devices needed for it to execute. Therefore, there is no transition in the READY STATE to WAITING STATE.


WAITING STATE to RUNNING STATE

The process scheduler chooses the processes or jobs to be executed only at the running state. Therefore, there is no transition happen between WAITING STATE to RUNNING STATE for the reason that there is no possibility to process a job by bypassing the running state. Also, in the waiting state, jobs on this state are the jobs waiting for an event happen from its required external devices or either waiting for its I/O completion. 

A Post Without Image

Best-Fit, First-Fit and Worst-Fit Memory Allocation Method for Fixed Partition

The following jobs are loaded into memory using fixed partition following a certain memory allocation method (best-fit, first-fit and worst-fit).
                                              
List of Jobs
Size
Turnaround
Job 1
100k
3
Job 2
10k
1
Job 3
35k
2
Job 4
15k
1
Job 5
23k
2
Job 6
6k
1
Job 7
25k
1
Job 8
55k
2
Job 9
88k
3
Job 10
100k
3
                  Memory Block            Size             
                      Block 1                    50k
                      Block 2                  200k 
                      Block 3                    70k
                      Block 4                  115k
                      Block 5                    15k









 B E S T - F I T

Best-fit memory allocation makes the best use of memory space but slower in making allocation. In the illustration below, on the first processing cycle, jobs 1 to 5 are submitted and be processed first. After the first  cycle, job 2 and 4 located on block 5 and block 3 respectively and both having one turnaround are replace by job 6 and 7 while  job 1, job 3 and job 5 remain on their designated block. In the third cycle, job 1 remain on block 4, while job 8 and job 9 replace job 7 and job 5 respectively (both having 2 turnaround). On the next cycle, job 9 and job 8 remain on their block while job 10 replace job 1 (having 3 turnaround). On the fifth cycle only job 9 and 10 are the remaining jobs to be process and there are 3 free memory blocks  for the incoming jobs. But since there are only 10 jobs, so it will remain free. On the sixth cycle, job 10 is the only remaining job to be process and finally on the seventh cycle, all jobs are successfully process and executed and all the memory blocks are now free.   
 
 
 
F I R S T - F I T
 
First-fit memory allocation is faster in making allocation but leads to memory waste. The illustration below shows that on the first cycle, job 1 to job 4 are submitted first while job 6 occupied block 5 because the remaining memory space is enough to its required memory size to be process. While  job 5 is in waiting queue because the memory size in block 5 is not enough for the job 5 to be process. Then on the next cycle, job 5 replace job 2 on block 1 and job 7 replace job 4 on block 4 after both job 2 and job 4 finish their process. Job 8 is in waiting queue because the remaining block is not enough to accommodate the memory size of job 8. On the third cycle, job 8 replace job 3 and job 9 occupies block 4 after processing job 7.  While Job 1 and job 5 remain on its designated block. After the third cycle block 1 and block 5 are free to serve the incoming jobs but since there are 10 jobs so it will remain free. And job 10 occupies block 2 after job 1 finish its turns. On the other hand, job 8 and job 9 remain on their block. Then on the fifth cycle, only job 9 and job 10 are to be process while there are 3 memory blocks free. In the sixth cycle, job 10 is the only remaining job to be process and lastly in the seventh cycle, all jobs are successfully process and executed and all the memory blocks are now free. 
 
 
 
W O R S T - F I T
 
Worst-fit memory allocation is opposite to best-fit. It allocates free available block to the new job and it is not the best choice for an actual system. In the illustration, on the first cycle, job 5 is in waiting queue while job 1 to job 4 and job 6 are the jobs to be first process. After then,  job 5 occupies the free block replacing job 2. Block 5 is now free to accommodate the next job which is job 8 but since the size in block 5 is not enough for job 8, so job 8 is in waiting queue. Then on the next cycle, block 3 accommodate job 8 while job 1 and job 5 remain on their memory block. In this cycle, there are 2 memory blocks are free. In the fourth cycle, only job 8 on block 3 remains while job 1 and job 5 are respectively replace by job 9 and job 10. Just the same in the previous cycle, there are still two free memory blocks. At fifth cycle, job 8 finish its job while the job 9 and job 10 are still on block 2 and block 4 respectively and there is additional memory block free. The same scenario happen on the sixth cycle. Lastly, on the seventh cycle, both job 9 and job 10 finish its process and in this cycle, all jobs are successfully process and executed. And all the memory blocks are now free.   
 
 

A Post Without Image

Dynamic and Relocatable Dynamic Partition


The following jobs are loaded into memory using dynamic partition and relocatable dynamic  partition. Its memory size is 220k with allocated OS for 15k. These are the following list of jobs with their specific size and turnaround.


Job 1          100k          3             
Job 2            10k          1             
Job 3             35k         2             
Job 4             15k         1              
Job 5             23k         2              
Job 6               6k         1
Job 7             25k         1
Job 8             55k         2
Job 9             88k         3
Job 10         100k         3


D Y N A M I C     P A R T I T I O N
The main memory is partitioned. Jobs given memory requested when loaded and one contiguous partition per job. It uses "First Come, First Serve" allocation method in allocating job and its memory waste is comparatively small.





R E L O C A T A B L E     D Y N A M I C   P A R T I T I O N
The memory manager relocates programs of which it gathers together all empty blocks. Compact the empty blocks and make one block of memory large enough to accommodate some or all of the jobs waiting to get in.