added load balancing to lec 18 notes
[kspaans/CS350] / lec18-0707.tex
1 \documentclass{article}
2 \usepackage{fullpage}
3 \usepackage{amsmath}
4 \author{Kyle Spaans}
5 \date{July 7, 2009}
6 \title{Operating Systems Lecture Notes}
7 \begin{document}
8 \maketitle 
10 \section*{Lecture 18 -- Scheduling And Device Drivers}
11 There isn't much else to talk about in terms of scheduling. It's worthwhile to
12 also think about medium- and long-term scheduling. For example, policies for
13 deciding when suspended processes should be resumed. Processes can either be
14 blocked or ready when they are suspended. How does this effect choices of when
15 and which ones should be resumed?
17 \subsection*{Multiprocessor Scheduling}
18 Normal scheduling has a ready queue where ready processes wait to be run. One
19 extreme strategy for multiprocessor scheduling is to have a single global ready
20 queue for all processors. Whenever a processor is ready for a job, it acquires
21 a lock on the ready queue, pops off a job, and releases the lock. The
22 disadvantage is that the queue is a global structure, so there is the overhead
23 associated with synchronizing concurrent access to it. Another disadvantage is
24 that processes/thread lose processor affinity. All of their associated context,
25 stored in the cache, will be lost if they are selected to run on another
26 processor. The advantage of this approach is that whenever there are processes
27 in the ready queue, and idle processor will be able to take on some work. This
28 means that the system load gets balanced evenly across all processors. 
30 The other extreme strategy is to have a ready queue for each processor in the
31 system. This gives each process/thread good affinity. However, if the load on
32 the system gets too high, processor affinity can still be lost. Processes will
33 spend too much time waiting in the queue, and it's context will get flushed or
34 otherwise overwriten from the processor's caches. The disadvantage of this
35 approach is that the load on the processors can become unbalanced. If too many
36 processes get placed in a single processor or a small group of processors
37 ready queues, then the remaining processors will sit idle if their own queues
38 are empty -- even if there may be lots of work to do in another processor's
39 queue.
41 Most modern schedulers try to strike a balance between these two extremes. The
42 keywords to think about are \textbf{processor affinity} and
43 \textbf{load balancing}.
45 \subsection*{I/O and Device Drivers}
46 Devices connect to the CPU through a bus. Each device will have a controller
47 that manages it's communication with the CPU and access to the bus. Because
48 it's how \emph{SYS161}'s LAMEbus works, we'll be thinking about a simplified
49 bus in which there is only one level of bus -- every decive, the CPU, and the
50 memory are all connected to a single bus. Data is transfered back and forth
51 across the bus between the CPU, memory, and/or device controllers. The devices
52 communicate with the CPU by generating interrupts. The device controller
53 exposes status and command registers for reading and writing to the CPU. These
54 are how the CPU finds out what the device is doing, and tell it what to do
55 next. For example, the LAMEbus timer device has second and nanosecond status
56 registers that return the current time. It also has a countdown register that,
57 after given an amount of time, will countdown and generate an interrupt after
58 the amount of time has run out.
60 \paragraph*{How does the CPU talk with devices}
61 To actually communicate with devices the CPU can either have special
62 instructions to read and write to device registers (like the coprocessor).
63 Alternatively the device registers can be mapped directly to specific physical
64 addresses. \emph{OS161} uses memory-mapped registers. Therefore to communicate
65 with devices, the kernel just need to load or store to specific addresses.
66 More specifically, each LAMEbus device is given one of 32 ``slots''. Each
67 device slot gets it's own 64KB chunk of physical memory in which to map
68 registers. Each register can be described by an offset within the slot, and a
69 size. Recall that the kernel can only reference virtual addresses, but KSEG0
70 corresponds to physical addresses in the first 0.5GB of physical memory. So if
71 a device register is at \texttt{0x1FE00004} then the kernel virtual address to
72 access that register is \texttt{0x9FE00004}. There is also KSEG1 which maps to
73 the same physical addresses, but it no cached by the hardware, which makes
74 sense when talking to devices. \emph{OS161} uses KSEG1 (starting at
75 \texttt{0xA0000000}) to access device registers. Therefore, device drivers for
76 LAMEbus devices are simply wrapper functions that map, read, and write to
77 the correct memory addresses.
79 \subsection*{DMA vs Direct Device Control}
80 If the device has a larger buffer, say the buffer for a block device (hard
81 disk), then the kernel will need to transfer more data than a single word.
82 This will, obviously, take more than a single instruction. The kernel can
83 run a simple routine to iteratively copy the data word by word. This is
84 called \textbf{program controlled I/O} and is fine except that is requires
85 that the kernel busy itself with the trivial task of copying data to devices.
86 Alternatively there is Direct Memory Access (DMA). With DMA, the CPU requests
87 for data to be transfered, and the device controller manages the transfer in or
88 out of memory. When it's finished, the CPU is signalled by an interrupt. This
89 frees the CPU to do other tasks during the (potentially lengthy) transfer. If
90 another device or the kernel needs access to the bus, the hardware needs to
91 provide bus abritration because of shared access to the resource.
93 \subsection*{What do devices look like to applications?}
94 The kernel's job is to manage devices and provide a unified interface to
95 applications: system calls. Applications see these and files. The kernel has
96 to mask any differences from the application. For exmaple, if an application
97 wants to read a single byte from a file, the disk driver will have to read a
98 512 byte block from the disk. The kernel will buffer or otherwise manage the
99 interface between the device and application such that the application doesn't
100 have to care about this particular detail of the device.
101 \end{document}