Book
Coverage: final
is open books, open notes, open solutions—yours or mine or
both.
Before
midterm:
Tan., Ch. 1, but light on history
Ch 2 to pg. 123, plus 132-148
Ch 3 to pg. 182, resource ordering
Ch 4 to pg. 210
Ch 5 to pg. 294. Note fix to pg. 280 in lecture notes.
Since
midterm.
Ch 4 to pg. 219, skip 4.4.7, read pp. 222-232, skip 233 (errors), read 234-247, 257-261, UNIX: 710-719, Win 8110823
Ch 5 to pg. 305, Sec. 5.5, pp 327-332, UNIX 723-732, Win 824-830
Ch 6 to pg. 414, 445-447, UNIX: 732-745, Win 830-841.
Security: would be good to read Ch 9, plus UNIX and Win sections, when you have time. You need an OS background to understand system security properly. As we’ve discussed, the idea of user-kernel separation is fundamental to system security. The same separation mechanisms keep the user programs apart too, each in their own virtual machine.
File Systems
pg. 743: lots of info in this picture. Note that the open file table is in the kernel global memory, while the file descriptor tables are in the process table entries. Each process has a file descriptor table in its process table entry (also see Figure 2-4, pg. 80).
A process started by the shell has fd = 0 for stdin, fd=1 for stdout, fd=2 for stderr, and then can go on to open files and get fd=3, 4, etc. These are entry #s in the file descriptor table in the process entry, pointing into the global open file table.
The i-node shown is also in memory, but has been copied in from disk, where it holds the file information we see in "ls -l" like file dates, but not the file name. It also points to the index blocks as shown (one way of the three shown, for an individual file.) The index blocks work the same logical way as page tables, pointing to the on-disk data blocks of the file (while page tables point to memory pages, of course.)Review of Homework
features
hw1—not an OS, just an interrupt-driven i/o package. Ideas of interrupt-driven i/o, device-independent i/o via dispatch through devtab, typeahead and write-behind, how to handle shut down and restart of UART output interrupts.
hw2—hw1 plus system calls for read, write, exit: first OS, with separate user and kernel code, transitions by system calls. Points to understand: mechanism of system call, which code is kernel (syswrite, sysread, sysexit, int. handlers), which user (main, crt.s, ulib.s.) The one user program has code, data, user stack while running user code. There is no scheduler yet, so the one user process can’t block on input or output. That means there still need to be busy loops in ttyread and ttywrite, not allowed in a serious OS.
hw3—multitasking kernel with non-preemptive scheduler. Each process has a process image, consisting of startup module, program code, data, and stack. In the kernel, it has a PEntry, with “saved registers”, saved at process-switch time. Now processes can block, so when one process needs to wait for i/o, another process can run.
There are no busy loops left in ttyread or ttywrite. Instead, there are calls to sleep(event) at points where the caller needs to wait. There are calls to wakeup in the interrupt handlers, signaling (by unblocking waiters) input data or output buffer-space to the blocked processes (if any.)
An interrupt handler is not allowed to block (i.e. call sleep()), but it often unblocks waiting processes, by calling wakeup(). Wakeup can be called by syscall code or interrupt-handler code. An example of syscall code calling wakeup() is in sysup of hw5's semaphore service.
Note that the a system is almost always executing in some process, or in an interrupt handler that has interrupted some process and borrowed its execution environment, including its stack. The only exceptions are the tiny moments the scheduler is actually switching processes, plus startup and shutdown. When none of the user processes can run, process 0 runs calling the scheduler over and over (and also being interrupted.)
Where’s the process’s kernel stack? It is built on top of the user stack during a system call (in both hw2 and hw3). When a process is running at user level, its kernel stack is empty even on a full OS. When a system call starts for a process, in hw3 the stack grows on top of the user stack and later shrinks again to nothing as the system call returns, leaving the user stack right back where it was before. In a real OS, the kernel stack is separate, in the kernel data area, and grows from empty to non-empty and then back to empty at system call return.
In hw3, we see the mechanism of process switch, with its saving of the old CPU state to the saved registers in the process’s PEntry, and then the restoration of the CPU state from the PEntry of the newly-chosen process.
In hw3, we also see the down-side of a non-preemptive scheduler. A CPU-bound process “hogs” the CPU until it finally does some i/o or exits.
hw5—preemptive scheduler: how timer is programmed for periodic interrupts, call to schedule from tick handler when quantum is counted down.
Our standard settings: tick every 10ms, character-transmission time 1ms (9600 baud), QUANTUM=4, so 40ms to run before preemption. Also, the output buffer holds 6 chars.
You should be able to predict behavior. For ex., suppose process A is CPU-bound and process B is i/o-bound, constantly outputting b’s. How do they run?
Suppose A starts running. It takes 4 ticks to preempt A, then process B runs, quickly fills up the output queue and blocks, so A runs again, and for the first 6 ms of that time, output drains at interrupt level while A is running, and after that a tick happens, and then three more before A is preempted again, etc.
Note that here we are seeing some
overlapping of work by A
and B: A is computing while B is outputting (via interrupts).
hw5 Implementation of semaphores
Semaphores provide mutex (and process synch) at user level, and are leveraged off of kernel mutex in their kernel implementation.
We need an array of structs, one for each semaphore, as kernel data.
One semaphore needs a count, a queue of pids of processes waiting on it, or searches through proctab as needed, and a used-flag. In addition, it needs a flag in PEntry to mark a process “appointed” by up to run as the one and only process for that up-instance, or a modification of wakeup to specify special wakeup-one-process behavior instead of the classic UNIX wakeup-everything waiting on an event.
hw4: x86 paging. KPT0 is at VA 52000 on the SAPC, and consists of 1024 4-byte PTEs, each of format given on pg. 818.
Thus the PTE for page 0 is at 0x52000,
page 1 is at 0x52004
page 2 is at 0x52008
...
page 0x50 is at 0x52000 + 4*0x50 = 0x52140,
and this PTE maps VAs 0x50xxx, i.e., 0x50000 through 0x50fff.
In the PTE, you should be able to work with the P, A, D, U, and W bits.
The whole paging system involves the page directory pointing to 1024 PTs, each pointing to 1024 pages, for a total of 1M pages, each 4K, so 4GB = 32-bit addr. space.
Process switch: reload CR3, the CPU register holding the PD location. Causes TLB flush, its biggest cost.
Topics—best to reread lecture notes.