Operating system: multiprogramming operating system

Describe the multiprogramming operating system.

The multiprogramming operating system can execute several jobs concurrently by switching the attention of the CPU back and forth among them. This switching is usually prompted by a relative slow input, output storage request that can be handled by a buffer, spooler or channel freeing the CPU to continue processing .

The primary reason multiprogramming operating system was developed and the reason they are popular, is that they enable the CPU to be utilized more efficiently. If the operating system can quickly switch the CPU to another task whenever the being worked in requires relatively slow input, output or storage operations, then CPU is not allowed to stand idle.

This mean that more can be accomplished a given amount of time. For example, if a disk drive that task can be delegated to channel and the CPU can be put to work in another program while the data are being read in multiprogramming is thus an effective way the fast-working CPU most busy with computations while slower input, output and storage operation are being carried out.

Advantages of multiprogramming operating system:

i) It increases CPU utilization.
ii) It decreases total read time needed to execute a job.
iii) It maximizes the total job throughput of a computer.

Disadvantages of multiprogramming operating system:

i) It is fairly sophisticated and more complex
ii) A multiprogramming operating system must keep track of all kinds of jobs it is concurrently running.

DMA
DMA (Direct Memory Access) unit is capable of transferring data straight from memory to I/O device.

How it works:

First the controller reads the block from the drive serially bit by bit, until the entire block in the controller’s internal buffer. Next it computes the checksum to verify that no reads errors have occurred.


Then the controllers’ causes an interrupt when the operating system starts running, it can read the disk block from the controller’s buffer a byte or a words at a time by executing a loop, with each iteration reading one byte or word from a controller device register and storing in memory .

After the controller has read the entire block from the device into its buffer and verified the checksum, it copies the first byte or word into the main memory at the address specified by the DMA memory address and decrements the DMA count by the numbers of byte just transferred. This process is repeated until the DMA count becomes zero at which time the controller causes an interrupt.

PCB

The operating system all information that it needs about a particular process into a data structure called descriptor or process control block(PCB).

Whenever a process is created (initialized, installed) the operating system creates a corresponding process control block to serve as its run-time description during the lifetime of the process. When the process terminates, its PCB is released to the pool of free cells, from which new PCBs are drawn. A process becomes known to the operating system and thus eligible to complete for system resources only it has an active PCB associated with it.

Each process is represented in the operating system by its own process control block (also called a lack control block). A process control block (PCB) is data block or record containing many pieces of the information associated with a specific process. The information in PCB typically include :

i) process ID/ Number

ii) The process states may be new ready, running or halted.

iii) The program counter indicates the address of the next instruction to be executed for this process.

iv) The CPU registers

v) Any memory management information including base and bounds registers or page tables.

vi) Any accounting information, including the amount of CPU and real time used, time limits account numbers, job or process number and so on.

vii) I/O status information

ix) CPU scheduling information, including a process priority, points to scheduling queues and any other scheduling parameters.


Deadlock prevention

By prevention one of four necessary conditions we can prevent the occurrence of deadlock. Let’s look on the approach by examining each of the four necessary conditions:

i) Mutual exclusion condition: A printer can not be simultaneously shard on the other hand do not require mutually exclusive access, can not be involved in a deadlock. Read only file at the same time, they can be granted simultaneously access to the file. A process never need wait to sharable resources. So it is not possible to prevent deadlocks by denying the mutual-exclusion conditions.

ii) Hold and wait conditions: If we can prevent processes that hold resources from waiting from more resources we can eliminate deadlock. One way to achieve this goal is to require all process to request all their resources before starting execution. If everything is available the process will be allocated whatever it needs and run to completion.

If one or more process are busy, nothing will be allocated and the process would just wait. Another way to break the hold and wait condition is to require a process requesting a resource to first temporarily release all resources it currently holds. Then it tries to get everything it needs all at once.

iii) No preemption condition: If we can serve that no preemption does not hold, we can eliminate deadlocks. The protocol is as follows:

If a process that is holding some resources request another resource that can not be immediately allocated to it (that is process must wait) then all resources currently being hold are preempted. That is, these resources are implicitly released. The preempted resources are added to the list of resources for which the process is waiting. The process will only be restarted when it can regain its old resources, as well as the new ones that it is requesting.

iv) Circular wait conditions: By preventing the circular wait from occurring, we can eliminate deadlock. For this, resources are uniquely numbered and processes can only requests resources in linear ascending order.

Now the protocol is this: process can requests whenever they want to, but all requests must be made in numerical order.

