Process Termination To eliminate the deadlock, we can simply kill one or more processes. For this, we use two methods:
Abort all the Deadlocked Processes: Aborting all the processes will certainly break the deadlock but at a great expense. The deadlocked processes may have been computed for a long time, and the result of those partial computations must be discarded and there is a probability of recalculating them later.
Abort one process at a time until the deadlock is eliminated: Abort one deadlocked process at a time, until the deadlock cycle is eliminated from the system. Due to this method, there may be considerable overhead, because, after aborting each process, we have to run a deadlock detection algorithm to check whether any processes are still deadlocked.
Advantages of Process Termination
It is a simple method for breaking a deadlock. It ensures that the deadlock will be resolved quickly, as all processes involved in the deadlock are terminated simultaneously. It frees up resources that were being used by the deadlocked processes, making those resources available for other processes.
Disadvantages of Process Termination
It can result in the loss of data and other resources that were being used by the terminated processes. It may cause further problems in the system if the terminated processes were critical to the system’s operation. It may result in a waste of resources, as the terminated processes may have already completed a significant amount of work before being terminated. For Process Destroy a process: Although killing a process can solve our problem, choosing which process to kill is more important. The operating system typically terminates a process after it has completed the least amount of work. End all processes: Although not suggestible, this strategy can be used if the issue worsens significantly. Because each process will have to start from scratch after being killed, the system will become inefficient. Resource Preemption To eliminate deadlocks using resource preemption, we preempt some resources from processes and give those resources to other processes. This method will raise three issues –
Selecting a victim: We must determine which resources and which processes are to be preempted and also in order to minimize the cost.
Rollback: We must determine what should be done with the process from which resources are preempted. One simple idea is total rollback. That means aborting the process and restarting it.
Starvation: In a system, it may happen that the same process is always picked as a victim. As a result, that process will never complete its designated task. This situation is called Starvation and must be avoided. One solution is that a process must be picked as a victim only a finite number of times.
Advantages of Resource Preemption
It can help in breaking a deadlock without terminating any processes, thus preserving data and resources. It is more efficient than process termination as it targets only the resources that are causing the deadlock. It can potentially avoid the need to restart the system.
Disadvantages of Resource Preemption
It may lead to increased overhead due to the need to determine which resources and processes should be preempted. It may cause further problems if the preempted resources were critical to the system’s operation. It may cause delays in the completion of processes if resources are frequently preempted. Module 5 Secondary – Storage Structure Magnetic disks provide a bulk of secondary storage. Disks come in various sizes and speed. Here the information is stored magnetically. Each disk platter has a flat circular shape like CD. The two surfaces of a platter are covered with a magnetic material. The surface of a platter is logically divided into circular tracks, which are subdivided into sectors. Sector is the basic unit of storage. The set of tracks that are at one arm position makes up a cylinder.
The number of cylinders in the disk dirve equals the number of tracks in each platter. There may be thousands of concentric cylinders in a disk drive, and each track may contain hundreds of sectors. The storage capacity of disk drives is measured in gigabytes.
The head moves from the inner track of
the disk to the outer track. When the disk drive is operating the disks is rotating at a constant speed.
To read or write the head must be
positioned at the desired track and at the beginning of the desired sector on that track.
• Seek Time:-Seek time is the time required to
move the disk arm to the required track. • Rotational Latency(Rotational Delay):- Rotational latency is the time taken for the disk torotate so that the required sector comes under the r/w head. • Positioning time or random access time is the summation of seek time and rotational delay. • Disk Bandwidth:-Disk bandwidth is the total number of bytes transferred divided by total time between the first request for service and the completion of last transfer. • Transfer rate is the rate at which data flow between the drive and the computer.
As the disk head flies on an extremely thin cushion of air, the head will make contact with the disk surface. Although the disk platters are coated with a thin protective layer, sometimes the head will damage the magnetic surface. This accident is called a head crash.
Magnetic Tapes Magnetic tape is a secondary-storage medium. It is a permanent memory and can hold large quantities of data. The time taken to access data (access time) is large compared with that of magnetic disk, because here data is accessed sequentially. When the nth data has to be read, the tape starts moving from first and reaches the nth position and then data is read from nth position. It is not possible to directly move to the nth position. So tapes are used mainly for backup, for storage of infrequently used information.
DISK STRUCTURE Each disk platter is divided into number of tracks and each track is divided into number of sectors. Sectors is the basic unit for read or write operation in the disk. Modern disk drives are addressed as a large one-dimensional array. The one-dimensional array of logical blocks is mapped onto the sectors of the disk sequentially. Sector 0 is the first sector of the first track on the outermost cylinder. The mapping proceeds in order through that track, then through the rest of the tracks in that cylinder, and then through the rest of the cylinders from outermost to innermost.
The disk structure (architecture) can be of two types –
i) Constant Linear Velocity (CLV)
ii) Constant Angular Velocity (CAV)
i) CLV - The density of bits per track is uniform. The farther a track is from the center of the disk, the greater its length, so the more sectors it can hold. As we move from outer zones to inner zones, the number of sectors per track decreases. This architecture is used in CD-ROM and DVD-ROM. ii) CAV – There is same number of sectors in each track. The sectors are densely packed in the inner tracks. The density of bits decreases from inner tracks to outer tracks to keep the data rate constant.
CAV CLV DISK ATTACHMENT Computers can access data in two ways. i) via I/O ports (or host-attached storage) ii) via a remote host in a distributed file system( or network-attached storage)
i) Host-Attached Storage Host-attached storage is storage accessed through local I/O ports. Example : the typical desktop PC uses an I/O bus architecture called IDE or ATA. This architecture supports amaximum of two drives per I/O bus. The other cabling systems are – SATA(Serially Attached Technology Attachment), SCSI(Small Computer System Interface) and fiber channel (FC).
SCSI is a bus architecture. Its physical medium is usually a ribbon cable. FC is a high- speed serial architecture that can operate over optical fiber or over a four-conductor copper cable. An improved version of this architecture is the basis of storage-area networks (SANs).
ii) Network-Attached Storage
A network-attached storage (NAS) device is a special-purpose storage system that is accessed remotely over a network as shown in the figure. Clients access network-attached storage via a remote-procedure-call interface. The remote procedure calls (RPCs) are carried via TCP or UDP over an IP network—-usually the same local-area network (LAN) carries all data traffic to the clients.
Network- attached storage provides a convenient way for all the computers on a LAN to share a pool of storage files.
iii) Storage Area Network(SAN)
A storage-area network (SAN) is a private network connecting servers and storage units. The power of a SAN lies in its flexibility. Multiple hosts and multiple storage arrays can attach to the same SAN, and storage can be dynamically allocated to hosts. A SAN switch allows or prohibits access between the hosts and the storage. Fiber Chanel is the most common SAN interconnect. Module V – Sec. Storage Strucutre, Protection, Linux case study
DISK SCHEDULING
Different types of disk scheduling algorithms are as follows:
• FCFS (First Come First Serve) • SSTF(Shortest Seek Time First) • SCAN (Elecvator) • C-SCAN • LOOK • C-LOOK
i) FCFS scheduling algorithm: This is the simplest form of disk scheduling algorithm. This services the request in the order they are received. This algorithm is fair but do not provide fastest service. It takes no special care to minimize the overall seek time. Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37,122, 14, 124, 65, 67
If the disk head is initially at 53, it will first
move from 53 to 98 then to 183 and then to 37, 122, 14, 124, 65, 67 for a total head movement of 640 cylinders. The wildswing from 122 to 14 and then back to 124 illustrates the problem with this schedule.
Prof. Sreelatha P K, CSE Dept. Page 4
Module V – Sec. Storage Strucutre, Protection, Linux case study
ii) SSTF ( Shortest Seek Time First) algorithm: This selects the request with minimum seek time from the current head position. SSTF chooses the pending request closest to the current head position. Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14, 124, 65, 67
If the disk head is initially at 53, the
closest is at cylinder 65, then 67, then 37 is closer then 98 to 67. So it services 37, continuing we service 14, 98, 122, 124 and finally 183. The total head movement is only 236 cylinders. SSTF is a substantial improvement over FCFS, it is not optimal.
iii) SCAN algorithm: In this the disk arm starts moving towards one end, servicing the request as it reaches each cylinder until it gets to the other end of the disk. At the other end, the direction of the head movement is reversed and servicing continues. The initial direction is chosen depending upon the direction of the head.
Eg:-:-consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14, 124, 65, 67
If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65, 67, 98, 122, 124 and183. At cylinder 199 the arm will reverse and will move towards the other end of the disk servicing 37 and then 14. The SCAN is also called as elevator algorithm.
Prof. Kavyashree S, ISE Dept. Page 5
Module V – Sec. Storage Strucutre, Protection, Linux case study
If the disk head is initially at 53 and if the head is moving towards 0th track, it services 37 and then 14. At cylinder 0 the arm will reverse and will move towards the other end of the disk servicing 65, 67, 98, 122, 124 and 183.
iv) C-SCAN (Circular scan) algorithm:
C-SCAN is a variant of SCAN designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from end of the disk to the other servicing the request along the way. When the head reaches the other end, it immediately returns to the beginning of the disk, without servicing any request on the return. Eg:- consider a disk queue with request for i/o to blocks on cylinders. 98, 183, 37, 122, 14, 124, 65, 67
If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65, 67, 98, 122, 124 and 183. At cylinder 199 the arm will reverse and will move immediately towards the other end of the disk, then changes the direction of head and serves 14 and then 37.
Note: If the disk head is initially at 53 and if the head is moving towards track 0, it services 37 and 14 first. At cylinder 0 the arm will reverse and will move immediately towards the other end of the disk servicing 65, 67, 98, 122, 124 and183.
Prof. Kavyashree S, ISE Dept. Page 6
Module V – Sec. Storage Strucutre, Protection, Linux case study
v) Look Scheduling algorithm:
Look and C-Look scheduling are different version of SCAN and C-SCAN respectively. Here the arm goes only as far as the final request in each direction. Then it reverses, without going all the way to the end of the disk. The Look and C-Look scheduling look for a request before continuing to move in a given direction.
A drive has 200 cylinders numbered 0 to 199. The drive is currently serving a request 53 .The queue of pending requests in order is: 98, 183, 37, 122, 14, 124, 65, 67 starting from current head position, what is total distance travelled for LOOK Algorithm, if the head is moving towards 0?
If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65, 67, 98, 122, 124 and183. At the final request 183, the arm will reverse and will move towards the first request 14 and then serves 37.
vi) C-Look Scheduling algorithm:
If the disk head is initially at 53 and if the head is moving towards the outer track, it services 65, 67, 98, 122, 124 and 183. At the last request, the arm will reverse and will move immediately towards the first request 14 and then serves 37.
Prof. Kavyashree S, ISE Dept. Page 7
Module V – Sec. Storage Strucutre, Protection, Linux case study
Selection of a Disk-Scheduling Algorithm
SSTF is commonly used and it increases performance over FCFS.SCAN and C-SCAN algorithm is better for a heavy load on disk. SCAN and C-SCAN have less starvation problem. Disk scheduling algorithm should be written as a separate module of the operating system.SSTF or Look is a reasonable choice for a default algorithm.
SSTF is commonly used algorithms has it has a less seek time when compared with other algorithms. SCAN and C-SCAN perform better for systems with a heavy load on the disk, (ie. more read and write operations from disk).
Selection of disk scheduling algorithm is influenced by the file allocation method, if
contiguous file allocation is choosen, then FCFS is best suitable, because the files are stored in contiguous blicks and there will be limited head movements required. A linked or indexed file, in contrast, may include blocks that are widely scattered on the disk, resulting in greater head movement.
The location of directories and index blocks is also important. Since every file must be opened to be used, and opening a file requires searching the directory structure, the directories will be accessed frequently. Suppose that a directory entry is on the first cylinder and a file's data are on the final cylinder. The disk head has to move the entire width of the disk. If the directory entry were on the middle cylinder, the head would have to move, at most, one-half the width. Caching the directories and index blocks in main memory can also help to reduce the disk-arm movement,particularly for read requests.
Because of these complexities, the disk-scheduling algorithm is very important and is
written asa separate module of the operating system.
