List and describe the 4 preconditions that have to be present for a deadlock to form.
Mutual Exclusion: Only one process may hold a protected resource at a time. No process may access a resource that is being held by a different process.
Hold and Wait: A process is allowed to hold a process while waiting to hold a process being held by a different process.
No Preemption: A process cannot be forced to release the resources it holds.
Circular Wait: A deadlock is a set of blocked process where each process is blocked waiting for a resource that is being held by another blocked process in the set.
What does it mean to ‘allow preemption’ of a process’s ownership of a held resource (e.g. the Bank Account example) in order to break a deadlock?
What is the problem with implementing the preemption of the resources held by a process involved in a deadlock set? Hint: Can we rollback a process’s state?
What is the only general solution to causing a process to release its ownership of the resources it holds / owns?
Preemption means for the OS to somehow cause a selected process in the deadlock set to release the resources it holds (has locked) allowing other processes in the deadlock set access to those resources and to make progress i.e. to break the deadlock.
The problem is that it is normally impossible to ‘roll back’ a process to the state it was in before it locked the contested resource. For example, the process may have modified local or static variables. The process might also have modified some shared / global resource such as a file or global data structure. These types of changes cannot be ‘undone’ and so preemption is impossible. Also know that DBMS allow the rollback of changes made to tables and so can rollback a transaction started by a process.
The only general solution to causing a process to release ownership of its resources is to terminate the process.
Describe the method presented in the book and slides of preventing deadlocks because of the “Circular Wait” precondition. Hint: Ordered Resource Locks
How would this method be applied to preventing the deadlock for the “transfer funds between two bank accounts” operation described in class? That is, an operation that locks two bank accounts with the goal of transferring funds from Account1 to Account2.
The method of avoiding ‘circular wait’ involves assigning a ordering / priority to the system’s resources that determine the order in which the resources must be requested. This method prevents processes from requesting resources in an order that creates a circular dependency.
The example had the transfer operation lock the resources in the numerical or alphabetical order of the bank account’s ID. The two processes would always attempt to lock accounts in the same order making deadlock impossible
Describe both the logical and physical views of a process image’s memory addresses.
What is the device that translates from logical to physical addressing?
Logical View: The logical view of the process image is the illusion that the image is installed in a contiguous range of memory addresses that starts at address zero and extend to N (the image size). The process logical address space is owned by the process and is separate from all other process images. That is, that every process has its own private 0-N address space.
Physical View: The physical view of the process image is the reality that all process images share common physical memory range of 0–M where M is the amount of system memory. Each process is installed into a memory partition at unique addresses in physical memory. Partitions can be relocated to new addresses, and with paged memory management can be placed in non-contiguous (non-adjacent) memory regions.
The translation from logical to physical addresses is primarily accomplished by the system’s Memory Management Unit hardware.
Consider a simple paging system with the following parameters:
* 2^32 bytes of physical memory address range.
* A page size of 2^10 bytes.
- What is the size of a frame?
- How many bits of a logical address are used to identify (index) a page table entry?
- How many entries are needed in the process’s page table?
- How many bits are needed in each page table entry?
- A frame is the same size as a page, 2^10 bytes.
- 10 bits are used as the offset into the page / frame, so 22 (32-10) bits remain to index into the page table.
- There is one Page Table Entry for each page in the logical address space, so 2^22 entries are needed.
- Ignoring the present and modified bits, 22 bits are needed in each PT Entry to specify the base address of the frame in physical memory.
What are the two characteristics of simple memory paging that lead to, and the fundamental idea defines virtual memory? Hint: Three parts in slides.
The two characteristics of simple paging are:
1. Because of the indirection between logical and physical addresses made possible with the page table, a process’s pages can be located in any frame of memory and can be moved (relocated) from one frame to another.
2. The frames occupied by a process’s pages do not need to be contiguous i.e. they can be spread throughout physical memory.
And the fundamental idea in virtual memory is:
3. Not all of a process’s pages need to be resident in physical memory for the process to execute. Only those pages in the process’s working set need to be resident.
- Describe Page Fault.
- Describe Page Fault Rate (PFR).
- Describe Thrashing.
- A page fault is the interrupt generated by the memory management unit when the process references a page that is not resident in memory i.e. the page table entry is not present.
- The page fault rate is a metric that describes the number of page faults that occur over some time period e.g. PFs per minute.
- Thrashing occurs when the system’s page fault rate (PFR) rises to a point that no processes can make progress i.e. each time the process is scheduled for execution (is made runnable) its execution takes it to a non-resident page and the page fault blocks the process’s execution.
- Describe a process’s Resident Set.
- What is the result of setting a process’s resident set size too small?
- What is the result of setting a process’s resident set size too large?
The resident set is the set of process pages that are resident in memory i.e. are contained in a memory frame.
A resident set that is too small will cause an increase in the number of page faults and so will cause the process to begin thrashing.
A resident set that is too large wastes memory (frames) by maintaining process pages in memory that are no longer being referenced by the process. This has the effect of reducing the overall number of processes that can be maintained in memory.
- Describe a process’s Working Set.
- Describe the relationship between the size of a process’s working set and its resident set.
- Generally, how is a process’s page fault frequency used to adjust a process’s resident set size i.e. how should the resident set size be adjusted if the process’s page fault rate increases and why?
- The Working Set is the set of pages that the process currently needs to execute i.e. the process’s locality. Any page in the working set that is not resident must be paged in.
- The working set size should smaller than the resident set size i.e. the resident set should include at least the working set. If the resident set is smaller than the process’s working set, the process will begin to thrash. If the resident set is much larger than the working set, the system is wasting frames (memory) on unneeded resident pages.
- The OS can monitor the PF Frequency and use it as an indicator of how to adjust the process’s resident set size up or down. If the resident set is smaller than the working set, the PF Frequency will rise providing an indication that the process’s resident set’s size must be increased. When the resident set contains the working set, the PF Frequency will drop to near zero indicating that the resident set may be reduced.
- Describe the difference between an IO-Bound and a Compute-Bound process.
- Describe Processor Burst Time.
- How is Processor Burst Time duration affected by IO and Compute bound processes?
- IO-Bound: Processes that make frequent I/O requests or system calls that cause the process to block e.g. an application that is retrieving and persisting data to files such as a database.
- Compute-Bound: Processes that spend most of their time processing data and will run for extended periods without making blocking system calls.
- Processor burst time is the time a process spends executing before being blocked (I/O) or preempted (timer interrupt).
- A process that is compute-bound will have longer processor burst times. Compute bound processes will not often block for I/O and so are more likely to run for their entire scheduling quantum. Processes that are I/O bound are likely to run for a small amount of their quantum before making a blocking I/O system call.
Describe the problem with fairness with Preemptive Round-Robin scheduling WRT I/O-bound processes vs. compute-bound processes.
RR scheduling allows a process to complete its quantum (time-slice) and then schedules the next process at the head of the queue. A compute-bound process will likely execute for its full quantum without blocking. However, an I/O-bound process is more likely not to use its entire quantum before being blocked (I/O) and rescheduled when the I/O operation completes. Thus because an I/O-bound process seldom finishes its quantum before blocking, it will receive less processor time than a compute-bound process.
- In the context of Multiprocessor Scheduling, describe the difference between Static Assignment vs. Dynamic Assignment of threads to processors.
- As described in the slides, how are both strategies implemented? Hint: queues.
- With static assignment, newly created threads are attached to, and execute on, the same processor throughout is lifetime (unless moved by a load balancer).
With dynamic assignment, ready threads are assigned by the dispatcher to any available processor i.e. threads migrate between processors. - Static assignment is implemented with per-processor ready queues.
Dynamic assignment is implemented with a single, global ready queue.
- Describe why we describe drives as block devices.
- Explain how data is addressed and retrieved from block devices.
- Describe the steps required to update the data (e.g. a record) stored on a block device.
- Block devices stores and manages its data in fixed sized blocks of 4096 bytes of data. Data is transferred to / from these devices as blocks of data rather than one word / byte at a time.
- The OS commands the device to retrieve data, or save data as specific block addresses starting at one (first block) though block N where N is the capacity of the drive (in bytes) divided by the block size.
- Data Update:
a. The block containing the record must be read from the device into memory.
b. The record within the block is updated in memory.
c. The entire block is written back to the drive. This includes the data surrounding the record which was not updated.
The key point is that data is not manipulated directly on the drive. The block containing the data to be updated must first be copied into memory where it can be accessed by the processor.
- What is the advantage of caching disk blocks in memory?
- What is the danger that comes from caching disk blocks in memory?
- A program may need to be certain that all its currently dirty block have been written to disk before proceeding e.g. a Database server. What system call does the Linux OS provide to the developer to address this problem?
- The advantage of caching disk blocks in memory is that the second, third, etc. access of a cached block does not require a relatively slow disk read operation.
- There is the danger of losing data that was written by the process and the system crashing before the ‘dirty block’ has been physically written back to disk.
- The Linux/UNIX OS provide the system call is fsync(). The call fsync() forces the OS to write the data block cached in memory out to the disk. This includes not only cached data blocks, but the blocks maintaining file system data structures such as the FAT and Unallocated Block List.
- What are three advantages of RAID1 (mirroring) given in the book? (Assume a two disk RAID)
- What is the primary disadvantage of RAID1?
Raid 1 is also known as “disk mirroring” where data is duplicated across (written to and read from) two disks.
1. Data on the logical RAID drive is protected from a single-disk failure.
2. A read request can be serviced by either of two disks and two read requests can be executed concurrently.
3. Even though both disks need to be updated for a write operation, the write can be executed concurrently on both disks.
Disadvantage: Because a block is mirrored on two disks, RAID1 uses only half the physical capacity of the RAID.
- What advantage does RAID2-6 have over RAID1?
- What disadvantage does RAID2-6 have when compared to RAID1? Hint: How is data retrieved when a disk is lost?
The advantage of RAID2-6 is that redundancy is obtained with only a single additional disk that maintains the stripe’s parity information. (unlike RAID1 which requires 2x the disks).
When RAID2-6 loses a data disk, the data must be reconstructed dynamically by reading from each of the remaining blocks in the missing block’s strip plus the parity block to reconstruct data from the missing disk. That is, N-1 block reads to reconstruct blocks from the missing disk.
Describe the purpose of the File Descriptor.
File descriptors are a resource created and managed by the operating system. File descriptors are a data structure created by system calls that create new files or open existing files. The file descriptor is used by system calls that manipulate the contents of a file i.e. read, write, seek, etc. The file descriptor maintains state information about the open file e.g. the stream index (position) of the next read or write operation on the open file.
- Describe the purpose of the File Allocation Table.
- Describe the purpose of the Unallocated Block List.
- The FAT is the data structure used to maintain the association between a file and the blocks allocated to storing the file’s contents including the ordering of the blocks.
- The UBL is the list (set) of blocks that are currently not allocated to any file. It is the file system’s free space.
- Describe the purpose of the ‘Inode’.
- What information is maintained in the FAT for Indexed Allocation with Inodes?
- How is inode overflow handled in the Linux filesystem?
- The Inode (Index Node or Index Block) is a disk block that maintains an ordered list of block numbers (addresses). The blocks in the list contain the file’s contents.
- The FAT contains the file name and block address of the file’s inode.
- When the size of the file exceeds the number of direct block addresses in the root inode, the root node maintains pointers to indirect address blocks which is a block containing file block addresses. Indirect address blocks can be nested like trees allowing for very large file sizes. See Slide 44 “Linux Nested Block Structure”.
