Everything is nothing but nothing is IMPORTANT: 2011

READY to WAITING and WAITING to RUNNING.

Process is a program in execution. It contains the program code and its current activity. A multitasking operating system may just switch between processes to give the appearance of many processes executing concurrently or simultaneously, though in fact only one process can be executing at any one time on a single-core CPU (unless using multi-threading or other similar technology). A process can be in one of many possible states:

Where the process is being created but has not been admitted to the pool of executable processes by the operating system.

Ready

The process is waiting to be assigned to a processor.

Running

The instructions are being executed.

Waiting

The process is waiting for some event to occur.

Terminated (Finished)

The process has finished execution.

Process State Transition Diagram

In this process state diagram, I will explain why there is no transition; from the READY to WAITING and from the WAITING to RUNNING.

From the READY state to the WAITING state, there is no transition because a job in the WAITING state is waiting for peripheral device response which must be received before the CPU can effectively be used again. A process in the READY queue is ready in all aspects to make effective use of the CPU. If a job in the READY state cannot proceed because a required device fails, it should be sent back to the HOLD state, not the WAITING state. The WAITING state is a service from the RUNNING state that the OS is not ready to perform and an access to a resource is not yet available. It initiates the I/O and must wait for the result where the waiting is for a process to provide the input. There is only a transition from READY to RUNNING which is the OS chooses one of the processes in the READY state and assigns CPU to it.

From the WAITING state to the RUNNING state, the Process Scheduler selects processes from the READY state for the CPU. By passing the READY queue would make process management impossible. The RUNNING state have only three transition: from RUNNING state to FINISHED; from RUNNING state to READY state; and from RUNNING state to WAITING state. From RUNNING state to FINISHED, the process is terminated by the OS if it has completed or aborted. From RUNNING state to READY state, the most common for this transition are: the running process has expired his time slot; the running process gets interrupted because a higher priority process is in the READY state. From RUNNING state to WAITING state, a process is put to this state if it requests for some thing for which it must wait. There is only a transition of WAITING to READY where a process from a WAITING state is moved to a READY state when the event for which it has been waiting occurs.

Therefore, if there is a transition from the READY to WAITING and from the WAITING to RUNNING the process in the state diagram would no longer work and the process would be complicated.

Best-fit, First-fit, and Worst-fit

The following jobs will be loaded into memory using fixed partition following a certain memory allocation method: a. best-fit, b. first-fit, c. worst-fit.

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

Above is the given memory blocks and sizes.

Legend: IF = Internal Fragmentation

a.) Best-fit

Makes the best use of memory space; results in least wasted space; internal fragmentation reduced, but not eliminated; its goal is to find the smallest memory block into which the job will fit.

We say that best-fit is which the jobs fit to the smallest internal fragmentation of the block. Job 1 was best-fitted in memory block 4 that has a size of 115k where it is the smallest fragmentation of 15k among the other blocks. Job 2 best-fitted in memory block 5 with only 5k internal fragmentation. Since block 4 and block 5 is busy, Job 3 only find its best-fit with block 1, block 2 and block 3. Job 3 fitted in block 1 which it has 15k of internal fragmentation. Same as the other jobs Job 4 was fitted on block 3 which it had 55k internal fragmentation and Job 5 in block 2 which it had 177k internal fragmentation. On the second round, Job 2 and Job 4 ends where Job 6 searched which will it be fitted then replaced Job 2 which it had 9k internal fragmentation and Job 7 replacing Job 4 with 45k internal fragmentation. In the third round, four jobs end Job 3, Job 5, Job 6 and Job 7, and Job 8 and Job 9 arrives. When Job 8 searching where it is fitted, block 1 and block 5 cannot accommodate Job 8 because of its lack of memory for Job 8 and also it cannot accommodate block 4 because it is busy since Job 1 has three turnaround. Job 8 accommodated block 3 not blocks 2 because block 3 is lesser internal fragmentation than block 2. Job 9 has no choice to be fitted on block 2 because other blocks is busy and cannot accommodate Job 9. In the fourth round, the round of Job 1 end while Job 8 which have two turnaround and Job 9 which have three turnaround remain and Job 10 arrives. Job 10 only fitted on block 4 which it replacing the Job 1 which it had only 15k internal fragmentation.

b.) First-fit

Leads to fast allocation of memory space; first partition fitting the requirements; faster in making allocation.

First-fit is first come first serve that it will arrive in block where it first be fitted no matter its internal fragmentation. Job 1 was first-fit in block 2 with a size of memory of 200k. Then, Job 2 with 10k was first-fit to block 1 with 50k. Since block 1 and block 2 is busy Job 3 proceed to block 3 which it’s first-fitted as well as Job 4 to block 4. Job 5 has no available memory block in the first round so Job 5 was in the waiting queue then Job 6 can accommodate block 5, Job 6 entered. In the second round, Job 2, Job 4 and Job 6 ends while Job 1 which has three turnaround and Job 3 which has two turnaround remain and Job 5 and Job 7 arrives. Job 5 with 23k first-fit to block 1 where it replaces Job 2. Job 7 was also first-fitted to block 4 with size of 115k. In the third round, Job 3 and Job 7 ends and Job 8 which have 55k and Job 9 which have 88k arrives. Since block 1 and block 2 is busy, Job 8 proceeds to block 3 which it fitted. As well as Job 8, Job 9 proceeds to block 4 where it fitted. In the fourth round, Job 1 and Job 5 end and Job 10 arrives. Job 10 was first-fitted to block 2 replacing Job 1’s places in the last round.

c.) Worst-fit

Allocates largest free available block to new job; opposite of best-fit; good way to explore theory of memory allocation but not best choice for an actual system.

We say that worst-fit is opposite to best-fit where jobs fitted on biggest internal fragmentation among the blocks. In the first round, when Job 1 was searching the whole blocks, it got the biggest internal fragmentation in block 2 of 100k. As well as Job 1, Job 2 searches the biggest internal fragmentation in block 4 of 105k. Since block 2 and block 4 is busy Job 3 only searched in block 1, block 3, and block 5 where Job 3 entered in block which have 35k internal fragmentation. Job 4 gets the biggest internal fragmentation in block 1 of 35k. Since Job 5 cannot accommodate block 5, Job 5 is in the waiting queue so Job 6 entered block 5 since block 5 accommodate Job 6 with 9k internal fragmentation. In the second round, Job 2, Job 4 and Job 6 ends and Job 1 with three turnaround and Job 3 with two turnaround remain and Job 5 in the waiting queue can now entered block 4 because block 4 can accommodate Job 5. Job 7 arrives and replaces Job 4 which has 25k internal fragmentation. In the third round, Job 3 and Job 7 ends and Job 8 arrives. Job 8 (since block 2 and block 4 is busy) searched the blocks 1, 3 and 5 where the biggest internal fragmentation is on block 3 with 15k. In the fourth round, Job 1 and Job 5 finished their turnarounds, Job 9 and Job 10 arrives. Job 9 searched the biggest internal fragmentation in block 2 with a memory size of 200k, where Job 9 has 112k internal fragmentation in block 2. Job 8 still remains because it had two turnaround. Job 10 entered in block 4 with a memory size of 115k with 15k internal fragmentation of block 10.

Dynamic Partition and Relocatable Dynamic Partition

The following jobs will load into memory using dynamic partition and relocatable dynamic partition: (The memory size is 220k with allocated OS for 15k).