X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?p=pintos-anon;a=blobdiff_plain;f=doc%2Fthreads.texi;h=c9094bc2d073ddd5642aad218fc82465ecabdc5c;hp=cbcda160631b2c918c23d9d81e9ce4277a10be23;hb=919347c164606c3f1544b2e8bd62f505aeda80a1;hpb=d4c30c6a386fe850e7eed1025e459fbc82a0b6e2 diff --git a/doc/threads.texi b/doc/threads.texi index cbcda16..c9094bc 100644 --- a/doc/threads.texi +++ b/doc/threads.texi @@ -40,7 +40,7 @@ The first step is to read and understand the code for the initial thread system. Pintos already implements thread creation and thread completion, a simple scheduler to switch between threads, and synchronization -primitives (semaphores, locks, condition variables, and memory +primitives (semaphores, locks, condition variables, and optimization barriers). Some of this code might seem slightly mysterious. If @@ -113,27 +113,30 @@ code to look at. @item loader.S @itemx loader.h The kernel loader. Assembles to 512 bytes of code and data that the -PC BIOS loads into memory and which in turn loads the kernel into -memory, does basic processor initialization, and jumps to the -beginning of the kernel. @xref{Pintos Loader}, for details. You should -not need to look at this code or modify it. +PC BIOS loads into memory and which in turn finds the kernel on disk, +loads it into memory, and jumps to @func{start} in @file{start.S}. +@xref{Pintos Loader}, for details. You should not need to look at +this code or modify it. + +@item start.S +Does basic setup needed for memory protection and 32-bit +operation on 80@var{x}86 CPUs. Unlike the loader, this code is +actually part of the kernel. @xref{Low-Level Kernel Initialization}, +for details. @item kernel.lds.S The linker script used to link the kernel. Sets the load address of -the kernel and arranges for @file{start.S} to be at the very beginning +the kernel and arranges for @file{start.S} to be near the beginning of the kernel image. @xref{Pintos Loader}, for details. Again, you should not need to look at this code or modify it, but it's here in case you're curious. -@item start.S -Jumps to @func{main}. - @item init.c @itemx init.h Kernel initialization, including @func{main}, the kernel's ``main program.'' You should look over @func{main} at least to see what gets initialized. You might want to add your own initialization code -here. @xref{Kernel Initialization}, for details. +here. @xref{High-Level Kernel Initialization}, for details. @item thread.c @itemx thread.h @@ -170,7 +173,7 @@ Infrastructure}, for more information. @item synch.c @itemx synch.h Basic synchronization primitives: semaphores, locks, condition -variables, and memory barriers. You will need to use these for +variables, and optimization barriers. You will need to use these for synchronization in all four projects. @xref{Synchronization}, for more information. @@ -220,10 +223,23 @@ Serial port driver. Again, @func{printf} calls this code for you, so you don't need to do so yourself. It handles serial input by passing it to the input layer (see below). -@item disk.c -@itemx disk.h -Supports reading and writing sectors on up to 4 IDE disks. This won't -actually be used until project 2. +@item block.c +@itemx block.h +An abstraction layer for @dfn{block devices}, that is, random-access, +disk-like devices that are organized as arrays of fixed-size blocks. +Out of the box, Pintos supports two types of block devices: IDE disks +and partitions. Block devices, regardless of type, won't actually be +used until project 2. + +@item ide.c +@itemx ide.h +Supports reading and writing sectors on up to 4 IDE disks. + +@item partition.c +@itemx partition.h +Understands the structure of partitions on disks, allowing a single +disk to be carved up into multiple regions (partitions) for +independent use. @item kbd.c @itemx kbd.h @@ -240,6 +256,22 @@ serial drivers. Interrupt queue, for managing a circular queue that both kernel threads and interrupt handlers want to access. Used by the keyboard and serial drivers. + +@item rtc.c +@itemx rtc.h +Real-time clock driver, to enable the kernel to determine the current +date and time. By default, this is only used by @file{thread/init.c} +to choose an initial seed for the random number generator. + +@item speaker.c +@itemx speaker.h +Driver that can produce tones on the PC speaker. + +@item pit.c +@itemx pit.h +Code to configure the 8254 Programmable Interrupt Timer. This code is +used by both @file{devices/timer.c} and @file{devices/speaker.c} +because each device uses one of the PIT's output channel. @end table @node lib files @@ -277,7 +309,11 @@ more information. @item random.c @itemx random.h -Pseudo-random number generator. +Pseudo-random number generator. The actual sequence of random values +will not vary from one Pintos run to another, unless you do one of +three things: specify a new random seed value on the @option{-rs} +kernel command-line option on each run, or use a simulator other than +Bochs, or specify the @option{-r} option to @command{pintos}. @item round.h Macros for rounding. @@ -364,13 +400,7 @@ with each other, requiring lots of last-minute debugging. Some groups who have done this have turned in code that did not even compile or boot, much less pass any tests. -Instead, we recommend integrating your team's changes early and often, -using a source code control system such as CVS (@pxref{CVS}) or a -group collaboration site such as SourceForge (@pxref{SourceForge}). -This is less likely to produce surprises, because everyone can see -everyone else's code as it is written, instead of just when it is -finished. These systems also make it possible to review changes and, -when a change introduces a bug, drop back to working versions of code. +@localcvspolicy{} You should expect to run into bugs that you simply don't understand while working on this and subsequent projects. When you do, @@ -480,9 +510,9 @@ priority. If necessary, you may impose a reasonable limit on depth of nested priority donation, such as 8 levels. You must implement priority donation for locks. You need not -implement priority donation for semaphores or condition variables -(but you are welcome to do so). You do need to implement -priority scheduling in all cases. +implement priority donation for the other Pintos synchronization +constructs. You do need to implement priority scheduling in all +cases. Finally, implement the following functions that allow a thread to examine and modify its own priority. Skeletons for these functions are @@ -524,7 +554,7 @@ scheduler with the @option{-mlfqs} kernel option. Passing this option sets @code{thread_mlfqs}, declared in @file{threads/thread.h}, to true when the options are parsed by @func{parse_options}, which happens -midway through @func{main}. +early in @func{main}. When the 4.4@acronym{BSD} scheduler is enabled, threads no longer directly control their own priorities. The @var{priority} argument to @@ -613,6 +643,18 @@ to cause many of the tests to fail. @xref{Testing}. +@item Should I try running the tests with jitter? + +Using the jitter feature in Bochs (@pxref{Debugging versus Testing}) +is a great way to discover bugs that are timing dependent. However, +the following tests are known to +fail with jitter even if your code is correct: @code{alarm-priority}, +@code{alarm-simultaneous}, +@code{mlfqs-recent-1}, @code{mlfqs-fair-2}, @code{mlfqs-fair-20}, +@code{mlfqs-nice-2}, @code{mlfqs-nice-10}, and @code{priority-fifo}. +The behavior of these tests can sometimes vary based on timing (e.g., +if a timer interrupt arrives at an inconvenient time). + @item Why do I get a test failure in @func{pass}? @anchor{The pass function fails} @@ -633,7 +675,7 @@ does not actually mean that @func{pass} called @func{debug_panic}. In fact, @func{fail} called @func{debug_panic} (via the @func{PANIC} macro). GCC knows that @func{debug_panic} does not return, because it is declared @code{NO_RETURN} (@pxref{Function and Parameter -Attributes}), so it doesn't include any code in @func{pass} to take +Attributes}), so it doesn't include any code in @func{fail} to take control when @func{debug_panic} returns. This means that the return address on the stack looks like it is at the beginning of the function that happens to follow @func{fail} in memory, which in this case happens @@ -696,7 +738,7 @@ kernel thread but the first. Don't worry about the possibility of timer values overflowing. Timer values are expressed as signed 64-bit numbers, which at 100 ticks per second should be good for almost 2,924,712,087 years. By then, we -expect Pintos to have been phased out of the CS 140 curriculum. +expect Pintos to have been phased out of the Computer Science curriculum. @end table @node Priority Scheduling FAQ @@ -740,11 +782,9 @@ to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8. @item Can a thread's priority change while it is on the ready queue? -Yes. Consider this case: low-priority thread @var{L} holds a -lock that high-priority thread @var{H} wants, so @var{H} donates its -priority to @var{L}. @var{L} releases the lock and -thus loses the CPU and is moved to the ready queue. Now @var{L}'s -old priority is restored while it is in the ready queue. +Yes. Consider a ready, low-priority thread @var{L} that holds a lock. +High-priority thread @var{H} attempts to acquire the lock and blocks, +thereby donating its priority to ready thread @var{L}. @item Can a thread's priority change while it is blocked? @@ -769,13 +809,35 @@ priority. When the donations are released, the thread's priority becomes the one set through the function call. This behavior is checked by the @code{priority-donate-lower} test. -@item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots! +@item Doubled test names in output make them fail. + +Suppose you are seeing output in which some test names are doubled, +like this: + +@example +(alarm-priority) begin +(alarm-priority) (alarm-priority) Thread priority 30 woke up. +Thread priority 29 woke up. +(alarm-priority) Thread priority 28 woke up. +@end example -@anchor{printf Reboots} -Yes. These functions are called before @func{printf} is ready to go. -You could add a global flag initialized to false and set it to true -just before the first @func{printf} in @func{main}. Then modify -@func{printf} itself to return immediately if the flag isn't set. +What is happening is that output from two threads is being +interleaved. That is, one thread is printing @code{"(alarm-priority) +Thread priority 29 woke up.\n"} and another thread is printing +@code{"(alarm-priority) Thread priority 30 woke up.\n"}, but the first +thread is being preempted by the second in the middle of its output. + +This problem indicates a bug in your priority scheduler. After all, a +thread with priority 29 should not be able to run while a thread with +priority 30 has work to do. + +Normally, the implementation of the @code{printf()} function in the +Pintos kernel attempts to prevent such interleaved output by acquiring +a console lock during the duration of the @code{printf} call and +releasing it afterwards. However, the output of the test name, +e.g., @code{(alarm-priority)}, and the message following it is output +using two calls to @code{printf}, resulting in the console lock being +acquired and released twice. @end table @node Advanced Scheduler FAQ @@ -791,4 +853,32 @@ scheduler at the same time. Yes. In general, your implementation may differ from the description, as long as its behavior is the same. + +@item Some scheduler tests fail and I don't understand why. Help! + +If your implementation mysteriously fails some of the advanced +scheduler tests, try the following: + +@itemize +@item +Read the source files for the tests that you're failing, to make sure +that you understand what's going on. Each one has a comment at the +top that explains its purpose and expected results. + +@item +Double-check your fixed-point arithmetic routines and your use of them +in the scheduler routines. + +@item +Consider how much work your implementation does in the timer +interrupt. If the timer interrupt handler takes too long, then it +will take away most of a timer tick from the thread that the timer +interrupt preempted. When it returns control to that thread, it +therefore won't get to do much work before the next timer interrupt +arrives. That thread will therefore get blamed for a lot more CPU +time than it actually got a chance to use. This raises the +interrupted thread's recent CPU count, thereby lowering its priority. +It can cause scheduling decisions to change. It also raises the load +average. +@end itemize @end table