Contiguous allocation scheme.

Contiguous allocation method requires each file to occupy a set of contiguous addresses on the disk. Disk addresses define a linear ordering in the disk. Contiguous location of a file is defined by the disk address of the first block and its length.

The both sequential and direct access can be supported by contiguous allocation. It has two backwards:

The first difficulty is determining how much space is needed fo a new life, once the implementation of free space list is defined, we can decide how to fin space for a contiguous allocation life. This problem can be compared to dynamic storage allocation problem.

Dynamic storage allocation problem: Disk space is viewed as a link list of free, used or allocated segments, each segment is a contiguous set of disk block or a hole, a hole is referred to as an unallocated segment. Dynamic storage allocation problem is how to satisfy a request from a list of free blocks.
Strategies Explanation
Best fit Segment places in hole which is closest to segment size.
First fit Segment is placed in first hole it can fit it.
Next fit Modification of first fit, starts looking at place where the last search ended.
Worst fit A segment is places into the largest possible hole.


Observation on performance:

i) Best fit usually perform the worst, since it leaves behind the smallest possible hole.

ii) First fit is dimpliest to implement and usually fastest and best.

iii) Next fit usually a little worse than the first fit.

The second problem is external fragmentation: External fragmentation exists when enough total disk space exists to satisfy a request, but it is not contiguous; storage is fragmented into large number of small holes. This can be solved by compaction.

Compaction: External fragmentation can be solved by compaction scheme. In compaction scheme, the user copies the entire file system into another floppy disk. The original floppy is then completely freed, creating one large contiguous free space from this one large hole. So compaction scheme effectively compacts all free space into one hole solved the segmentation problem. But it time consuming.

Control program
 Control program permits user-computer communication, log-jobs, overseas the overall computer operation to ensure that the various activities run smoothly and to completion. The principal control programs are described below:

i) The major operating system control program is called the supervisor. The supervisor handles the overall management of a computer system. It is maintained in memory and supervises the loading of other parts of the operating system from secondary storage to main memory as they are needed. It also supervises the application program for execution. The supervisor also interprets user commands and it keep tracks of jobs.

ii) Command interpreter: The portion of operating system that can accept interpret and carry out user’s command is referred to as interpreter. The command interpreter consists of a number of individuals programs modules, each responsible for handling single command.
Individual user’s command to copy a file, FORMAT a disk and so on, are handled by command interpreter. Command to the operating system of a microcomputer are actually requests to execute individual command interpreter programs.

iii) Interrupt handler: The interrupt handler acknowledges and processes all interrupt to the system. One of the most common sources of interrupt if from I/O devices, such as the keyboards, printer and secondary storage. These devices must communicate with the CPU the operating system. Thus operating system never idle, must constantly be on the alert for an interrupt trigged by internal or external events, such as an I/O device indicating that it has completed its task or that an error condition may have occurred.
iv) Input/output control system: The input/output control system (IOCS) schedules and activates the proper I/O device as the storage unit. It also monitors the operation of input/output devices are not available; the IOCS will substitute another device in its place. It control and coordinates the flow of data between I/O devices, for example, from a terminal keyboard to display screen or to other output devices like disk drives and printers.


Four conditions for deadlock must hole in river crossing example.

Coffman et.al (1971) showed that a deadlock situation can arise if and only the four following conditions simultaneously in system.

i) Mutual exclusion condition: There exits shared resources that are used in a mutual exclusion manner. At least one resource is held in non-sharable mode; that in only one process a tone can use the resource. Of another process requests that resource, the requesting process must be delayed until the resource has bees released.

ii) Hold and wait condition: Process hold on the resources they already have while waiting for all allocation of another resources, a process obtaining a lock holds that lock while asking for another.

iii) No-preemption condition: Resources can not be preempted; i.e. can only be resources can not be removed from a process until that process released.

iv) Circular wait: A circular chain of processes exits in which each process hold resources wanted by the next process in the chain. We can see these four conditions in our river crossing example. A deadlock occur if and only two people two people opposite sides of the river meet in the middle. The mutual exclusion condition obviously holds since at must one can be stepping on a stone at one time.

The hold and wait condition is satisfied, since each person is stepping on one stone and waiting to step on the next one. The no-preemption holds, since a stepping stone can not be forcibly removed from the person stepping on it. Finally, the circular-wait condition holds, since the person coming from the east is waiting in the person coming from the west, while the person coming from the west is waiting in the person coming from the east. Neither of the two intern can proceed and each is waiting for other to remove their from one of the stepping stone.