In the Multics system, the pages assigned to the operating system were marked as being privileged, while the user's pages were unprivileged. In system state, all pages in the address map were equally addressible, but in user state, it was illegal to reference an address in a privileged page.
The Multics approach to gate crossing was to mark each page that contained the entry point of a system service with a bit indicating that it was an entry point. Such pages were called gateway pages. If a program executing in user state attempted to call a procedure starting at location zero in a gateway page, using a normal procedure call instruction; such a call was called a gate-crossing call.
When the Multics CPU detected a gate-crossing call, it pushed the previous CPU state on the stack along with the return address, and then continued with a normal call. When an attempt was made to return from a gate-crossing call, using a standard procedure return instruction, the saved information was used to restore the CPU state to the caller's state.
As a result of this arrangement, using the gateway and system protection bits in each page table entry and the gate crossing mechanisms built into the CPU, a Multics system call was, from both the user and system programmer's point of view, identical to a standard procedure call. As a result, no assembly language code was required to pass through the gateways from user to system, and system calls could be freely called by system code without using a different version depending on the identity of the caller.
More Background: For this problem, consider a machine with a paged memory management unit with only 3 hardware-recognized states of each page table entry. No-access, read-only, and read-write. There are a number of spare bits in each page-table entry that are not interpreted by hardware, but the hardware does not understand anything like the concept of a privileged page or a gateway page.
The problem, part A: Consider the problem of running this machine with a Multics-like memory model. If the CPU is in user state, only the user's pages should be accessable. If the CPU is in system state, both user and system pages should be accessable.
How would you identify system pages in the page table? Given that the array page_table[] holds the page table entries, where each entry is a record with an access_rights field, some software defined fields you may need, named by you, and other fields that don't matter to this assignment, write code for two procedures, system_mode that changes the page table from the user-mode representation to the system-mode representation, and user_mode, that reverses these changes.
The problem, part B: Given that you have solved part A, how would your software detect the execution of a gate-crossing instruction by code running in user mode? How would your software distingusih such an instruction from an attempt to call a procedure in some page that was not marked as a gatway or from an attempt to call a procedure starting at some location other than location zero of a gateway page.
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 by the code that detected an attempt to cross the gateway at address P. This procedure implement the actual gate crossing and the return. For this assignment, assume that gateway procedures do not take parameters, so you need not deal with their presence.
Consider also a capability based file system where each directory is a capability list. Directory entries therefore name an object and the rights conferred to the user by the use of that capability. Directory entries in this file system may reference either files or directories, and users may reach files by following paths from directory to directory until they reach the file they want.
The problem: In theory, capability lists and access control lists are equally able to describe any access control matrix. In practice, this can be difficult. Consider the problem of moving a set of files from the access-control-list based system descirbed above to the capability-based system. How would you handle this?
Hint: This problem is fairly open ended. It would be trivial if there were no groups in the access control list context and if capability lists could not refer to other capability lists. It is the presence of these complicating factors that makes this problem interesting!