Term
|
Definition
| A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. |
|
|
Term
| T/f: In the bridge crossing example, deadlocks may only be resolved if one car backs up. |
|
Definition
|
|
Term
|
Definition
| Only one process at a time can use a certain resource. |
|
|
Term
| Deadlocks may only occur if all of these 4 conditions hold simultaneously. |
|
Definition
1. Mutual Exclusion - only one process at a time can use a resource.
2. Hold and Wait - a process holding at least one resource is waiting to acquire resources held by other processes.
3. No preemption - a resource can be released only voluntarily by the processes holding it, after that process has completed its task.
4. Circular wait - there is a set of waiting processes such that one of the processes is waiting for a resource that is held by another process which is also waiting for another process, etc etc. |
|
|
Term
| What are the 3 basic methods for HANDLING deadlocks? |
|
Definition
1. ensure system will never enter a deadlocked state.
2. allow the system to ensure a deadlock and then recover.
3. ignore problem. |
|
|
Term
| T/F: Most OS's ignore deadlocks and pretend that they do not occur. |
|
Definition
|
|
Term
|
Definition
| This happens when a process holding at least one resource is waiting to acquire additional resources held by other processes. |
|
|
Term
| What does the term "no preemption mean"? |
|
Definition
| this means that a resource may only be released voluntarily by the process that is holding it, usually after it has completed its task. |
|
|
Term
| Describe a hold and wait. |
|
Definition
| this happens when a process holding at least one resource is waiting to acquire resources held by other processes. |
|
|
Term
| Explain deadlock prevention. |
|
Definition
Goal is to restrain how requests can be made.
1) mututal exclusion - must hold for shareable resources.
2) must guarantee that whenever a process requests a resource, it does not hold any other resources. Require the process to request and be allocated all its resoures before it begins execution or allow the process to request resources only when the process has none.
3: If a process that is holding some resources requests another
resource that cannot be immediately allocated to it, then all
resources currently being held are released |
|
|
Term
| True or false: Deadlock avoidance requires that the system has some additional priori information available |
|
Definition
|
|
Term
| True or false: the deadlock avoidance algorithm dynamicaly examines the resource-allocation state to ensure that there can never be a circular wait condition. |
|
Definition
|
|
Term
| True or false: the resource allocation state is defined by the number of available and allocated resources and the maximum demands of the processes |
|
Definition
|
|
Term
| What is the resource-allocation state. |
|
Definition
| The resource-allocation state is defined by the number of available and allocated resources and the maximum demands of the processes. |
|
|
Term
| With deadlock avoidance, when a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state. |
|
Definition
|
|
Term
| What does it mean that the system is in a safe state? |
|
Definition
| the system is safe if there exists a sequence of all processes such that for each process, the resources that can it can request can be satisfied by the currently available resources plus the resources held by all other processes. |
|
|
Term
| True or false: If a system is in a safe state, then deadlocks may still be possible. |
|
Definition
|
|
Term
| true or false: deadlocks are possible when the system is in an unsafe state. |
|
Definition
|
|
Term
| Deadlock avoidance works by ensuring that the system will never enter an unsafe state. |
|
Definition
|
|
Term
| What are the two deadlock avoidance algorithms? |
|
Definition
| Resource allocation graph for single instance of a resource type and the banker's algorithm for multiple instances of a resource type. |
|
|
Term
| Explain the banker's algorithm. |
|
Definition
| The banker's algorithm is used for multiple instances of each resource. the process must claim it's max use. When a process request a resource, it may have to wait for other processes to complete. After it gets all the resources it needs, it must return them in a finite amount of time. |
|
|
Term
| True or false: Deadlock detection allows the system to enter an deadlocked state and uses a detection algorithm to detect the deadlock. It then uses a recovery scheme. |
|
Definition
|
|
Term
| The deadlock detection algorithm searches for a cycle in the graph |
|
Definition
|
|
Term
| Explain how the system can recover from a deadlock. |
|
Definition
| You can either abort all deadlocked processes or abort one process at a time until the deadlocked cycle is eliminated. |
|
|
Term
| What are some things to consider when selecting which order to abort a process when recovering from a deadlock. |
|
Definition
Priority of the process.
How long the process as computed and how much time it has remaining.
How many resources the process has used and how many it needs to complete.
How many processes need to be terminated.
Is the process interactive or batch. |
|
|
Term
| Explain resource preemption when recovering from a deadlock. |
|
Definition
1. Deciding which victim to abort.
2. Rollback - need to return to some safe state and be able to restart the process for that state.
3. Starvation - if the same process is always picked as a victim, it may be starved so you need to include the number of rollback in the cost factor. |
|
|
Term
| True or false: A program must be brought from disk into main memory and placed within a process for it to be run. |
|
Definition
|
|
Term
| True or false: main memory and registers are only storage CPU can access directly |
|
Definition
|
|
Term
| The CPU can only access what types of memory directly? |
|
Definition
| Main memory and registers |
|
|
Term
| True or False: Register access occurs in one CPU clock or less. |
|
Definition
|
|
Term
| Main memory only takes one cycle to complete |
|
Definition
|
|
Term
| Where is Cache located within the system? |
|
Definition
| Cache sits between the main memory and the CPU registers. |
|
|
Term
| True or false: A pair of base and limit registers define the logical address space? |
|
Definition
|
|
Term
| What defines the logical address space? |
|
Definition
| A pair of base and limit registers. |
|
|
Term
| Address binding of instructions and data to memory address can happen at which different states. |
|
Definition
| During compiling, loading or execution. |
|
|
Term
| True or False: The concept of a logical address space being bound to a separate physical address space is central to proper memory management? |
|
Definition
|
|
Term
| True or false: Logical addresses are generated by the CPU. |
|
Definition
|
|
Term
| Logical addresses are referred to as virtual addresses. |
|
Definition
|
|
Term
| The address as seen by the memory unit is called the physical address |
|
Definition
|
|
Term
|
Definition
| memory management unit is the hardware device that maps the virtual to physical addresses. In this scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory. |
|
|
Term
| True or false: the user program deals with logical addresses and it never sees the real physical address. |
|
Definition
|
|
Term
| True or false: the physical address can be found by adding the logical address to the base. |
|
Definition
|
|
Term
|
Definition
| In dynamic loading, the routines are not loaded until they are called. This allows better memory space utilization because unused routines are never called. This is useful for large amounts of code and also no special OS support is required. |
|
|
Term
|
Definition
| with dynamic linking, linking does not occur until execution time. A small piece of code called a stub is used to locate the needed library file and then repalces itself with the address of the routine and then executes it. In this scheme, the OS needs to see if the routine is in the processes memory. This system is also known as shared libraries. |
|
|
Term
|
Definition
| this is when a process is moved temporarily out of memory and into a backing store and then brought back later for continued execution. |
|
|
Term
|
Definition
| fast disk storage that is large enough to accomodate all copies of memory images for all users, it must provide direct access to these memory images. |
|
|
Term
| True or false: the backing store does not need to provide direct access to the memory images it contains. |
|
Definition
| False, it must so that swapping can occur. |
|
|
Term
| True or false: in priority based scheduling algorithms, the roll out, roll in swapping variant is used. |
|
Definition
|
|
Term
| Explain roll out and roll in. |
|
Definition
| this is a swapping variant that is used for priority based scheduling algorithms. lower priority process is swapped out so that a high priority can be loaded and executed. |
|
|
Term
| True or false: In roll out and roll in swapping, a major part of the swap time is the transfer time. |
|
Definition
|
|
Term
| What is contiguous memory allocation? |
|
Definition
| Main memory is split into two partitions, one for the OS and the other for user processes. Continuous means that each process is contained in a single contiguous section of memory. |
|
|
Term
| True or false: The resident operating system is usually held high in memory. |
|
Definition
|
|
Term
| True or false: the base register contains the value of the smallest physical address. |
|
Definition
|
|
Term
| true or false: the limit register contains the range of physical addresses. |
|
Definition
| False, it contains the range of logical addresses. |
|
|
Term
| True or false: the MMU maps logical addresses dynamically. |
|
Definition
|
|
Term
| Explain the first first storage allocation solution. |
|
Definition
| Allocate the first hole that is large enough. |
|
|
Term
| Explain the worst fit storage allocation method. |
|
Definition
| Allocate the largest hole. It must search the entire list and it produces the largest leftover hole. |
|
|
Term
| Explain the best fit storage allocation. |
|
Definition
| Allocate the smallest hole that is large enough. Must search entire list unless ordered by size. Produces the smallest left over hole. |
|
|
Term
| True or false: First fit and best fit are better than worse fit in terms of speed and storage utilization |
|
Definition
|
|
Term
| What is external fragmentation? |
|
Definition
| this happens as a result of the first and best fit memory allocation strategies. As processes are loaded and removed, the free memory is broken into smaller pieces. External fragmentation exists when there is enough total memory to satisfy a request but the memory is not contiguous. |
|
|
Term
| What is internal fragmentation. |
|
Definition
| When memory is broken down into fixed sized blocks and allocates memory in units based on block size. With this approach, the memory allocated to a process may be slighly larger than the requested memory. The difference between the memory allocated and needed is the internal fragmentation -- unused memory that is internal to one particular partition. |
|
|
Term
|
Definition
| If memory is fragmented, then it can be shuffled around so that all the free memory is together in one large block. |
|
|
Term
| True or false: Compaction is possible with static relocation. |
|
Definition
| False, relocation must be dynamic and done at execution time. |
|
|
Term
|
Definition
| Paging is a memory management scheme that permits the physical address space of a process to be non-contiguous. |
|
|
Term
| True or false: External fragmentation and compaction can be avoided by using Paging? |
|
Definition
|
|
Term
| Paging is used in most operating systems? |
|
Definition
|
|
Term
| What is the file control block? |
|
Definition
| This is a storage structure which consists of information about a file including ownership, permiossions and location of the file contents. |
|
|
Term
| True or false, the file System is organized into only one layer. |
|
Definition
| False, it is made up of 6 layers. |
|
|
Term
| What is the purpose of the file system? |
|
Definition
| Provides efficient and convenient access to disk by allowing data to be stored, located and retrieved easily. |
|
|
Term
| What controls the file system hardware? |
|
Definition
|
|
Term
| What are the 6 layers of the file system? |
|
Definition
1. Application programs.
2. logical file system.
3. file-organization module
4. basic file system
5. IO control
6. devices |
|
|
Term
| True or false: The boot control block contains info needed by the system to boot OS from that volume. |
|
Definition
|
|
Term
| What is the boot control block? |
|
Definition
| Contains info needed by the system to book an OS from the volume. In UFS, it is called the boot block, in NTFS it is the partition boot sector. |
|
|
Term
| True or False: The Volume Control Block contains volume details such as the number of blocks in the partition, the size of the blocks, or free-block counter and points. |
|
Definition
|
|
Term
| What is the purpose of the volume control block? |
|
Definition
| To store information about the volume such as number of blocks in the partition, block size, available block count and free block pointers. |
|
|
Term
| True or False: The directory structure is used to organize files. |
|
Definition
|
|
Term
| What is the purpose of the Directory Structure? |
|
Definition
|
|
Term
| True or false: An in-memory mount table contains information about each mounted volume |
|
Definition
|
|
Term
| What is the in memory directory-structure? |
|
Definition
| This cache holds the directory information of recently accessed directories. |
|
|
Term
| True or false: The system-wide open-file table contains a copy of the FCB of each open file, as well as other info. |
|
Definition
|
|
Term
| True or false: The VFS, or virtual file system, provides an OOP way of implementing file systems. |
|
Definition
|
|
Term
| What are the 3 file system allocation methods? |
|
Definition
|
|
Term
| Explain contiguous allocation as it related to file structure |
|
Definition
| Each file occupies a set of contiguous blocks on the disk. It is the most simple since only the starting block # and the length (num of blocks) are required. It is random access but it wastes space and does not allow files to grow. |
|
|
Term
| What are the disadvantages of continuous memory allocation? |
|
Definition
| It wastes space and does not allow files to grow. |
|
|
Term
| True or false: Contiguous allocation is wasteful of space and does not allow files to grow. |
|
Definition
|
|
Term
| True or false: An extent is a contigous block of disks used for file allocation. |
|
Definition
|
|
Term
| True of false: A file in an extent-based system may consist of one or many extents. |
|
Definition
|
|
Term
| Explain linked allocation. |
|
Definition
| Each file is a linked list of disk blocks where the blocks can be scattered anywhere on the disk. |
|
|
Term
| Explain indexed allocation. |
|
Definition
| This brings all pointers together into an index block. The index block contains all the pointers to the memory locations so that is can access. Avoid external fragmentation but the index block uses overhead. |
|
|
Term
| What are file attributes? |
|
Definition
| Information about a file. Includes, name, identifier, type, location, size, protection/permissions, time/date/user identification. All stored within the directory structure. |
|
|
Term
| True or false: The file name is stored in the Name attribute |
|
Definition
|
|
Term
| True or False: A File Identifier is the unique tag number that identifies the file within the system. |
|
Definition
|
|
Term
|
Definition
| This is a pointer to the location on the device. |
|
|
Term
| In terms of File Attributes, what is protection? |
|
Definition
| Controls who can do reading writing and execution. |
|
|
Term
| True or false. Information about files are kept in the Directory Structure, which is maintained on the disk |
|
Definition
|
|
Term
| What are the various file operations? |
|
Definition
| Create, write, read, reposition within file, delete, truncate, open, and close. |
|
|
Term
| What information is needed to open a file? |
|
Definition
1. file pointer
2. file open counter
3. disk location
4. access rights |
|
|
Term
| True or False: The LRU algorithm replaces the page that has not been used for the longest period of time. |
|
Definition
|
|
Term
|
Definition
| When the system references a page that is not yet in memory it will generate a trap to the OS. |
|
|
Term
| How does the system handle a page fault |
|
Definition
| Determine if the reference is invalid, if not and the page is just not in memory then get an empty frame and swap the page into it. Reset the tables and set the validation bit to v (valid) and then restart the instruction. |
|
|
Term
|
Definition
| Effective access time describes the time requirement for demand paging. It is = (1-p)x time + p(avg. page fault service time). |
|
|
Term
| What does copy on write (cow) do? |
|
Definition
| Allows both the parent and child process to initially share the same pages in memory. If either process modifies a shared page, then the page is copied. |
|
|
Term
| True or false: COW allows more efficient process creation as only modified pages are copied. |
|
Definition
|
|
Term
| What is page replacement? |
|
Definition
| when there is no free frame available, we must find a process to swap out and replace. |
|
|
Term
| What is a modify or dirty bit? |
|
Definition
| This is a bit used to identify if a page has been modified. This is used to ensure that only modified pages are written to disk. There is no need to rewrite a page to disk if it is already there. This reduces the overhead associated with the page replacement algorithms. |
|
|
Term
| True or false: page replacement completes separation between logical memory and physical memory. |
|
Definition
|
|
Term
| Describe the page replacement process. |
|
Definition
1. Fine the location of the desired page on disk.
2. Find a free frame, if there IS a free frame, use it. If there it not a free frame, must select a victim frame.
3. bring the desired page into the new frame and update the page and frame tables.
4. Restart the process. |
|
|
Term
| True or False: Page replacement algorithms can be evaluated using a reference string and then computing the number of page faults on it. |
|
Definition
|
|
Term
| True or False: The optimal algorithm replaces pages that will not be used for the longest periods of time. |
|
Definition
|
|
Term
|
Definition
| Thrashing occurrs when a process does not have enough pages resulting in a high page-fault rate. this causes the process to remain busy swapping pages in and out. |
|
|
Term
| True or false: thrashing results in low cpu utilization |
|
Definition
|
|
