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
@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.
@item serial.c
@itemx serial.h
Serial port driver. Again, @func{printf} calls this code for you,
-so you don't need to do so yourself. Feel free to look through it if
-you're curious.
+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 kbd.c
+@itemx kbd.h
+Keyboard driver. Handles keystrokes passing them to the input layer
+(see below).
+
+@item input.c
+@itemx input.h
+Input layer. Queues input characters passed along by the keyboard or
+serial drivers.
+
@item intq.c
@itemx intq.h
Interrupt queue, for managing a circular queue that both kernel
than the currently running thread, the current thread should
immediately yield the processor to the new thread. Similarly, when
threads are waiting for a lock, semaphore, or condition variable, the
-highest priority waiting thread should be woken up first. A thread
+highest priority waiting thread should be awakened first. A thread
may raise or lower its own priority at any time, but lowering its
priority such that it no longer has the highest priority must cause it
to immediately yield the CPU.
must be active, but we must be able to choose the 4.4@acronym{BSD}
scheduler
with the @option{-mlfqs} kernel option. Passing this
-option sets @code{enable_mlfqs}, declared in @file{threads/init.h}, to
+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
to be @func{pass}.
@xref{Backtraces}, for more information.
+
+@item How do interrupts get re-enabled in the new thread following @func{schedule}?
+
+Every path into @func{schedule} disables interrupts. They eventually
+get re-enabled by the next thread to be scheduled. Consider the
+possibilities: the new thread is running in @func{switch_thread} (but
+see below), which is called by @func{schedule}, which is called by one
+of a few possible functions:
+
+@itemize @bullet
+@item
+@func{thread_exit}, but we'll never switch back into such a thread, so
+it's uninteresting.
+
+@item
+@func{thread_yield}, which immediately restores the interrupt level upon
+return from @func{schedule}.
+
+@item
+@func{thread_block}, which is called from multiple places:
+
+@itemize @minus
+@item
+@func{sema_down}, which restores the interrupt level before returning.
+
+@item
+@func{idle}, which enables interrupts with an explicit assembly STI
+instruction.
+
+@item
+@func{wait} in @file{devices/intq.c}, whose callers are responsible for
+re-enabling interrupts.
+@end itemize
+@end itemize
+
+There is a special case when a newly created thread runs for the first
+time. Such a thread calls @func{intr_enable} as the first action in
+@func{kernel_thread}, which is at the bottom of the call stack for every
+kernel thread but the first.
@end table
@menu
@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?
+
+Yes. While a thread that has acquired lock @var{L} is blocked for any
+reason, its priority can increase by priority donation if a
+higher-priority thread attempts to acquire @var{L}. This case is
+checked by the @code{priority-donate-sema} test.
@item Can a thread added to the ready list preempt the processor?
@item How does @func{thread_set_priority} affect a thread receiving donations?
-It should do something sensible, but no particular behavior is
-required. None of the test cases call @func{thread_set_priority} from a
-thread while it is receiving a priority donation.
-
-@item Calling @func{printf} in @func{sema_up} or @func{sema_down} reboots!
-
-@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.
+It sets the thread's base priority. The thread's effective priority
+becomes the higher of the newly set priority or the highest donated
+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.
@end table
@node Advanced Scheduler FAQ
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
projects / pintos-anon / blobdiff