A process is a program in execution. The execution of a process must progress in a sequential fashion. That is at any time, at most one instruction is executed on behalf of the process.
A program by itself is not a process; a program is a passive entity, whereas a process is an active entity.
As a process executes, it changes state. The state of the process is defined in part by the followings states:
New
- The process is being created.
Ready
- The process is waiting to be assigned to a processor.
Running
- Instructions are being executed.
Waiting
- The process is waiting for an event to occur.
Terminated
- The process has finished execution.
These names are random, and vary between operating systems. However, the state that they represent are found on all systems.
From Ready to Waiting
There is no transition from READY to WAITING because, as defined, when a process is at its READY state, the process is only waiting to be assigned to a processor. And from the word itself, the process is ready for execution. When the process is already in that state, all the events it needs to execute were already executed before it can be placed in the READY STATE. If we are going to put a transition from READY to WAITING, it would only mean that in the first place, the process should not be in the READY state. Because the WAITING state is still waiting for an event to occur, it is still not ready for execution.
From Waiting to Running
When a process is interrupted during in the RUNNING process, it is placed in the WAITING state. Therefore, all process in the WAITING list has interrupts and lacks I/O request. A process cannot be placed in the RUNNING state when it lacks I/O request. And when the I/O requests are complete, the process is being placed in the READY state. Thus, it is impossible to have a transition from WAITING to RUNNING.
Tuesday, March 22, 2011
Case 5: Memory Allocation in Fixed Partition
Legend: * - Turnaround; ( )- Size; E- Excess memory
First- fit
A. The first batch of jobs is loaded to the memory blocks. Job 1 searches for a block that is big enough. Searching can stop as soon as it can find a memory block that fits. Block 2 is the first memory block that fits Job1. Therefore, Job 1 is loaded to Block 2. Block 1 is the first one that fits Job 2. Block 3 first fits Job 3. Block 4 fits Job 4. Job 5 can not be loaded because Blocks 1 to 4 are already occupied and Block 5 has lesser memory than Job 5. Job 5 is placed in the waiting list.
B. Jobs 2 and 4 terminate and leave the memory block they occupy. Job 5 is loaded first. Block 1 is the first memory block that fits Job 5. Job 6 first fits in Block 4. Job 7 is placed in the waiting list for the same reason Job 5 was also placed in the waiting list.
C. Jobs 3 and 6 terminate. Job 7 is loaded to Block 3 where it first fits. Job 8 first fits on Block 4. Job 9 is placed in the waiting list.
D. Jobs 1, 5, and 7 terminate. Job 9 is loaded to Block 2 where it first fits. Job 10 is placed in the waiting list.
E. Job 8 terminates. Job 10 is loaded to Block 4 where it fits.
F. Jobs 9 and 10 continue processing.
G. Job 9 terminates. Job 10 is still processing.
H. Job 10 terminates.
Best- fit
A. Job 1 searches the entire list. It is loaded to the block which produces the smallest excess memory or leftover. In this case, Job 1 is loaded to Block 4, Job 2 to Block 5, Job 3 to Block 1, Job 4 to Block 3, and Job 5 to Block 2.
B. Jobs 4 and 2 terminate. Job 6 is loaded to Block 5, Job 7 to Block 3.
C. Jobs 3, 5, 7, and 6 terminate. Job 8 is loaded to Block 3, Job 9 to Block 2. Job 10 is placed in the waiting list because its memory exceeds the remaining free memory blocks.
D. Job 1 terminates. Job 10 is loaded to Block 4.
E. Job 8 terminates. Jobs 9 and 10 are still processing.
F. Job 9 terminates. Job 10 is still processing.
G. Job 10 terminates.
Worst- fit
A. In this case, the job searches the entire list and is loaded to the block which produces the largest leftover. Block 2 is the block where Job 1 produces the largest leftover. Job 2 to Block 4. Job 3 to Block 3. Job 4 to Block 1. Job 5 is placed in the waiting list.
B. Jobs 4 and 2 terminate. Job 5 searches the list of free memory block. Block 4 produces the largest leftover for Job 5. Job 6 is loaded to Block 1. Job 7 is placed in the waiting list.
C. Jobs 3 and 6 terminate. Job 7 is loaded to Block 3. Job 8 is placed in the waiting list.
D. Jobs 1, 5, and 7 terminate. Job 8 is loaded to Block 2, Job 9 to Block 4. Job 10 is placed in the waiting list.
E. Jobs 8 and 9 are still processing. Job 10 is still in the waiting list.
F. Job 9 terminates. Job 10 is still processing.
G. Job 10 is processing.
H. Job 10 terminates.
First- fit
A. The first batch of jobs is loaded to the memory blocks. Job 1 searches for a block that is big enough. Searching can stop as soon as it can find a memory block that fits. Block 2 is the first memory block that fits Job1. Therefore, Job 1 is loaded to Block 2. Block 1 is the first one that fits Job 2. Block 3 first fits Job 3. Block 4 fits Job 4. Job 5 can not be loaded because Blocks 1 to 4 are already occupied and Block 5 has lesser memory than Job 5. Job 5 is placed in the waiting list.
B. Jobs 2 and 4 terminate and leave the memory block they occupy. Job 5 is loaded first. Block 1 is the first memory block that fits Job 5. Job 6 first fits in Block 4. Job 7 is placed in the waiting list for the same reason Job 5 was also placed in the waiting list.
C. Jobs 3 and 6 terminate. Job 7 is loaded to Block 3 where it first fits. Job 8 first fits on Block 4. Job 9 is placed in the waiting list.
D. Jobs 1, 5, and 7 terminate. Job 9 is loaded to Block 2 where it first fits. Job 10 is placed in the waiting list.
E. Job 8 terminates. Job 10 is loaded to Block 4 where it fits.
F. Jobs 9 and 10 continue processing.
G. Job 9 terminates. Job 10 is still processing.
H. Job 10 terminates.
Best- fit
A. Job 1 searches the entire list. It is loaded to the block which produces the smallest excess memory or leftover. In this case, Job 1 is loaded to Block 4, Job 2 to Block 5, Job 3 to Block 1, Job 4 to Block 3, and Job 5 to Block 2.
B. Jobs 4 and 2 terminate. Job 6 is loaded to Block 5, Job 7 to Block 3.
C. Jobs 3, 5, 7, and 6 terminate. Job 8 is loaded to Block 3, Job 9 to Block 2. Job 10 is placed in the waiting list because its memory exceeds the remaining free memory blocks.
D. Job 1 terminates. Job 10 is loaded to Block 4.
E. Job 8 terminates. Jobs 9 and 10 are still processing.
F. Job 9 terminates. Job 10 is still processing.
G. Job 10 terminates.
Worst- fit
A. In this case, the job searches the entire list and is loaded to the block which produces the largest leftover. Block 2 is the block where Job 1 produces the largest leftover. Job 2 to Block 4. Job 3 to Block 3. Job 4 to Block 1. Job 5 is placed in the waiting list.
B. Jobs 4 and 2 terminate. Job 5 searches the list of free memory block. Block 4 produces the largest leftover for Job 5. Job 6 is loaded to Block 1. Job 7 is placed in the waiting list.
C. Jobs 3 and 6 terminate. Job 7 is loaded to Block 3. Job 8 is placed in the waiting list.
D. Jobs 1, 5, and 7 terminate. Job 8 is loaded to Block 2, Job 9 to Block 4. Job 10 is placed in the waiting list.
E. Jobs 8 and 9 are still processing. Job 10 is still in the waiting list.
F. Job 9 terminates. Job 10 is still processing.
G. Job 10 is processing.
H. Job 10 terminates.