diff options
Diffstat (limited to 'web/l3.html')
| -rw-r--r-- | web/l3.html | 334 |
1 files changed, 0 insertions, 334 deletions
diff --git a/web/l3.html b/web/l3.html deleted file mode 100644 index 7d6ca0d..0000000 --- a/web/l3.html +++ /dev/null @@ -1,334 +0,0 @@ -<title>L3</title> -<html> -<head> -</head> -<body> - -<h1>Operating system organizaton</h1> - -<p>Required reading: Exokernel paper. - -<h2>Intro: virtualizing</h2> - -<p>One way to think about an operating system interface is that it -extends the hardware instructions with a set of "instructions" that -are implemented in software. These instructions are invoked using a -system call instruction (int on the x86). In this view, a task of the -operating system is to provide each application with a <i>virtual</i> -version of the interface; that is, it provides each application with a -virtual computer. - -<p>One of the challenges in an operating system is multiplexing the -physical resources between the potentially many virtual computers. -What makes the multiplexing typically complicated is an additional -constraint: isolate the virtual computers well from each other. That -is, -<ul> -<li> stores shouldn't be able to overwrite other apps's data -<li> jmp shouldn't be able to enter another application -<li> one virtual computer cannot hog the processor -</ul> - -<p>In this lecture, we will explore at a high-level how to build -virtual computer that meet these goals. In the rest of the term we -work out the details. - -<h2>Virtual processors</h2> - -<p>To give each application its own set of virtual processor, we need -to virtualize the physical processors. One way to do is to multiplex -the physical processor over time: the operating system runs one -application for a while, then runs another application for while, etc. -We can implement this solution as follows: when an application has run -for its share of the processor, unload the state of the phyical -processor, save that state to be able to resume the application later, -load in the state for the next application, and resume it. - -<p>What needs to be saved and restored? That depends on the -processor, but for the x86: -<ul> -<li>IP -<li>SP -<li>The other processor registers (eax, etc.) -</ul> - -<p>To enforce that a virtual processor doesn't keep a processor, the -operating system can arrange for a periodic interrupt, and switch the -processor in the interrupt routine. - -<p>To separate the memories of the applications, we may also need to save -and restore the registers that define the (virtual) memory of the -application (e.g., segment and MMU registers on the x86), which is -explained next. - - - -<h2>Separating memories</h2> - -<p>Approach to separating memories: -<ul> -<li>Force programs to be written in high-level, type-safe language -<li>Enforce separation using hardware support -</ul> -The approaches can be combined. - -<p>Lets assume unlimited physical memory for a little while. We can -enforce separation then as follows: -<ul> - -<li>Put device (memory management unit) between processor and memory, - which checks each memory access against a set of domain registers. - (The domain registers are like segment registers on the x86, except - there is no computation to compute an address.) -<li>The domain register specifies a range of addresses that the - processor is allow to access. -<li>When switching applications, switch domain registers. -</ul> -Why does this work? load/stores/jmps cannot touch/enter other -application's domains. - -<p>To allow for controled sharing and separation with an application, -extend domain registers with protectioin bits: read (R), write (W), -execute-only (X). - -<p>How to protect the domain registers? Extend the protection bits -with a kernel-only one. When in kernel-mode, processor can change -domain registers. As we will see in lecture 4, x86 stores the U/K -information in CPL (current privilege level) in CS segment -register. - -<p>To change from user to kernel, extend the hardware with special -instructions for entering a "supervisor" or "system" call, and -returning from it. On x86, int and reti. The int instruction takes as -argument the system call number. We can then think of the kernel -interface as the set of "instructions" that augment the instructions -implemented in hardware. - -<h2>Memory management</h2> - -<p>We assumed unlimited physical memory and big addresses. In -practice, operating system must support creating, shrinking, and -growing of domains, while still allowing the addresses of an -application to be contiguous (for programming convenience). What if -we want to grow the domain of application 1 but the memory right below -and above it is in use by application 2? - -<p>How? Virtual addresses and spaces. Virtualize addresses and let -the kernel control the mapping from virtual to physical. - -<p> Address spaces provide each application with the ideas that it has -a complete memory for itself. All the addresses it issues are its -addresses (e.g., each application has an address 0). - -<li> How do you give each application its own address space? -<ul> - <li> MMU translates <i>virtual</i> address to <i>physical</i> - addresses using a translation table - <li> Implementation approaches for translation table: -<ol> - -<li> for each virtual address store physical address, too costly. - -<li> translate a set of contiguous virtual addresses at a time using -segments (segment #, base address, length) - -<li> translate a fixed-size set of address (page) at a time using a -page map (page # -> block #) (draw hardware page table picture). -Datastructures for page map: array, n-level tree, superpages, etc. - -</ol> -<br>Some processor have both 2+3: x86! (see lecture 4) -</ul> - -<li> What if two applications want to share real memory? Map the pages -into multiple address spaces and have protection bits per page. - -<li> How do you give an application access to a memory-mapped-IO -device? Map the physical address for the device into the applications -address space. - -<li> How do you get off the ground? -<ul> - <li> when computer starts, MMU is disabled. - <li> computer starts in kernel mode, with no - translation (i.e., virtual address 0 is physical address 0, and - so on) - <li> kernel program sets up MMU to translate kernel address to physical - address. often kernel virtual address translates to physical adress 0. - <li> enable MMU -<br><p>Lab 2 explores this topic in detail. -</ul> - -<h2>Operating system organizations</h2> - -<p>A central theme in operating system design is how to organize the -operating system. It is helpful to define a couple of terms: -<ul> - -<li>Kernel: the program that runs in kernel mode, in a kernel -address space. - -<li>Library: code against which application link (e.g., libc). - -<li>Application: code that runs in a user-level address space. - -<li>Operating system: kernel plus all user-level system code (e.g., -servers, libraries, etc.) - -</ul> - -<p>Example: trace a call to printf made by an application. - -<p>There are roughly 4 operating system designs: -<ul> - -<li>Monolithic design. The OS interface is the kernel interface (i.e., -the complete operating systems runs in kernel mode). This has limited -flexibility (other than downloadable kernel modules) and doesn't fault -isolate individual OS modules (e.g., the file system and process -module are both in the kernel address space). xv6 has this -organization. - -<li>Microkernl design. The kernel interface provides a minimal set of -abstractions (e.g., virtual memory, IPC, and threads), and the rest of -the operating system is implemented by user applications (often called -servers). - -<li>Virtual machine design. The kernel implements a virtual machine -monitor. The monitor multiplexes multiple virtual machines, which -each provide as the kernel programming interface the machine platform -(the instruction set, devices, etc.). Each virtual machine runs its -own, perhaps simple, operating system. - -<li>Exokernel design. Only used in this class and discussed below. - -</ul> - -<p>Although monolithic operating systems are the dominant operating -system architecture for desktop and server machines, it is worthwhile -to consider alternative architectures, even it is just to understand -operating systems better. This lecture looks at exokernels, because -that is what you will building in the lab. xv6 is organized as a -monolithic system, and we will study in the next lectures. Later in -the term we will read papers about microkernel and virtual machine -operating systems. - -<h2>Exokernels</h2> - -<p>The exokernel architecture takes an end-to-end approach to -operating system design. In this design, the kernel just securely -multiplexes physical resources; any programmer can decide what the -operating system interface and its implementation are for his -application. One would expect a couple of popular APIs (e.g., UNIX) -that most applications will link against, but a programmer is always -free to replace that API, partially or completely. (Draw picture of -JOS.) - -<p>Compare UNIX interface (<a href="v6.c">v6</a> or <a -href="os10.h">OSX</a>) with the JOS exokernel-like interface: -<pre> -enum -{ - SYS_cputs = 0, - SYS_cgetc, - SYS_getenvid, - SYS_env_destroy, - SYS_page_alloc, - SYS_page_map, - SYS_page_unmap, - SYS_exofork, - SYS_env_set_status, - SYS_env_set_trapframe, - SYS_env_set_pgfault_upcall, - SYS_yield, - SYS_ipc_try_send, - SYS_ipc_recv, -}; -</pre> - -<p>To illustrate the differences between these interfaces in more -detail consider implementing the following: -<ul> - -<li>User-level thread package that deals well with blocking system -calls, page faults, etc. - -<li>High-performance web server performing optimizations across module -boundaries (e.g., file system and network stack). - -</ul> - -<p>How well can each kernel interface implement the above examples? -(Start with UNIX interface and see where you run into problems.) (The -JOS kernel interface is not flexible enough: for example, -<i>ipc_receive</i> is blocking.) - -<h2>Exokernel paper discussion</h2> - - -<p>The central challenge in an exokernel design it to provide -extensibility, but provide fault isolation. This challenge breaks -down into three problems: - -<ul> - -<li>tracking owner ship of resources; - -<li>ensuring fault isolation between applications; - -<li>revoking access to resources. - -</ul> - -<ul> - -<li>How is physical memory multiplexed? Kernel tracks for each -physical page who has it. - -<li>How is the processor multiplexed? Time slices. - -<li>How is the network multiplexed? Packet filters. - -<li>What is the plan for revoking resources? -<ul> - -<li>Expose information so that application can do the right thing. - -<li>Ask applications politely to release resources of a given type. - -<li>Ask applications with force to release resources - -</ul> - -<li>What is an environment? The processor environment: it stores -sufficient information to deliver events to applications: exception -context, interrupt context, protected entry context, and addressing -context. This structure is processor specific. - -<li>How does on implement a minimal protected control transfer on the -x86? Lab 4's approach to IPC has some short comings: what are they? -(It is essentially a polling-based solution, and the one you implement -is unfair.) What is a better way? Set up a specific handler to be -called when an environment wants to call this environment. How does -this impact scheduling of environments? (i.e., give up time slice or -not?) - -<li>How does one dispatch exceptions (e.g., page fault) to user space -on the x86? Give each environment a separate exception stack in user -space, and propagate exceptions on that stack. See page-fault handling -in lab 4. - -<li>How does on implement processes in user space? The thread part of -a process is easy. The difficult part it to perform the copy of the -address space efficiently; one would like to share memory between -parent and child. This property can be achieved using copy-on-write. -The child should, however, have its own exception stack. Again, -see lab 4. <i>sfork</i> is a trivial extension of user-level <i>fork</i>. - -<li>What are the examples of extensibility in this paper? (RPC system -in which server saves and restores registers, different page table, -and stride scheduler.) - -</ul> - -</body> |