read the xv6 book: “Appendix A, PC hardware” and “Appendix B, The boot loader” start on the booting exercise learn to work with systems software: reading code/manuals, debugging, etc. xv6 (exercises): a Unix-style OS on x86 JOS (labs): an exokernel-style OS on x86 lectures: basic/more modern concepts sections: help you with exercises/labs final exam: open book/notes/laptop; no Internet or other communication CPU, Memory, and I/O CPU interprets instructions: IP (Instruction Pointer) to memory memory stores instructions and data I/O to external world: memory-mapped I/O & port I/O in this class we use QEMU to emulate the PC concepts apply to non-x86 architectures how does printing “hello” work on this PC? example: a tiny hello “kernel” (tar and source code) VGA text buffer at physical memory address 0xb8000 one byte for character, one byte for attribute memory-mapped I/O: 0xb8000 + (row * 80 + column) * 2;
talk to devices through memory address space will see more examples in later labs perhaps the lowest-level “hello world” you have seen so far what if we have two applications trying to print? what’s an OS / why do we need an OS a set of programming abstractions a mediator between applications/hardware Kirk McKusick - A Narrative History of BSD what’s the OS on your phone/laptop/…? see more on the readings page what happens after power on? high-level: firmware → bootloader → OS kernel what’re the “handover protocols” / machine state after each handover BIOS firmware: a program stored in non-volatile memory detect & initialize hardware start in real mode: 16-bit registers, 20-bit (1 MB) addresses load the master boot record (the first sector, 512 bytes) to 0x7c00 & jump there example: bootloader-kernel handover via Multiboot the xv6 bootloader: bootasm. switch to protected mode: 32-bit registers/addresses
load the kernel (in ELF) from hard drive prepare machine state & handover: jump to the entry point in entry. why do we need the bootloader hard to fit the entire OS in 512 bytes more options for users: boot from cdrom, network, usb, etc. can have multiple stages BIOS-booting pros & cons arch-specific: x86 real to protected (to long) mode Unified Extensible Firmware Interface (UEFI) the first xv6 exercise & JOS lab 1 review x86 calling convention from CSE 351Being able to easily run and debug a simple operating system can be really useful when you want to learn how low level components are implemented. very simple Unix-like operating system that allows you to do just that. this in the Hacker News’ thread on Xv6: Wondered how a filesystem can survive a power outage? Wondered how to organize C code? Wondered how memory allocation works? Wondered how memory paging works? Wondered about the difference between a kernel function and a userspace function?
Wondered how a shell works? (How it parses your commands, or how to write your own, etc) Wondered how a mutex can be implemented? Or how to have multiple threads executing safely? How multiple processes are scheduled by the OS? How permissions are enforced by the OS? Why Unix won while Multics didn’t (simplicity)?Stdin/stdout and how to compose them together to build complicated systems without drowning in complexity? I credit studying xv6 as being one of the most important decisions I’ve made; up there with learning vim or emacs, or touch typing. knowledge which will serve you the rest of your life in a thousand ways, bothSpend a weekend or two dissecting xv6 and you’ll love yourself for it later. (Be sure to study the book, not just the source code. It’s freely available online. The source code is also distributed as a PDF, which seems strange till you start reading the book. Both PDFs are meant to be read simultaneously, rather than each alone.)
Download, Compile, and Run You can download Xv6’s source code, compile, and run under QEMU using the It looks like this: There are very few commands available but you can see UNIX here: Xv6’s Makefile has a rule to make this very easy (qemu-gdb): Execution stopped before the first instruction and is now waiting for GDB to connect and supervise the execution (breakpoint, continue…). Now you can set breakpoints, resume execution, and do whatever you want. set a breakpoint at the exec function: You can see that /init was the first process, it spawned sh and I entered ls in the console myself. Things are magically simple!Due 11:59 PM, Friday, April 15, 2016 In this lab you will experiment with different scheduling policies in xv6. Specifically, you will implement the lottery scheduling policy. If you want to build upon your copy-on-write fork, you may. However, you are also welcome to create a new branch based on the unmodified xv6 code.
When you are ready to hand in your lab code and write-up, create a file called slack.txt noting how many late hours you have used both for this assignment and in(This is to help us agree on the number that you have used.) This file should contain a single line formatted as follows (where n is the number of late hours): Then run make handin-lab4 in the xv6 directory. If you submit multiple times, we will take the latest submission and count late hours accordingly. In this and all other labs, you may complete challenge problems for extra credit. If you do this, please create a file called challenge.txt, which includes a short (e.g., one or two paragraph) description of what you did to solve your chosen challenge problem and how to test it. If you implement more than one challenge problem, you must describe each one. This lab does not include any questions for you to answer, but you should document your design in the README file.
Start by reading Chapter 5 of the xv6 book. This is a very good guide to the details of how scheduling and context switches are implemented in xv6. The default and only scheduling policy in xv6 is round-robin. In other words, every runnable process gets an equal CPU timeslice, regardless of priority. Your goal for this homework is to create a framework for expressing priorities, as well as implement the lottery scheduler to support these priorities. You will also need to write several test cases to demonstrate that your system implements these policies correctly. The first step in implementing a non-trivial scheduler is to actually haveIn order to keep the homework simple, you may just implement the nice Unix API as an extra system call. Remember, a higher nice value means a lower priority. For more on the nice specification, type man 2 nice on a Linux system. This should be a very straightforward exercise after lab 1, except that you will also need
to store the nice value in the process structure. Note that xv6 stores the process control block (PCB, or PEB in Windows parlance, or task struct in Linux parlance) in struct proc in the file proc.h. Simplification: You do not need to enforce permissions on nice. On a typical Linux system, only root can increase priorities (lower nice values); to keep life simple for this project, you can skip this part of the specification. Hint: nice is specified as a "set" method, but there is a way to also "get" the current value with clever argument selection. this works on your system. Implement the nice system call in xv6. Write a simple test case to verify that the nice value can set and be read back correctly. Document how to run this test in a file named README.lab3. Lottery scheduling is a randomized heuristic. This does not require strong randomness, as may be need for cryptographic algorithms---a decent pseudo-random number
generator (PRNG) will do. Because xv6 does not include a PRNG, you will need to write one. For your implementation, we recommend something in although you are welcome to use others. Hint: If you do use Xorshift, be very careful to pick non-zero seed values. Implement an in-kernel pseudo-random number generator. Write a simple, in-kernel test case to verify that the values returned look reasonably evenly distributed over the value space. Document how to run this test (up to 25 points, depending on solution quality) Implement a true random number generator, suitable for use in a cryptographic algorithm. True randomness is hard, and requires both sophisticated algorithms and a pool of entropy from external sources, such as non-deterministic hardware events (e.g., mouse movement, keystrokes, and heat). Software Generation of Practically Strong Random Numbers (Gutmann, Usenix Security '07) Recommendations for Randomness in the Operating System (Corrigan-Gibbs and Jana, HotOS '15)
As explained in the course slides, as well as Chapter 9 of the OS book, lottery scheduling basically works by assigning numbers (tickets) to each process in the system, and then randomly picking a "winning" ticket each timeslice. You may decide (and document in README.lab3) a policy for how many more tickets to assign less "nice" processes, From here, the design of the scheduling data structures isAs you read the book and think about your design, some factors to consider: How to map the winning number back to a runnable process? What data structure makes sense? How would you gracefully handle proceses leaving or entering the system, while maintaining the policy?Simplification:Please keep both schedulers as options. For simplicity, it is fine for the scheduler selection (lottery vs. RR) to be a compile-time option, although a few bonus points are availble if a group wishes to implement the ability to dynamically select Implement lottery scheduling in xv6.
As explained above, the particular selection of data structures and policies for mapping the number of tickets to nice values is up to you. An important aspect of this project is convincing the course staff that your implementation handles all of the reasonable edge cases, so please err on the side of writing extensive documentation (even "what if?" questions and answers) in the README.lab3 file. Write at least three good test cases (although more are strongly recommended) for your lottery scheduler. Extra credit is possible for creativity, and the quality of these tests can influence your score for Exercise 3. Some suggestions and hints: Fork several children all doing the same CPU-bound task (say computing prime numbers), but with different priorities. Each child prints progress at incremental points. Verify that the higher-priority children make more progress, and that progress is reasonably proportional to priority. Change the priority of a process dynamically;
does progress accelerate or slow appropriately? For setting up a simple, controlled experiment, you may find yield helpful. But do note that yield should forego the rest of a timeslice, so factor this into your analysis of test behavior. (up to 5 points, depending on solution quality) Implement the ability to dynamically select between the round-robin scheduler and the lottery scheduler. Be sure that policies are correctly enforced when switching back and forth (e.g., nice values or "tickets" are not lost or mis-allocated when switching). (up to 20 points, depending on solution quality) Implement the multi-level feedback queue scheduler, as 8 of the OS book. Be sure to add enough (optional) debug prints and documentation to be sure that the algorithm is working correctly, and design test cases that demonstrate that, as nice values change, the number of quanta assigned This completes the lab. hand in your work with make handin-lab4.