-@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::
* Problem 1-2 Join::
* Problem 1-3 Priority Scheduling::
* Problem 1-4 Advanced Scheduler::
-* Threads FAQ::
-* Multilevel Feedback Scheduling::
+* 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
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 (MLFQS) to
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
No. Hard-coding the dispatch table values is fine.
@end enumerate
@end enumerate
-
-@include mlfqs.texi
projects / pintos-anon / blobdiff