Homework 6 Solved

22C:116, Fall 1995

Douglas W. Jones

The problem, part A: How would you identify system pages in the page table?
The answer: One software defined bit would be needed in each page-table entry, call it system_only. This would be set for system pages, and reset for user pages. In addition, a software field would be needed to hold the real access rights for the page, as opposed to the rights known to the hardware, which may differ when a soft page fault is required. Call this new field real_rights.
```
system_mode:
   for every page table entry E
      if E.system_only = 1
         then E.access_rights = E.real_rights
      endif
   endloop

user_mode:
   for every page table entry E
      if E.system_only = 1
         then E.access_rights = no-access
      endif
   endloop
```
The problem, part B: How would your software detect the execution of a gate-crossing instruction by code running in user mode?
The answer: A new software defined bit would be needed in each page table entry to identify the pages that contained gateways. Call this bit gateway_page.
When a program in user mode attempts to reference a system page, it will cause a fault (because all system pages are marked as no-access when in user mode). The fault service routine would then check the nature of the attempted access. If the instruction that caused the fault was a procedure call instruction and the effective address pointed to the first word of a gateway page, the fault service routine would interpret it as a gate crossing soft page fault. Otherwise, it would be interpreted as an illegal memory reference.

The problem, part C: Given that an attempt to cross a gateway has been detected and that you have procedures available for implementing the state change from user to system state and back, outline the structure of a the procedure gate_call(P) that is called within the operating system by the code that detected an attempt to cross the gateway at address P.
The answer:
```
gate_call(P)
  system_state()
  call P()
  user_state()
  return from page-fault trap
```
Warning: The above is probably oversimplified! It is likely to be more complex in real systems.
The problem: Consider the problem of moving a set of files from the access-control-list based system descirbed to the capability-based system described.
In effect, the problem can be solved by using the access control lists to create an access matrix and then using this access matrix to construct a set of capability lists. Algorithmically, this reduces to:
```
For every resource R
   For every user-operation pair  in the ACL for R
      The access matrix entry for user U and resource R is O.
      Put the capability  in the capability list for U.
```
The difficult question is, what do you do with access groups? There are two approaches:
First, one can eliminate them in the process of making the access matrix, so that only real resources show up in the matrix, and what might have been a sparse matrix is no-longer sparse because of the information about groups that was scattered in the matrix. Having done this, the C-list version will involve some very long C-lists unless new C-lists are used to factor out common access rights and simplify the system.
Second, one can do the following direct transformation: For each group in the ACL system, create a C-list. The entries in the C-list for a group give the rights that members of the group had to files accessible to that group, and each user that was a member of the group gets a capability for the group's C-list in their home C-list. This can be described by the following:
```
For every resource R
   If R is a group
      Create a C-list for R, call it CR.
      Por every user U listed in R
         Put a capability for CR in the C-list for U.
   Else
      For every user-operation pair  in the ACL for R
         put the capability  in the capability list for U
         (note that U may be a user's C-list or a group's C-list)
```