-@node Project 1--Threads, Project 2--User Programs, Top, Top
+@node Project 1--Threads, Project 2--User Programs, Introduction, Top
@chapter Project 1: Threads
In this assignment, we give you a minimally functional thread system.
@menu
* Understanding Threads::
+* Project 1 Code::
* Debugging versus Testing::
* Tips::
* Problem 1-1 Alarm Clock::
* Threads FAQ::
@end menu
-@node Understanding Threads, Debugging versus Testing, Project 1--Threads, Project 1--Threads
+@node Understanding Threads
@section Understanding Threads
The first step is to read and understand the initial thread system.
Pintos, by default, implements thread creation and thread completion,
a simple scheduler to switch between threads, and synchronization
primitives (semaphores, locks, and condition variables).
-@c FIXME: base system doesn't do anything. Debugger sucks.
-However, there's a lot of magic going on in some of this code, so you
-should compile and run the base system to see a simple test of the
-code. You should read through the source code by hand to see what's
-going on. If you like, you can add calls to @code{printf()} almost
+
+However, there's a lot of magic going on in some of this code, so if
+you haven't already compiled and run the base system, as described in
+the introduction (@pxref{Introduction}), you should do so now. You
+can read through parts of the source code by hand to see what's going
+on. If you like, you can add calls to @code{printf()} almost
anywhere, then recompile and run to see what happens and in what
-order.
+order. You can also run the kernel in a debugger and set breakpoints
+at interesting spots, single-step through code and examine data, and
+so on. @xref{i386-elf-gdb}, for more information.
When a thread is created, you are creating a new context to be
scheduled. You provide a function to be run in this context as an
assembly; don't worry about understanding it). It involves saving the
state of the currently running thread and restoring the state of the
thread we're switching to.
-@c FIXME
-Slowly trace through a context switch to see what happens. Be sure to
-keep track of each thread's address and state, and what procedures are
-on the call stack for each thread. You will notice that when one
-thread calls @code{switch_threads()}, another thread starts running,
-and the first thing the new thread does is to return from
-@code{switch_threads()}. We realize this comment will seem cryptic to
+
+Using the @command{gdb} debugger, slowly trace through a context
+switch to see what happens (@pxref{i386-elf-gdb}). You can set a
+breakpoint on the @code{schedule()} function to start out, and then
+single-step from there. Be sure to keep track of each thread's
+address and state, and what procedures are on the call stack for each
+thread. You will notice that when one thread calls
+@code{switch_threads()}, another thread starts running, and the first
+thing the new thread does is to return from
+@code{switch_threads()}. We realize this comment will seem cryptic to
you at this point, but you will understand threads once you understand
why the @code{switch_threads()} that gets called is different from the
-@code{switch_threads()} that returns.
+@code{switch_threads()} that returns. @c FIXME
@strong{Warning}: In Pintos, each thread is assigned a small,
fixed-size execution stack just under @w{4 kB} in size. The kernel
limit. If you need larger chunks, consider using a linked structure
instead.
-@node Debugging versus Testing, Tips, Understanding Threads, Project 1--Threads
+@node Project 1 Code
+@section Code
+
+Here is a brief overview of the files in the @file{threads}
+directory. You will not need to modify most of this code, but the
+hope is that presenting this overview will give you a start on what
+code to look at.
+
+@table @file
+@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. You should not need to look at this code or
+modify it.
+
+@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
+of the kernel image. 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 @code{main()}.
+
+@item init.c
+@itemx init.h
+Kernel initialization, including @code{main()}, the kernel's ``main
+program.'' You should look over @code{main()} at least to see what
+gets initialized.
+
+@item thread.c
+@itemx thread.h
+Basic thread support. Much of your work will take place in these
+files. @file{thread.h} defines @code{struct thread}, which you will
+modify in the first three projects.
+
+@item switch.S
+@itemx switch.h
+Assembly language routine for switching threads. Already discussed
+above.
+
+@item palloc.c
+@itemx palloc.h
+Page allocator, which hands out system memory one 4 kB page at a time.
+
+@item paging.c
+@itemx paging.h
+Initializes the kernel page table. FIXME
+
+@item malloc.c
+@itemx malloc.h
+A very simple implementation of @code{malloc()} and @code{free()} for
+the kernel. The largest block that can be allocated is 2 kB.
+
+@item interrupt.c
+@itemx interrupt.h
+Basic interrupt handling and functions for turning interrupts on and
+off.
+
+@item intr-stubs.pl
+@itemx intr-stubs.h
+A Perl program that outputs assembly for low-level interrupt handling.
+
+@item synch.c
+@itemx synch.h
+Basic synchronization primitives: semaphores, locks, and condition
+variables. You will need to use these for synchronization through all
+four projects.
+
+@item test.c
+@itemx test.h
+Test code. For project 1, you will replace this file with your test
+cases.
+
+@item io.h
+Functions for I/O port access. This is mostly used by source code in
+the @file{devices} directory that you won't have to touch.
+
+@item mmu.h
+Functions and macros related to memory management, including page
+directories and page tables. This will be more important to you in
+project 3. For now, you can ignore it.
+@end table
+
+
+
+@node Debugging versus Testing
@section Debugging versus Testing
When you're debugging code, it's useful to be able to be able to run a
as @var{seed} is varied. Thus, for the highest degree of confidence
you should test your code with many seed values.
-@node Tips, Problem 1-1 Alarm Clock, Debugging versus Testing, Project 1--Threads
+@node Tips
@section Tips
There should be no busy-waiting in any of your solutions to this
need to fix it for future assignments. The other parts can be turned
off in the future if you find you can't make them work quite right.
-Also keep in mind that Problem 4 (the MFQS) builds on the features you
+Also keep in mind that Problem 4 (the MLFQS) builds on the features you
implement in Problem 3, so to avoid unnecessary code duplication, it
would be a good idea to divide up the work among your team members
such that you have Problem 3 fully working before you begin to tackle
Problem 4.
-@node Problem 1-1 Alarm Clock, Problem 1-2 Join, Tips, Project 1--Threads
-@section Problem 1-2: Alarm Clock
+@node Problem 1-1 Alarm Clock
+@section Problem 1-1: Alarm Clock
Improve the implementation of the timer device defined in
@file{devices/timer.c} by reimplementing @code{timer_sleep()}.
The argument to @code{timer_sleep()} is expressed in timer ticks, not
in milliseconds or some other unit.
-@node Problem 1-2 Join, Problem 1-3 Priority Scheduling, Problem 1-1 Alarm Clock, Project 1--Threads
+@node Problem 1-2 Join
@section Problem 1-2: Join
Implement @code{thread_join(struct thread *)} in
Be careful to program this function correctly. You will need its
functionality for project 2.
-@node Problem 1-3 Priority Scheduling, Problem 1-4 Advanced Scheduler, Problem 1-2 Join, Project 1--Threads
+@node Problem 1-3 Priority Scheduling
@section Problem 1-3 Priority Scheduling
Implement priority scheduling in Pintos. Priority
implement this fix for semaphores, condition variables or joins.
However, you do need to implement priority scheduling in all cases.
-@node Problem 1-4 Advanced Scheduler, Threads FAQ, Problem 1-3 Priority Scheduling, Project 1--Threads
+@node Problem 1-4 Advanced Scheduler
@section Problem 1-4 Advanced Scheduler
-Implement Solaris's multilevel feedback queue scheduler (MFQS), as
-explained in this @uref{mlfqs.pdf, , PDF} or @uref{mlfqs.ps, ,
-PostScript} file, to reduce the average response time for running jobs
-on your system.
+Implement Solaris's multilevel feedback queue scheduler (MLFQS) to
+reduce the average response time for running jobs on your system.
+@xref{Multilevel Feedback Scheduling}, for a detailed description of
+the MLFQS requirements.
Demonstrate that your scheduling algorithm reduces response time
relative to the original Pintos scheduling algorithm (round robin) for
to ``re-donate'' a thread's priority if it changes (although you are
free to do so).
-@node Threads FAQ, , Problem 1-4 Advanced Scheduler, Project 1--Threads
+@node Threads FAQ
@section FAQ
@enumerate 1
@enumerate 1
@item
@b{I am adding a new @file{.h} or @file{.c} file. How do I fix the
-@file{Makefile}s?}
+@file{Makefile}s?}@anchor{Adding c or h Files}
To add a @file{.c} file, edit the top-level @file{Makefile.build}.
You'll want to add your file to variable @samp{@var{dir}_SRC}, where
directory. Then run @code{make}. If your new file doesn't get
compiled, run @code{make clean} and then try again.
+When you modify the top-level @file{Makefile.build}, the modified
+version should be automatically copied to
+@file{threads/build/Makefile} when you re-run make. The opposite is
+not true, so any changes will be lost the next time you run @code{make
+clean} from the @file{threads} directory. Therefore, you should
+prefer to edit @file{Makefile.build} (unless your changes are meant to
+be truly temporary).
+
There is no need to edit the @file{Makefile}s to add a @file{.h} file.
@item
projects / pintos-anon / blobdiff