lec 17 notes done
[kspaans/CS350] / lec17-0702.tex
index 5f404d5..c3dd492 100644 (file)
@@ -35,7 +35,18 @@ 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
+fault handler! We need to make sure that the TLB is properly filled before
+trying to touch any memory when inside of the page fault handler. A similar
+example is when we find a segment in the ELF file that is marked as read-only.
+If the page is marked as read-only before we start copying bits into it,
+\emph{bad} things will happen.
+
+A tip for avoiding this is to remember that kernel virtual addresses
+(\texttt{0x80000000} and up) map directly to physical addresses. They cannot
+generate page faults. Therefore we can substitute kernel vritual addresses for
+any userspace virtual address without having to worry about generating more
+page faults. (We will get a ``bus error'' if we touch invalid kernel virtual
+addresses.)
 
 \subsection*{What's a Scheduler?}
 The scheduler is a kernel program (subsystem?) that decides which processes get
@@ -43,68 +54,25 @@ 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.
+waiting for I/O to complete. That is to say, it schedules a processes CPU
+bursts.
 
 \subsection*{Preemptive and Non-preemptive Scheduling Algorithms}
+First-Come First-Served, Round-Robin, Shortest Job First, Shortest Remaining
+Time First, Highest Respone Ratio Next. There is a concept of the ``ready
+queue''. Processes get put in the queue as they are created or become
+unblocked. There is also a wait queue where blocked processes go. Some
+algorithms aim to lower average time spent in the wait queue (SJF). For this
+to be practical however, the lengths of the processes CPU bursts would have to
+be predicted. This can be done by taking an exponential average of previous
+burst lengths for example. Note that starvation can happen with SJF if there is
+a long job waiting, but new and shorter jobs keep appearing. HRRN will prevent
+this since each process's status gets updated as time goes on, so eventually
+the long job will get selected (waiting time is accounted for in the ratio).
 
-\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.
+Another idea is to prioritize processes. This can help schedule more important
+ones better. This can also lead to starvation though. To avoid this the kernel
+should have a way of modifying the priority of processes so that ones which
+wait too long will have a chance to run. (Think of the UNIX \texttt{nice}
+program.)
 \end{document}