lecture 17 getting more or less done
authorKyle Spaans <kspaans@student.math.uwaterloo.ca>
Sat, 4 Jul 2009 05:01:17 +0000 (01:01 -0400)
committerKyle Spaans <kspaans@student.math.uwaterloo.ca>
Sat, 4 Jul 2009 05:01:17 +0000 (01:01 -0400)
lec17-0702.tex [new file with mode: 0644]

diff --git a/lec17-0702.tex b/lec17-0702.tex
new file mode 100644 (file)
index 0000000..5f404d5
--- /dev/null
@@ -0,0 +1,110 @@
+\documentclass{article}
+\usepackage{fullpage}
+\usepackage{amsmath}
+\author{Kyle Spaans}
+\date{July 2, 2009}
+\title{Operating Systems Lecture Notes}
+\begin{document}
+\maketitle 
+
+\section*{Lecture 17 -- Scheduling}
+First, some notes about A3. At boot the kernel code and data are loaded into
+the lowest portion of memory (recall that \texttt{0x80000000} gets mapped
+directly to \texttt{0x00000000}). \texttt{Runprogram()} reads the ELF file to
+decide how big the program's segments are and what will go in them. When doing
+this it immediately allocates frames of memory and adjusts the thread's address
+space struct accordingly. \texttt{Load\_elf()} will then fill these allocated
+segments accordingly from the contents of the ELF file. Page faults will occur
+immediately as \texttt{load\_elf()} tries to write to the fresh pages in
+memory. The kernel takes the data from the thread's address space structure and
+fills the TLB.
+
+In A3 we will be implementing dynamic loading of pages. This means that memory
+will not actually be allocated until that page is used by the program. The
+point is that our OS should let us ``run'' programs that have huge ELF files
+(larger than the amount of physical memory \emph{SYS161} has) that, if loaded
+directly into memory when run, would cause the system to run out of memory.
+Since the programs will only touch a small number of pages within their address
+spaces, they should be able to work. There are tests specifically for this. We
+will also implement a page freer so that \emph{OS161} won't crash all the time.
+It should be able to reclaim pages that have been entirely freed (E.G. when a
+thread terminates). The \textt{kfree()} already handles allocation and freeing
+within subpages, but once a whole page it touched, the kernel does not try to
+reclaim it. It will be a \textbf{physical memory manager}.
+
+Some gotchas to watch out for! Page faults should happen as segments get filled
+with data and code. However, we will be doing this while inside of the
+interrupt handler. Page faults should not be generated when inside of the page
+fault handler! We need to make sure
+
+\subsection*{What's a Scheduler?}
+The scheduler is a kernel program (subsystem?) that decides which processes get
+to run next whenever a thread blocks, yields, exits, or gets pre-empted (and
+has used up it's quantum, if the schedules defines such a thing). We say that
+programs divide their life between CPU bursts and I/O bursts. CPU bursts
+involve computation, whereas I/O Bursts involve the process being blocked
+waiting for I/O to complete.
+
+\subsection*{Preemptive and Non-preemptive Scheduling Algorithms}
+
+\paragraph*{Prefetching}
+We can further hide latency by trying to guess which pages will be requested
+next. If the kernel can guess correctly, then the process will not incurr
+page faults. If the kernel guesses incorrectly, then not only will processes
+page fault, but it's possible that the kernel evicted a useful page in order
+to prefetch the new one. Prefetching implies that we're no longer doing demand
+paging. A simple but common prefetching technique is ``sequential readahead''.
+When page $x$ is requested, page $x + 1$ will probably be needed as well, so
+prefetch it.
+
+\paragraph*{Choice of Page Size}
+Some hardware lets you select the page size that you want. There are some
+tradeoffs between using larger or smaller pages. Larges pagesize means smaller
+page table, larger TLB footprint (amount of memory covered by entries in the
+TLB which means fewer TLB misses), and more efficient I/O. More efficient
+because there will be fewer pages that need to be swapped less often, and
+because reading a larger file from disk does not necessarily take a
+linearly-proportional amount of time. However the downsides are that larger
+page can have more irrelevant information in it and more internal
+fragmentation (proportional to the size of the page).
+
+\paragraph*{Application Behaviour: Belady's Anomaly}
+The anomaly is where a page replacement policy performs worse when given more
+memory to work with. This can be seen in FIFO, with a bad enough reference
+string. It turns out that there are some strategies which we can guarantee
+will perform no worse when given more memory. These are called \textbf{stack
+policies}. We define a stack policy as one where for all reference strings,
+all memory sizes (amount of physical memory) $m$, and at any time $t$ then
+the number of pages occupying memory of size $m$ is a subset of those occupying
+an amount of memory $m + 1$. To be more precise: $B(m,t) \subseteq B(m + 1,t)$.
+This means that the policy enforces a total ordering on all pages in physical
+memory. Total ordering means every page is given a specific ordering. Therefore
+if this doesn't change when we add memory, then the page replacement policy
+cannot possibly do any \emph{worse} with more memory. How can we decide if a
+page replacement algorithm is a stack policy? First, we are given that LRU is
+one such algorithm. But when considering others, a sufficient (but not
+necessary) condition is the ordering property. As long as things aren't changed
+if memory is added. Consider FIFO, if memory is added, the order of elements in
+$B(m,t)$ can change. Similarly, the clock algorithm is not a stack policy.
+
+\paragraph*{How much memory does a process use?}
+The \texttt{ps} command in Linux can give us this information. How many of a
+processes pages are in memory? This is called the \texttt{Resident Set Size}.
+The total number of pages comprising the process can be called the
+\texttt{Virtual Space Size}. There is a notion of the \texttt{working set} of
+a process. This is the set of pages that are used most frequently. Admittedly
+this is a slippery concept, and so hard to take advantage of fully in practice.
+If the OS can keep the working set of a process in memory, then that process
+should incurr very few page faults. These properties can be loosely used to
+prioritize pages for eviction. To find the ideal working set of a process, the
+graph of page faults per unit time against the number of pages used.
+
+\paragraph*{Thrashing}
+When the number of page faults are too high, lots of swapping to and from disk
+will happen. This is called \textbf{thrasing}. When we are trying to increase
+the multiprogramming level of the OS, if we increase it too much, there will
+be contention on resources and probably thrashing. If the level is too low,
+resources will be left idle. To try and speedup the recovery of a system that
+is thrasing, processes can be killed (very mean) or they can be suspended.
+Suspension just means moving all of the processes' pages to disk.
+\end{document}