Section notes for CS162 Section #8, March 19, 2002 Barbara Hohlt ----------------------------------------------------------------------------- PROJECT 2 FAQs ----------------------------------------------------------------------------- - LotteryScheduler should require minimal changes to existing code - System call is invoked when MIPS simulator does 'syscall' instruction - Causes instruction processing loop to throw 'MipsException' - When caught, calls MipsException.handle - handle() writes 'cause' into machine register - Causes 'Machine.processor().exceptionHandler' to be invoked - This is set by UserKernel constructor to be UserKernel.exceptionHandler - This gets current process (casts current KThread to UThread and extracts process field) - Calls process.handleException(cause) - Illegal operations do NOT include anything "illegal" done while calling a system call -> just return -1 from system call instead - write/read should return -1 if cannot read/write complete memory buffer provided by user, but number of bytes transferred if memory is OK but filesystem is not - Use Lib.random() to get an int for LotteryScheduler: Will be deterministic - Don't introduce overflow bugs in your code, but OK to assume that an 'int' is good enough to do the lottery with ----------------------------------------------------------------------------- PROTECTION ----------------------------------------------------------------------------- - The motivation for protection is multiprogramming. The goal is to keep user programs from corrupting the OS or each other. - Can be implemented in SW or HW - SW support via strong typing or software fault isolation. - HW support requires both - address translation ( base and limit registers, ... ) - dual mode operation: kernel vs user mode - mode bit - priviledged instructions (ie system services) ----------------------------------------------------------------------------- TYPES OF ADDRESS TRANSLATION ----------------------------------------------------------------------------- - Base and Bounds - Segmentation - Paging ----------------------------------------------------------------------------- SEGMENTATION ----------------------------------------------------------------------------- - Segments are variable length contiguous regions of memory. Usally associated with the logical partition of virtual address space (ie code, data, stack) - Segment table has all segment table entries for one process. - Each segment table entry has physical segment number, bounds, and protection bits - Virtual address: - the virtual segment number indexes into the segment table - HW provides STBR, segment table, checking protection bits ----------------------------------------------------------------------------- PAGING ----------------------------------------------------------------------------- - Pages are fixed length small regions of memory. Usually about 4K in size. - Page table has all page table entries for one process - Each page table entry has physical page number and protection bits - Virtual address: - the virtual page number indexes into the page table - HW provides PTBR, PT size, page table, checking protection bits - Segmentation vs. paging - Fixed page size is the key to paging over segmentation - Solves segmentation problem: If we need to allocate space for a new page, any empty page frame will do - A large object does not need to be contiguous - Cons: - If page size too large, get internal fragmentation (object that needs one byte more than size of page takes 2 pages) - If page size too small, too many page table entries - How big are single-level page tables? - Say we have 32-bit address with 4Kb pages. How many page table entries are there? - Answer: 20 bits of page address, so 2^20 or 1024*1024 entries - How big is a page table entry? - Minimum size is enough to span physical memory. So with 512 MBytes in your machine, how many bits is the physical page frame number in the page table entry? - Answer: 29 bits of physical address space (512 MBytes), divided into 4 KB pages -> 12 bits of offset, 17 bits of page address So, need 17 bits to store physical page frame number - Problem is that we don't want to hard-wire the amount of physical memory the machine might have! - In general, on a 32-bit machine can have 32-bit physical addresses. So, with 4KB pages need 12 bits for offset and 20 bits for page address, just like virtual addresses - So how big is the page table then? 1024 * 1024 * 20 bits = 2.5 MBytes, all in physical memory!! - AND THAT'S FOR EACH PROCESS! - Note also that each page table entry also contains some accounting and status bits, for example, indicating whether a given page is read-only, whether it has been modified, etc. So on a 32-bit machine a page table entry tends to be 32 bits wide, which means 1024 * 1024 * 32 = 4 MBytes. ----------------------------------------------------------------------------- MULTI-LEVEL PAGE TABLES ----------------------------------------------------------------------------- - Multilevel paging - Solves the problem by using a hierarchy of page tables (Show picture of tree of page tables) - Since at any given time a process is only using a small portion of its address space, only need page table entries corresponding to what's actually in use - Note that later on we will talk about DEMAND PAGING: Moving memory to and from disk - This is going to allow us to allocate more virtual memory than we actually have physical RAM - With multilevel page tables, the PAGE TABLES can be PAGED - meaning that if the process has a portion of its address space which hasn't been used in a long time, those page tables (and the associated pages) go out to disk - This is project phase 3, so pay attention :-) - Multilevel paging on the x86 - Uses two-level page tables - Virtual address is divided into 3 components: 10 bits (31 .. 22): Page directory index 10 bits (21 .. 12): Page table index 10 bits (11 .. 0): Offset - Example: Virtual address 0x13a49F01 = 0001001110 | 1001001001 | 111100000001 in binary 0x04e | 0x249 | 0xF01 pgdirind. | pgtblind. | offset - First, use page dir index as index into "page directory" Physical base address of the page directory is stored in a special register (called "CR3") on the x86. It is always page-aligned, so the base address might be 0x0001c000. How many entries in the page directory? Well 10 bits of index, so 2^10 entries * 4 bytes each entry = 4Kb (One page!) At offset 0x04e in the page directory we find the physical address of page table, e.g.,: 0x000a2000. (Note that the page table is also page-aligned and holds just one page.) - We use the "page table index" as an index into this second-level table. At index 0x249 into the page table at 0xa2000 we find the physical page number of the address we are looking for, e.g., 0x0341b000. We add to this the offset (0xf01) to get the final physical address: 0x0341bf01. - New twist: What if the address of the page table is a VIRTUAL ADDRESS, which means we have to go through another step of translation to look up its physical address! - This means that to simply look up one virtual address, we may have to do a SECOND virtual address translation - Can this process go on forever? What if the SECOND translation above turns into a THIRD translation, and so forth? Pretty complex! - Generally the page directory entries contain PHYSICAL addresses for page tables. However, the least significant bit of the entry indicates whether the page table is "present" or not. If not present, then the entry would contain an OS-specific pointer (such as a disk block address) used to record where the page table is stored on disk. In this way, page directory entries always use PHYSICAL addresses, but the page tables can still be swapped out. - Note that the page directory is always resident in physical memory, meaning that each process has 1 page always "pinned"