CS444 Class 18
Handout: debuglog
for hw3
Note uprog.sh in hw2soln, does input and output
Also uprog.sh in hw3, does only input, for main testing needed.
You can use hw2soln’s when you test reading.
New system call for
hw3: sleep(int ms)
A new system call, so give it a number. Also a new waitcode. You can use tsleep to block a process, but it isn’t reasonable to use the broadcast twakeup here, so just set the process status when the time is up, or implement wakeup_one(int pid). You need the pid argument in wakeup_one() because this will be called from the tick handler, which has figured out the pid that needs waking up when its sleep is over.
The system discovers the time is up in the tick handler. Unless you are implementing a preemptive scheduler (for two-person
project), you don’t want to call schedule here, because a non-preemptive
scheduler never process-switches in an interrupt handler.
Memory
Management
Read Chap. 3 to pg. 194, esp. 189-194, then 3.3.3, TLBs, 3.3.4 multilevel page tables,
3.4 on page replacement algorithms, skipping 3.4.8,
3.6 through pg. 232, Linux pp. 758-762
Sec 3.4.6: only need
to read the first two paragraphs
Skip 3.4.7
Add pg. 887 x86 PTE
bits
Sec. 10.4.4 Paging in
Linux, to end of pg. 770, so you know PFRA is a clock-like algorithm that uses
the page reference bit.
Examples: SAPC, MSDOS
Both the user code and OS code sit in the same memory space, and each can see the other. The data is also in this space and mutually accessible, and must be writable (the code might be in ROM, and thus protected from write.) The user code can accidentally or on purpose corrupt the OS data. Thus the system is seriously insecure.
What do we need in order to get the needed user-OS separation? We need help from the hardware and software that uses it properly.
More specifically, we need help from memory management hardware (the MMU) to restrict memory access based on user vs kernel execution. That means we need to have the CPU keep track of whether it’s executing user or kernel code, and make sure the transition between the two is very carefully handled.
User vs. Kernel Mode Execution
All CPUs used for serious OS’s have at least two modes of execution, for user and kernel. In fact, the x86 has 4 “rings” for this, but only two of them are in use by UNIX or Win2K. Thus we will stick to the simple picture of two levels, user and kernel. In the x86, the current execution mode (ring number) is stored in the CS (code segment descriptor) register of the CPU.
User-Kernel Transitions
We have already studied the mechanism of system calls, and saw how careful they are to transfer only a minimal amount of information from the user execution environment to the kernel, just a syscall number and the arguments. The whole syscall execution looks like the execution of a single instruction in the user code, the syscall trap instruction.
Interrupts during user execution also make the user-kernel mode transition. We have seen that they utilize the same basic CPU trap cycle as the system calls, with the additional trick of turning off interrupts, and some way of getting a device identifier. They can’t even be detected by user code unless it does high-precision timekeeping.
The MMU (part of the CPU) Picture, pg. 189
The MMU needs to know which addresses are user, which are kernel, as well as the current CPU mode, user or kernel. Then when it is handling a certain address, it can detect a user-mode access to kernel address, and make it fail. We will see how this works.
The MMU is another helper to the CPU proper, but it is not like the other helper, the PIC, which we called the “secretary to the CPU,” because it remembered things and organized work for the CPU. The MMU just takes orders, more like a telephone for the boss. Type in a number and a phone places a particular call. Similarly, the CPU asks the MMU for the data at a certain address.
A MMU is needed to support the concept of an address space, discussed in Tanenbaum starting on pg. 179. It is possible to support address spaces without using paging, but we will not study that case. It is covered on pp. 180 (last paragraph)-181.
Def, pg. 180: an address space is the set of addresses that a process can use to address memory. Each process has its own address space. This holds for UNIX/Linux and Windows.
For example, on 32-bit Linux, processes have 3GB-sized address spaces going from A = 0 to 3G-1 = 0xbfffffff. Two such processes can each use address 0x100234 and read different values, because these are two different address spaces.
In fact not all addresses are readable: some will cause an exception on access because no memory has been allocated there yet.
Swapping: Copying program-image data to/from memory into special areas on disk is called swapping. In current systems, this happens normally only to idle processes (multiple minutes idle.) If a system is running two many processes to fit the non-idle ones all in memory (at least their most important pages), it is in trouble (overloaded). The process swap rate can be used as a danger signal. Swapping whole programs back and forth to disk is discussed in Section 3.2.2, but we don’t need a lot of detail on this.
Paging (starting pg. 189): This is the main method of memory management for systems operating within their normal range (not overloaded.) If a process can be provided with memory under its most commonly-used pages, and extra memory as needed for less-commonly used pages, it can run well and share the memory efficiently with other processes using paging.
Under paging, the memory is divided up into equal-sized blocks called pages, typically 4K (x86) or 8K (Sparc) in size. The VA (virtual address) space for each process is the memory it sees and works with, i.e., its address space. It is quietly divided into pages—the page division marks are not apparent to programmers. If the program extends even one byte into a page, the whole page is used (in theory, but if no reference is made to this one byte, it may never be given real memory.) Thus we don’t want pages to be too big, or too small, either, because each page needs to be kept track of, an overhead.
The physical memory is divided up into the same size blocks, called page frames. All the page frames are exactly the same in terms of memory resources. The idea of paging is that any page frame can be used as memory under any virtual page. A page table (PT for short) tells which page frame is assigned to each page of (some part of) a VA space.
Parts of the CPU, pg. 189 pic
Here we see that the MMU is part of the CPU, specifically the part closer to the bus, which makes sense since the bus carries the addresses out to memory to specify which RAM chip is accessed (the physical location.) The upper part of the CPU contains the ALU, the arithmetic-logical unit, i.e. the brains of the CPU. This part works in VAs. You could add the registers to the upper box: these all contain VAs if they contain addresses.
The PC (x86 EIP) is a VA, and specifies which next instruction to pull in from memory. A read request by VA is generated in the upper CPU and passed to the MMU, which maps it to a PA (with the help of a page table), and the PA specifies the exact physical location.
Next: look at examples on pg. 190 and 191.