Homework 6 Solved

22C:116, Fall 1995

Douglas W. Jones
  1. 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.

  2. 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)