lec 18 notes done
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Tue, 7 Jul 2009 23:55:36 +0000 (19:55 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Tue, 7 Jul 2009 23:55:36 +0000 (19:55 -0400)
lec18-0707.tex [new file with mode: 0644]

diff --git a/lec18-0707.tex b/lec18-0707.tex
new file mode 100644 (file)
index 0000000..bd7ab54
--- /dev/null
@@ -0,0 +1,93 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{July 7, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 18 -- Scheduling And Device Drivers}
+There isn't much else to talk about in terms of scheduling. It's worthwhile to
+also think about medium- and long-term scheduling. For example, policies for
+deciding when suspended processes should be resumed. Processes can either be
+blocked or ready when they are suspended. How does this effect choices of when
+and which ones should be resumed?
+
+\subsection*{Multiprocessor Scheduling}
+Normal scheduling has a ready queue where ready processes wait to be run. One
+extreme strategy for multiprocessor scheduling is to have a single global ready
+queue for all processors. Whenever a processor is ready for a job, it acquires
+a lock on the ready queue, pops off a job, and releases the lock. The
+disadvantage is that the queue is a global structure, so there is the overhead
+associated with synchronizing concurrent access to it. Another disadvantage is
+that processes/thread lose processor affinity. All of their associated context,
+stored in the cache, will be lost if they are selected to run on another
+processor.
+
+The other extreme strategy is to have a ready queue for each processor in the
+system. This gives each process/thread good affinity. However, if the load on
+the system gets too high, processor affinity can still be lost. Processes will
+spend too much time waiting in the queue, and it's context will get flushed or
+otherwise overwriten from the processor's caches.
+
+Most modern schedulers try to strike a balance between these two extremes. The
+keywords to think about are \textbf{affinity} and \textbf{something else}...
+
+\subsection*{I/O and Device Drivers}
+Devices connect to the CPU through a bus. Each device will have a controller
+that manages it's communication with the CPU and access to the bus. Because
+it's how \emph{SYS161}'s LAMEbus works, we'll be thinking about a simplified
+bus in which there is only one level of bus -- every decive, the CPU, and the
+memory are all connected to a single bus. Data is transfered back and forth
+across the bus between the CPU, memory, and/or device controllers. The devices
+communicate with the CPU by generating interrupts. The device controller
+exposes status and command registers for reading and writing to the CPU. These
+are how the CPU finds out what the device is doing, and tell it what to do
+next. For example, the LAMEbus timer device has second and nanosecond status
+registers that return the current time. It also has a countdown register that,
+after given an amount of time, will countdown and generate an interrupt after
+the amount of time has run out.
+
+\paragraph*{How does the CPU talk with devices}
+To actually communicate with devices the CPU can either have special
+instructions to read and write to device registers (like the coprocessor).
+Alternatively the device registers can be mapped directly to specific physical
+addresses. \emph{OS161} uses memory-mapped registers. Therefore to communicate
+with devices, the kernel just need to load or store to specific addresses.
+More specifically, each LAMEbus device is given one of 32 ``slots''. Each
+device slot gets it's own 64KB chunk of physical memory in which to map
+registers. Each register can be described by an offset within the slot, and a
+size. Recall that the kernel can only reference virtual addresses, but KSEG0
+corresponds to physical addresses in the first 0.5GB of physical memory. So if
+a device register is at \texttt{0x1FE00004} then the kernel virtual address to
+access that register is \texttt{0x9FE00004}. There is also KSEG1 which maps to
+the same physical addresses, but it no cached by the hardware, which makes
+sense when talking to devices. \emph{OS161} uses KSEG1 (starting at
+\texttt{0xA0000000}) to access device registers. Therefore, device drivers for
+LAMEbus devices are simply wrapper functions that map, read, and write to
+the correct memory addresses.
+
+\subsection*{DMA vs Direct Device Control}
+If the device has a larger buffer, say the buffer for a block device (hard
+disk), then the kernel will need to transfer more data than a single word.
+This will, obviously, take more than a single instruction. The kernel can
+run a simple routine to iteratively copy the data word by word. This is
+called \textbf{program controlled I/O} and is fine except that is requires
+that the kernel busy itself with the trivial task of copying data to devices.
+Alternatively there is Direct Memory Access (DMA). With DMA, the CPU requests
+for data to be transfered, and the device controller manages the transfer in or
+out of memory. When it's finished, the CPU is signalled by an interrupt. This
+frees the CPU to do other tasks during the (potentially lengthy) transfer. If
+another device or the kernel needs access to the bus, the hardware needs to
+provide bus abritration because of shared access to the resource.
+
+\subsection*{What do devices look like to applications?}
+The kernel's job is to manage devices and provide a unified interface to
+applications: system calls. Applications see these and files. The kernel has
+to mask any differences from the application. For exmaple, if an application
+wants to read a single byte from a file, the disk driver will have to read a
+512 byte block from the disk. The kernel will buffer or otherwise manage the
+interface between the device and application such that the application doesn't
+have to care about this particular detail of the device.
+\end{document}