What is the difference between access control lists and capabilities?

The theme of this exam is that you are to write a new OS based on a simplistic OS I wrote
for a senior project, lo these many years ago. Your hardware platform is a single board
computer with a 6809 processor, an RS-232 serial interface for a terminal, and an SD card
for storage. Details will appear as needed in the questions, but if anything seems to be
missing, feel free to ask.
1. Short Answer
a) (4 points) If the maximum speed of our RS-232 port is 115,200 bits/sec, how many
characters per second can we transmit to the terminal?
b) (4 points) If the CPU averages 1µS per instruction, how many instructions can we
have in the transmit interrupt handler and still be able to transmit at full speed?
c) (4 points) What is the difference between access control lists and capabilities?
d) (4 points) What are the different roles of the upper half and the lower half of a device
driver?
e) (4 points) Which of the classes of systems in the DOD Orange Book represents the
highest level of trust?
1
2) The 6809 processor works with 16-bit memory addresses and is byte addressed (i.e.
8-bit data units). The physical memory on the computer is 128KB. Further, the upper
16KB of the virtual address space is divided into an 8KB section for I/O and an 8KB
section for boot ROM.
a) (3 points) If the two 8KB blocks at the upper end of the virtual address space are
the only reserved parts of the address space, how much does that leave for RAM?
b) (3 points) The system has a very simple memory management unit that works with
a small number of relatively large pages. If the RAM portion of the memory space is
divided into three pages, how large is each page?
c) (3 points) How many page frames can the physical memory be divded into?
d) (3 points) How many bits are needed then to specify the page frame number?
e) (4 points) If the OS takes one physical page that is shared in the virtual space of all
processes and each process is given two full pages of RAM, how many processes can be
resident in memory at once?
f) (4 points) Sketch the virtual and physical memory spaces showing which regions are
used for what purposes.
2
3) As is typical, the 6809 keeps interrupts disabled between the time that an interrupt
is received and the time that a return from interrupt instruction is executed. Input and
output to the terminal is interrupt-driven. In particular, each time a character is received
from the terminal, an interrupt gets generated, and each time a character is finished
being transmitted to the terminal, an interrupt is generated. You have two registers for
reading and writing characters. Access to them is provided by routines called inserial()
and outserial().
a) (5 points) If there is a buffer of characters that have been received and not processed
and another buffer of characters that have been generated but not transmitted, briefly
describe the operation of the receive interrupt handler.
b) (5 points) What type of mutual exclusion mechanism should be used in the upper
half of the driver when putting characters into the transmit buffer?
c) (5 points) Using a mixture of pseudo-code and C, draft out the transmit routine in
the upper half of the driver with the lock and unlock operations in the right places.
3
For communicating with the SD card, there’s a different type of serial communication
that’s used. You have three signals: a clock, a one bit input, and a one bit output. These
are available to you on the low order three bits of an I/O port called A. You have routines
to access that port called ina() and outa(). The technique you need to use is called bitbanging. For each bit you send, you will need to set the bit value on the output, set the
clock to 1, and finally set the clock to 0. You should transmit the bits least significant bit
first.
d) (5 points) Using a mixture of pseudo-code and C, draft a routine that takes a byte
(character) as an argument and transmits it to the SD card.
4
4) You are relieved to learn that although SD cards usually have FAT file systems on
them, you will be implementing a somewhat more simplistic file system. Here, the disk
(SD card) will be divided into a number of contiguous groups of blocks, each of which will
contain all the files in a particular directory. The first block of each of these directory
areas is the directory listing itself. The first four bytes of the directory block are an integer
giving the number of blocks in that directory area. After the block count, the remainder of
the directory block is an array of entries, each of which contains the file name, the starting
block number of the file, and the number of blocks in the file. For subdirectories, the
starting block number in the directory entry is the block number of the directory block
for the subdirectory. The second block of each directory area is a list of the free blocks in
that area.
a) (5 points) Translate this verbal description of the disk organization into diagrams
that illustrates how data is laid out on the disk.
b) (5 points) How can we tell if a given name in a directory refers to a regular file or a
subdirectory?
5
c) (5 points) This type of structure has some pretty significant limitations. List at least
five limitations on the use of files and directories in this system that are not present in the
Inferno kfs file system we discussed in class.
d) (5 points) Using a mixture of pseudo-code and C, draft a routine that will create a
file in this file system structure.
6
5) (20 points) Although never completed in the original system, there was always the
intention of supporting multiple processes. However, in the particular hardware before
you, there is no clock to generate periodic interrupts. Of course, this implies that your
multi-processing will have to be cooperative rather than preemptive. Based on the descriptions above, discuss how you would approach the scheduling and context switching
when supporting multiple processes here. Be sure to include not only what the OS does
but also how user processes interact with that functionality.