1. A colleague of yours believes the deadlock problem in resource allocation can be solved using protection domains: make sure each resource appears in one protection domain only. With no sharing among domains, there can be no deadlock. What do you think of your colleague's idea? Explain.

   ---

   It's not a good idea, because your colleague misunderstands how protection domains are used. Even if each resource only appears in one protection domain, the same protection domain may be assigned to several processes, re-introducing sharing.

   Several people also pointed out that there still could be deadlock among the resources in a single protection domain (for example, put all the philosopher's forks in one protection domain).

   ---

2. You are designing a high-performance file system for a computer architecture with a small amount of primary store and a single disk that will be between 90 and 95% full. How should your file system keep track of the free disk blocks? Explain.

   ---

   Your file system should use linked lists. Because the disk is almost full, there will be few free disk pages. Under those conditions, a bit-map free list will be sparse and searching it will be expensive in disk I-O. With a link-list, no searching is required because each link contains pointers directly to the free blocks, saving on expected disk I-O.

   ---

3. You have to determine the security profile (that is, the list of objects accessed and how they are accessed) for an application (a text editor, say). Would you rather the protection mechanisms be implemented with capabilities or access control lists, or doesn't it make a difference? Explain.

   ---

   It makes a difference. A capability is a reference to an object and the operations allowed on the referenced object. The list of capabilities owned by an application is the security profile of the application. The operating system maintains an application's capability list, and so finding the application's security profile is as easy as making a system call, assuming the proper permissions.

   An access control list indicates, for each object, which protection domains can perform which operations on the object. With ACLs, finding an application's security profile involves a search over all objects in the system, examining each ACL to see if it includes the application's protection domain. This may or may not be more complicated than finding the capability list, but it certainly takes more time.

   ---

4. Explain how large disk blocks help make linked index lists a more useful technique for keeping track of disk block allocations for files. Explain the trade-off that prevents disk blocks from growing too large.

   ---

   The larger the disk block, the smaller the linked index list. The larger the disk block, the greater lost disk space due to internal fragmentation.

   ---

This page last modified on 13 December 2000.