CS644 Tues, May 11, last class

Practice final coming

Finish up Memory management

Final Review

Book coverage:

Comer: Chap 1, Chap 3-7, Fig. 8.2, Chap. 9 but skip 9.2, Chap 10 but skip 10.8, Chap 11-12, Chap 13 except assembly code.

Love: Chap 1, Chap 3-5, but can skip priority calculations, Chap 6 to pg. 88, summary pg. 92, Chap. 7 to pg. 95 (i.e., just the basic ideas), 8-9, can skip “Reader-Writer” subsections, also “Ordering and Barriers”, Chap.  10 through pg. 161, then also pp. 166-171, Chap. 11, just pg. 181, Chap. 13, just pg. 235, Chap. 14, pp 251-252, pg. 260, Fig. 14.1, pg. 267, Chap. 16, pp. 279-280

See “Fixes to Love”, linked from the class web page, particularly notes on pg. 59.

Before midterm, essential background: see notes of Mar. 25 for midterm review.

· above OS: syscalls, program image, meaning of fork(), shared memory

· below OS: hardware: UART, timer, polling i/o vs interrupts

at the boundary: mechanism of Linux system call:

trap-type instruction ---CPU trap cycle--> syscall handler in OS, with sys_call_table, user eax = syscall number, args in other user registers

sys_call_table[read syscall#] = sys_read, etc., system call code “table-driven”, like devtab

trap-type instruction ---CPU trap cycle-->syscall handler ----sys_call_table---> syscall code

UNIX*: User mode vs. kernel mode: this info in the CPU CS register, crucial to which instructions are valid and what memory is accessible. If in user mode, can’t execute privileged instructions or access pages with U=0 in their PTE (i.e. all of kernel pages). in, out: swing case.

User mode to kernel mode transitions in UNIX*:

· Syscalls (use trap/exception cycle in CPU)

· other exceptions: page fault, divide-by-0, illegal instruction (use trap/exception cycle in CPU)

· interrupts (use interrupt cycle in CPU, like trap cycle except also sets IF=0, gets IRQ# from PIC)

All these cases return to user mode with iret once the kernel is finished handling them.

For Xinu, a system call is just a normal call instruction, with a normal return. An interrupt works the same way as in Linux. We don’t worry about other exceptions. No page faults can happen.

Processes

A UNIX* process has a VA space and one or more threads, also known as processes in Linux. Confusing terminology. Linux view is that some processes share a VA space.  Will try to be clear on final.

Xinu: all processes share one address space.

Process Switch: Very basic, save CPU context, restore it from process descriptor (pentry/task_struct), plus address-space switch if necessary on Linux. resched()/schedule(). See notes of Apr. 8.

UNIX*/Xinu: A process spends its life alternating between running at user level and kernel level, doing syscalls as requested by the user code. Occasionally blocks, waiting for something.

UNIX*/Xinu: Interrupts can occur anytime IF=1. The interrupt handler execution is kernel execution in “interrupt context.”

Process Context vs. Interrupt Context
When not executing an interrupt handler, the system is in “process context”, either at user level or kernel level, and in “null process” or “process 0” if no user process is runnable.

UNIX*/Xinu: Process context: current macro/currproc gives the current process id (MP: on a certain CPU) and its process descriptor is relevant. OK to block.

UNIX*/Xinu: Interrupt context: current macro/currproc tells what process is being interrupted, but the interrupt belongs to the whole system, not that process, so the interrupt handler code should not normally access the process descriptor. An exception to this rule is the preemption decision code. Not allowed to block.

Process Stacks

Xinu Stacks: only one per process in Xinu, but we can see subdivisions in it: <--I--<--K_A--<--U_A--|  where A is the process id, and <--I-- and/or <--K_A--can be dropped. Note kernel or int handler never calls user code.

UNIX* Stacks: two/thread, one for user, one for kernel/int’s called the “kernel stack”. Kernel stack is empty when user code is running, gets contents at syscall and/or interrupt time, looks like <--I--<--K_A--|  where A is the process id, and <--I-- and/or <--K_A--can be dropped.

Process state diagrams: see Comer, pg. 95, Love, pg. 28.

Kernel Mutex: guarding access to shared memory objects, or sometimes hardware or other resources.

Easy in Xinu, since UP, just disable/restore after a single enable() in system startup.  disable can be called when code already under disable: restore restores old IF state, whether 0 or 1.

Linux: Assume MP, so much harder. Spinlocks are the most basic/general facility. See notes of Apr. 22. Kernel semaphores are built on spinlocks plus shared memory and schedule() like Xinu semaphores are built on disable/restore + shared memory + resched(). A Linux kernel mutex is a new facility (not in Love), like a kernel semaphore with count = 1.  

Per-process Kernel data structures:

· Process descriptor (kernel global): pentry in Xinu, task_struct + thread_struct in Linux

· Kernel Stack: Linux: (process/thread private) between the two parts of the process descriptor in Linux (pg. 26), so the total package is 8KB. Xinu: just builds on top of the user stack.

· Process page tables: (kernel global) only in UNIX*. Originally set up for process in sys_fork().

Other kernel global data structures we know exist:

· Runqueues/q array

· Wait queues/q array

· Semaphore structs for user-level semaphores

· Semaphore structs for kernel semaphores, kernel mutexes (Linux).

· Device structs for device-driver use, devtab in Xinu.

Need for mutex: needed access to kernel global data, even just reads of such data. Local variables are process/thread-private, so don’t need mutex protection.

Device drivers and I/O System

Device-independent system calls: open, close, read, write, ...

Each device has major, minor device numbers that allow lookup of the device driver function pointers for its dv_open, dv_close, dv_read, dv_write functions.  Devtab in Xinu, indexed collection of file_operations structs in Linux.

UNIX*: each device has a “device file” that gives a device a name in the filesystem and holds the major and minor device numbers.

Device driver also has interrupt handler(s), which need registration in Linux.

Device driver output: like producer consumer but the consumer (int. handler) can’t block.

Device driver input: like producer consumer but the producer (int. handler) can’t block.