1 @node Pintos Tour, Project 1--Threads, Introduction, Top
2 @chapter A Tour Through Pintos
4 This chapter is a brief tour through the Pintos code. It covers the
5 entire code base, but you'll only be using Pintos one part at a time,
6 so you may find that you want to read each part as you work on the
9 Hint: try using ``tags'' to follow along with references to function
10 and variable names (@pxref{Tags}).
20 This section covers the Pintos loader and basic kernel
25 * Kernel Initialization::
29 @subsection The Loader
31 The first part of Pintos that runs is the loader, in
32 @file{threads/loader.S}. The PC BIOS loads the loader into memory.
33 The loader, in turn, is responsible for initializing the CPU, loading
34 the rest of Pintos into memory, and then jumping to its start. It's
35 not important to understand exactly what the loader does, but if
36 you're interested, read on. You should probably read along with the
37 loader's source. You should also understand the basics of the
38 80@var{x}86 architecture as described by chapter 3 of
41 Because the PC BIOS loads the loader, the loader has to play by the
42 BIOS's rules. In particular, the BIOS only loads 512 bytes (one disk
43 sector) into memory. This is a severe restriction and it means that,
44 practically speaking, the loader has to be written in assembly
47 Pintos' loader first initializes the CPU. The first important part of
48 this is to enable the A20 line, that is, the CPU's address line
49 numbered 20. For historical reasons, PCs start out with this address
50 line fixed at 0, which means that attempts to access memory beyond the
51 first 1 MB (2 raised to the 20th power) will fail. Pintos wants to
52 access more memory than this, so we have to enable it.
54 Next, the loader asks the BIOS for the PC's memory size. Again for
55 historical reasons, the function that we call in the BIOS to do this
56 can only detect up to 64 MB of RAM, so that's the practical limit that
57 Pintos can support. The memory size is stashed away in a location in
58 the loader that the kernel can read after it boots.
60 Third, the loader creates a basic page table. This page table maps
61 the 64 MB at the base of virtual memory (starting at virtual address
62 0) directly to the identical physical addresses. It also maps the
63 same physical memory starting at virtual address
64 @code{LOADER_PHYS_BASE}, which defaults to @t{0xc0000000} (3 GB). The
65 Pintos kernel only wants the latter mapping, but there's a
66 chicken-and-egg problem if we don't include the former: our current
67 virtual address is roughly @t{0x7c00}, the location where the BIOS
68 loaded us, and we can't jump to @t{0xc0007c00} until we turn on the
69 page table, but if we turn on the page table without jumping there,
70 then we've just pulled the rug out from under ourselves.
72 After the page table is initialized, we load the CPU's control
73 registers to turn on protected mode and paging, and then we set up the
74 segment registers. We aren't equipped to handle interrupts in
75 protected mode yet, so we disable interrupts.
77 Finally it's time to load the kernel from disk. We use a simple but
78 inflexible method to do this: we program the IDE disk
79 controller directly. We assume that the kernel is stored starting
80 from the second sector of the first IDE disk (the first sector normally
81 contains the boot loader). We also assume that the BIOS has
82 already set up the IDE controller for us. We read
83 @code{KERNEL_LOAD_PAGES} pages of data (4 kB per page) from the disk directly
84 into virtual memory, starting @code{LOADER_KERN_BASE} bytes past
85 @code{LOADER_PHYS_BASE}, which by default means that we load the
86 kernel starting 1 MB into physical memory.
88 Then we jump to the start of the compiled kernel image. Using the
89 ``linker script'' in @file{threads/kernel.lds.S}, the kernel has
90 arranged that it begins with the assembly module
91 @file{threads/start.S}. This assembly module just calls
92 @func{main}, which never returns.
94 There's one more trick: the Pintos kernel command line
95 is stored in the boot loader. The @command{pintos} program actually
96 modifies the boot loader on disk each time it runs the kernel, putting
97 in whatever command line arguments the user supplies to the kernel,
98 and then the kernel at boot time reads those arguments out of the boot
99 loader in memory. This is something of a nasty hack, but it is simple
102 @node Kernel Initialization
103 @subsection Kernel Initialization
105 The kernel proper starts with the @func{main} function. The
106 @func{main} function is written in C, as will be most of the code we
107 encounter in Pintos from here on out.
109 When @func{main} starts, the system is in a pretty raw state. We're
110 in protected mode with paging enabled, but hardly anything else is
111 ready. Thus, the @func{main} function consists primarily of calls
112 into other Pintos modules' initialization functions.
113 These are usually named @func{@var{module}_init}, where
114 @var{module} is the module's name, @file{@var{module}.c} is the
115 module's source code, and @file{@var{module}.h} is the module's
118 First we initialize kernel RAM in @func{ram_init}. The first step
119 is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
120 segment that should be initialized to all zeros. In most C
121 implementations, whenever you
122 declare a variable outside a function without providing an
123 initializer, that variable goes into the BSS. Because it's all zeros, the
124 BSS isn't stored in the image that the loader brought into memory. We
125 just use @func{memset} to zero it out. The other task of
126 @func{ram_init} is to read out the machine's memory size from where
127 the loader stored it and put it into the @code{ram_pages} variable for
130 Next, @func{thread_init} initializes the thread system. We will defer
131 full discussion to our discussion of Pintos threads below. It is
132 called so early in initialization because the console, initialized
133 just afterward, tries to use locks, and locks in turn require there to be a
136 Then we initialize the console so that we can use @func{printf}.
137 @func{main} calls @func{vga_init}, which initializes the VGA text
138 display and clears the screen. It also calls @func{serial_init_poll}
139 to initialize the first serial port in ``polling mode,'' that is,
140 where the kernel busy-waits for the port to be ready for each
141 character to be output. (We use polling mode until we're ready to set
142 up interrupts later.) Finally we initialize the console device and
143 print a startup message to the console.
145 @func{main} calls @func{read_command_line} to break the kernel command
146 line into arguments, then @func{parse_options} to read any options at
147 the beginning of the command line. (Executing actions specified on the
148 command line happens later.)
150 The next block of functions we call initialize the kernel's memory
151 system. @func{palloc_init} sets up the kernel page allocator, which
152 doles out memory one or more pages at a time. @func{malloc_init} sets
153 up the allocator that handles odd-sized allocations.
154 @func{paging_init} sets up a page table for the kernel.
156 In projects 2 and later, @func{main} also calls @func{tss_init} and
157 @func{gdt_init}, but we'll talk about those later.
159 @func{main} calls @func{random_init} to initialize the kernel random
160 number generator. If the user specified @option{-rs} on the
161 @command{pintos} command line, @func{parse_options} has already done
162 this, but calling it a second time is harmless and has no effect.
164 We initialize the interrupt system in the next set of calls.
165 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
166 (IDT) to ready it for interrupt handling (@pxref{Interrupt
167 Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for
168 handling timer interrupts and keyboard interrupts, respectively. In
169 projects 2 and later, we also prepare to handle interrupts caused by
170 user programs using @func{exception_init} and @func{syscall_init}.
172 Now that interrupts are set up, we can start preemptively scheduling
173 threads with @func{thread_start}, which also enables interrupts.
174 With interrupts enabled, interrupt-driven serial port I/O becomes
176 @func{serial_init_queue} to switch to that mode. Finally,
177 @func{timer_calibrate} calibrates the timer for accurate short delays.
179 If the file system is compiled in, as it will starting in project 2, we
180 now initialize the disks with @func{disk_init}, then the
181 file system with @func{filesys_init}.
183 Boot is complete, so we print a message.
185 Function @func{run_actions} now parses and executes actions specified on
186 the kernel command line, such as @command{run} to run a test (in project
187 1) or a user program (in later projects).
189 Finally, if @option{-q} was specified on the kernel command line, we
190 call @func{power_off} to terminate the machine simulator. Otherwise,
191 @func{main} calls @func{thread_exit}, which allows any other running
192 threads to continue running.
195 @section Threads Project
200 * Interrupt Handling::
201 * Memory Allocation::
205 @subsection Thread Support
214 @subsubsection @code{struct thread}
216 The main Pintos data structure for threads is @struct{thread},
217 declared in @file{threads/thread.h}.
219 @deftp {Structure} {@struct{thread}}
220 Represents a thread or a user process. In the projects, you will have
221 to add your own members to @struct{thread}. You may also change or
222 delete the definitions of existing members.
224 Every @struct{thread} occupies the beginning of its own page of
225 memory. The rest of the page is used for the thread's stack, which
226 grows downward from the end of the page. It looks like this:
230 4 kB +---------------------------------+
244 +---------------------------------+
250 0 kB +---------------------------------+
254 This has two consequences. First, @struct{thread} must not be allowed
255 to grow too big. If it does, then there will not be enough room for the
256 kernel stack. The base @struct{thread} is only a few bytes in size. It
257 probably should stay well under 1 kB.
259 Second, kernel stacks must not be allowed to grow too large. If a stack
260 overflows, it will corrupt the thread state. Thus, kernel functions
261 should not allocate large structures or arrays as non-static local
262 variables. Use dynamic allocation with @func{malloc} or
263 @func{palloc_get_page} instead (@pxref{Memory Allocation}).
266 @deftypecv {Member} {@struct{thread}} {tid_t} tid
267 The thread's thread identifier or @dfn{tid}. Every thread must have a
268 tid that is unique over the entire lifetime of the kernel. By
269 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
270 thread receives the numerically next higher tid, starting from 1 for
271 the initial process. You can change the type and the numbering scheme
275 @deftypecv {Member} {@struct{thread}} {enum thread_status} status
276 The thread's state, one of the following:
278 @defvr {Thread State} @code{THREAD_RUNNING}
279 The thread is running. Exactly one thread is running at a given time.
280 @func{thread_current} returns the running thread.
283 @defvr {Thread State} @code{THREAD_READY}
284 The thread is ready to run, but it's not running right now. The
285 thread could be selected to run the next time the scheduler is
286 invoked. Ready threads are kept in a doubly linked list called
290 @defvr {Thread State} @code{THREAD_BLOCKED}
291 The thread is waiting for something, e.g.@: a lock to become
292 available, an interrupt to be invoked. The thread won't be scheduled
293 again until it transitions to the @code{THREAD_READY} state with a
294 call to @func{thread_unblock}.
297 @defvr {Thread State} @code{THREAD_DYING}
298 The thread will be destroyed by the scheduler after switching to the
303 @deftypecv {Member} {@struct{thread}} {char} name[16]
304 The thread's name as a string, or at least the first few characters of
308 @deftypecv {Member} {@struct{thread}} {uint8_t *} stack
309 Every thread has its own stack to keep track of its state. When the
310 thread is running, the CPU's stack pointer register tracks the top of
311 the stack and this member is unused. But when the CPU switches to
312 another thread, this member saves the thread's stack pointer. No
313 other members are needed to save the thread's registers, because the
314 other registers that must be saved are saved on the stack.
316 When an interrupt occurs, whether in the kernel or a user program, an
317 @struct{intr_frame} is pushed onto the stack. When the interrupt occurs
318 in a user program, the @struct{intr_frame} is always at the very top of
319 the page. @xref{Interrupt Handling}, for more information.
322 @deftypecv {Member} {@struct{thread}} {int} priority
323 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
324 (63). Lower numbers correspond to @emph{higher} priorities, so that
325 priority 0 is the highest priority and priority 63 is the lowest.
326 Pintos as provided ignores thread priorities, but you will implement
327 priority scheduling in project 1 (@pxref{Priority Scheduling}).
330 @deftypecv {Member} {@struct{thread}} {@struct{list_elem}} elem
331 A ``list element'' used to put the thread into doubly linked lists,
332 either the list of threads ready to run or a list of threads waiting
333 on a semaphore. Take a look at @file{lib/kernel/list.h} for
334 information on how to use Pintos doubly linked lists.
337 @deftypecv {Member} {@struct{thread}} {uint32_t *} pagedir
338 Only present in project 2 and later.
341 @deftypecv {Member} {@struct{thread}} {unsigned} magic
342 Always set to @code{THREAD_MAGIC}, which is just a random number defined
343 in @file{threads/thread.c}, and used to detect stack overflow.
344 @func{thread_current} checks that the @code{magic} member of the running
345 thread's @struct{thread} is set to @code{THREAD_MAGIC}. Stack overflow
346 will normally change this value, triggering the assertion. For greatest
347 benefit, as you add members to @struct{thread}, leave @code{magic} as
351 @node Thread Functions
352 @subsubsection Thread Functions
354 @file{threads/thread.c} implements several public functions for thread
355 support. Let's take a look at the most useful:
357 @deftypefun void thread_init (void)
358 Called by @func{main} to initialize the thread system. Its main
359 purpose is to create a @struct{thread} for Pintos's initial thread.
360 This is possible because the Pintos loader puts the initial
361 thread's stack at the top of a page, in the same position as any other
364 Before @func{thread_init} runs,
365 @func{thread_current} will fail because the running thread's
366 @code{magic} value is incorrect. Lots of functions call
367 @func{thread_current} directly or indirectly, including
368 @func{lock_acquire} for locking a lock, so @func{thread_init} is
369 called early in Pintos initialization.
372 @deftypefun void thread_start (void)
373 Called by @func{main} to start the scheduler. Creates the idle
374 thread, that is, the thread that is scheduled when no other thread is
375 ready. Then enables interrupts, which as a side effect enables the
376 scheduler because the scheduler runs on return from the timer interrupt, using
377 @func{intr_yield_on_return} (@pxref{External Interrupt Handling}).
380 @deftypefun void thread_tick (void)
381 Called by the timer interrupt at each timer tick. It keeps track of
382 thread statistics and triggers the scheduler when a time slice expires.
385 @deftypefun void thread_print_stats (void)
386 Called during Pintos shutdown to print thread statistics.
389 @deftypefun void thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
390 Creates and starts a new thread named @var{name} with the given
391 @var{priority}, returning the new thread's tid. The thread executes
392 @var{func}, passing @var{aux} as the function's single argument.
394 @func{thread_create} allocates a page for the thread's
395 @struct{thread} and stack and initializes its members, then it sets
396 up a set of fake stack frames for it (more about this
397 later). The thread is initialized in the blocked state, so the final
398 action before returning is to unblock it, which allows the new thread to
402 @deftp {Type} {void thread_func (void *@var{aux})}
403 This is the type of a thread function. Its @var{aux} argument is the
404 value passed to @func{thread_create}.
407 @deftypefun void thread_block (void)
408 Transitions the running thread from the running state to the blocked
409 state. The thread will not run again until @func{thread_unblock} is
410 called on it, so you'd better have some way arranged for that to happen.
411 Because @func{thread_block} is so low-level, you should prefer to use
412 one of the synchronization primitives instead (@pxref{Synchronization}).
415 @deftypefun void thread_unblock (struct thread *@var{thread})
416 Transitions @var{thread}, which must be in the blocked state, to the
417 ready state, allowing it to resume running. This is called when the
418 event that the thread is waiting for occurs, e.g.@: when the lock that
419 the thread is waiting on becomes available.
422 @deftypefun {struct thread *} thread_current (void)
423 Returns the running thread.
426 @deftypefun {tid_t} thread_tid (void)
427 Returns the running thread's thread id. Equivalent to
428 @code{thread_current ()->tid}.
431 @deftypefun {const char *} thread_name (void)
432 Returns the running thread's name. Equivalent to @code{thread_current
436 @deftypefun void thread_exit (void) @code{NO_RETURN}
437 Causes the current thread to exit. Never returns, hence
438 @code{NO_RETURN} (@pxref{Function and Parameter Attributes}).
441 @deftypefun void thread_yield (void)
442 Yields the CPU to the scheduler, which picks a new thread to run. The
443 new thread might be the current thread, so you can't depend on this
444 function to keep this thread from running for any particular length of
448 @deftypefun int thread_get_priority (void)
449 @deftypefunx void thread_set_priority (int @var{new_priority})
450 Skeleton to set and get thread priority. @xref{Priority Scheduling}.
453 @deftypefun int thread_get_nice (void)
454 @deftypefunx void thread_set_nice (int @var{new_nice})
455 @deftypefunx int thread_get_recent_cpu (void)
456 @deftypefunx int thread_get_load_avg (void)
457 Skeletons for the advanced scheduler. @xref{4.4BSD Scheduler}.
460 @node Thread Switching
461 @subsubsection Thread Switching
463 @func{schedule} is the function responsible for switching threads. It
464 is internal to @file{threads/thread.c} and called only by the three
465 public thread functions that need to switch threads:
466 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
467 Before any of these functions call @func{schedule}, they disable
468 interrupts (or ensure that they are already disabled) and then change
469 the running thread's state to something other than running.
471 @func{schedule} is simple but tricky. It records the
472 current thread in local variable @var{cur}, determines the next thread
473 to run as local variable @var{next} (by calling
474 @func{next_thread_to_run}), and then calls @func{switch_threads} to do
475 the actual thread switch. The thread we switched to was also running
476 inside @func{switch_threads}, as are all the threads not currently
477 running, so the new thread now returns out of
478 @func{switch_threads}, returning the previously running thread.
480 @func{switch_threads} is an assembly language routine in
481 @file{threads/switch.S}. It saves registers on the stack, saves the
482 CPU's current stack pointer in the current @struct{thread}'s @code{stack}
483 member, restores the new thread's @code{stack} into the CPU's stack
484 pointer, restores registers from the stack, and returns.
486 The rest of the scheduler is implemented as @func{schedule_tail}. It
487 marks the new thread as running. If the thread we just switched from
488 is in the dying state, then it also frees the page that contained the
489 dying thread's @struct{thread} and stack. These couldn't be freed
490 prior to the thread switch because the switch needed to use it.
492 Running a thread for the first time is a special case. When
493 @func{thread_create} creates a new thread, it goes through a fair
494 amount of trouble to get it started properly. In particular, a new
495 thread hasn't started running yet, so there's no way for it to be
496 running inside @func{switch_threads} as the scheduler expects. To
497 solve the problem, @func{thread_create} creates some fake stack frames
498 in the new thread's stack:
502 The topmost fake stack frame is for @func{switch_threads}, represented
503 by @struct{switch_threads_frame}. The important part of this frame is
504 its @code{eip} member, the return address. We point @code{eip} to
505 @func{switch_entry}, indicating it to be the function that called
509 The next fake stack frame is for @func{switch_entry}, an assembly
510 language routine in @file{threads/switch.S} that adjusts the stack
511 pointer,@footnote{This is because @func{switch_threads} takes
512 arguments on the stack and the 80@var{x}86 SVR4 calling convention
513 requires the caller, not the called function, to remove them when the
514 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
515 calls @func{schedule_tail} (this special case is why
516 @func{schedule_tail} is separate from @func{schedule}), and returns.
517 We fill in its stack frame so that it returns into
518 @func{kernel_thread}, a function in @file{threads/thread.c}.
521 The final stack frame is for @func{kernel_thread}, which enables
522 interrupts and calls the thread's function (the function passed to
523 @func{thread_create}). If the thread's function returns, it calls
524 @func{thread_exit} to terminate the thread.
527 @node Synchronization
528 @subsection Synchronization
530 If sharing of resources between threads is not handled in a careful,
531 controlled fashion, then the result is usually a big mess.
532 This is especially the case in operating system kernels, where
533 faulty sharing can crash the entire machine. Pintos provides several
534 synchronization primitives to help out.
537 * Disabling Interrupts::
540 * Condition Variables::
544 @node Disabling Interrupts
545 @subsubsection Disabling Interrupts
547 The crudest way to do synchronization is to disable interrupts, that
548 is, to temporarily prevent the CPU from responding to interrupts. If
549 interrupts are off, no other thread will preempt the running thread,
550 because thread preemption is driven by the timer interrupt. If
551 interrupts are on, as they normally are, then the running thread may
552 be preempted by another at any time, whether between two C statements
553 or even within the execution of one.
555 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
556 is, kernel threads can be preempted at any time. Traditional Unix
557 systems are ``nonpreemptible,'' that is, kernel threads can only be
558 preempted at points where they explicitly call into the scheduler.
559 (User programs can be preempted at any time in both models.) As you
560 might imagine, preemptible kernels require more explicit
563 You should have little need to set the interrupt state directly. Most
564 of the time you should use the other synchronization primitives
565 described in the following sections. The main reason to disable
566 interrupts is to synchronize kernel threads with external interrupt
567 handlers, which cannot sleep and thus cannot use most other forms of
568 synchronization (@pxref{External Interrupt Handling}).
570 Types and functions for disabling and enabling interrupts are in
571 @file{threads/interrupt.h}.
573 @deftp Type {enum intr_level}
574 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
575 disabled or enabled, respectively.
578 @deftypefun {enum intr_level} intr_get_level (void)
579 Returns the current interrupt state.
582 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
583 Turns interrupts on or off according to @var{level}. Returns the
584 previous interrupt state.
587 @deftypefun {enum intr_level} intr_enable (void)
588 Turns interrupts on. Returns the previous interrupt state.
591 @deftypefun {enum intr_level} intr_disable (void)
592 Turns interrupts off. Returns the previous interrupt state.
596 @subsubsection Semaphores
598 Pintos' semaphore type and operations are declared in
599 @file{threads/synch.h}.
601 @deftp {Type} {struct semaphore}
602 Represents a @dfn{semaphore}, a nonnegative integer together with two
603 operators that manipulate it atomically, which are:
607 ``Down'' or ``P'': wait for the value to become positive, then
611 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
615 A semaphore initialized to 0 may be used to wait for an event
616 that will happen exactly once. For example, suppose thread @var{A}
617 starts another thread @var{B} and wants to wait for @var{B} to signal
618 that some activity is complete. @var{A} can create a semaphore
619 initialized to 0, pass it to @var{B} as it starts it, and then
620 ``down'' the semaphore. When @var{B} finishes its activity, it
621 ``ups'' the semaphore. This works regardless of whether @var{A}
622 ``downs'' the semaphore or @var{B} ``ups'' it first.
624 A semaphore initialized to 1 is typically used for controlling access
625 to a resource. Before a block of code starts using the resource, it
626 ``downs'' the semaphore, then after it is done with the resource it
627 ``ups'' the resource. In such a case a lock, described below, may be
630 Semaphores can also be initialized to values larger than 1. These are
634 @deftypefun void sema_init (struct semaphore *@var{sema}, unsigned @var{value})
635 Initializes @var{sema} as a new semaphore with the given initial
639 @deftypefun void sema_down (struct semaphore *@var{sema})
640 Executes the ``down'' or ``P'' operation on @var{sema}, waiting for
641 its value to become positive and then decrementing it by one.
644 @deftypefun bool sema_try_down (struct semaphore *@var{sema})
645 Tries to execute the ``down'' or ``P'' operation on @var{sema},
646 without waiting. Returns true if @var{sema} had a positive value
647 that was successfully decremented, or false if it was already
648 zero and thus could not be decremented. Calling this function in a
649 tight loop wastes CPU time (use @func{sema_down} instead, or find a
653 @deftypefun void sema_up (struct semaphore *@var{sema})
654 Executes the ``up'' or ``V'' operation on @var{sema},
655 incrementing its value. If any threads are waiting on
656 @var{sema}, wakes one of them up.
659 Semaphores are internally built out of disabling interrupt
660 (@pxref{Disabling Interrupts}) and thread blocking and unblocking
661 (@func{thread_block} and @func{thread_unblock}). Each semaphore maintains
662 a list of waiting threads, using the linked list
663 implementation in @file{lib/kernel/list.c}.
668 Lock types and functions are declared in @file{threads/synch.h}.
670 @deftp {Type} {struct lock}
671 Represents a @dfn{lock}, a specialized semaphore with an initial value
672 of 1 (@pxref{Semaphores}). The difference between a lock and such a
673 semaphore is twofold. First, a semaphore does not have an owner,
674 meaning that one thread can ``down'' the semaphore and then another one
675 ``up'' it, but a single thread must both acquire and release a lock.
676 Second, a semaphore can have a value greater than 1, but a lock can only
677 be owned by a single thread at a time. If these restrictions prove
678 onerous, it's a good sign that a semaphore should be used, instead of a
681 Locks in Pintos are not ``recursive,'' that is, it is an error for the
682 thread currently holding a lock to try to acquire that lock.
685 @deftypefun void lock_init (struct lock *@var{lock})
686 Initializes @var{lock} as a new lock.
689 @deftypefun void lock_acquire (struct lock *@var{lock})
690 Acquires @var{lock} for use by the current thread, first waiting for
691 any current owner to release it if necessary.
694 @deftypefun bool lock_try_acquire (struct lock *@var{lock})
695 Tries to acquire @var{lock} for use by the current thread, without
696 waiting. Returns true if successful, false if the lock is already
697 owned. Calling this function in a tight loop is a bad idea because it
698 wastes CPU time (use @func{lock_acquire} instead).
701 @deftypefun void lock_release (struct lock *@var{lock})
702 Releases @var{lock}, which the current thread must own.
705 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
706 Returns true if the running thread owns @var{lock},
710 @node Condition Variables
711 @subsubsection Condition Variables
713 Condition variable types and functions are declared in
714 @file{threads/synch.h}.
716 @deftp {Type} {struct condition}
717 Represents a condition variable, which allows one piece of code to
719 and cooperating code to receive the signal and act upon it. Each
720 condition variable is associated with a lock. A given condition
721 variable is associated with only a single lock, but one lock may be
722 associated with any number of condition variables. A set of condition
723 variables taken together with their lock is called a ``monitor.''
725 A thread that owns the monitor lock is said to be ``in the monitor.''
726 The thread in the monitor has control over all the data protected by
727 the lock. It may freely examine or modify this data. If it discovers
728 that it needs to wait for some condition to become true, then it
729 ``waits'' on the associated condition, which releases the lock and
730 waits for the condition to be signaled. If, on the other hand, it has
731 caused one of these conditions to become true, it ``signals'' the
732 condition to wake up one waiter, or ``broadcasts'' the condition to
735 Pintos monitors are ``Mesa'' style, not
736 ``Hoare'' style. That is, sending and receiving a signal are not an
737 atomic operation. Thus, typically the caller must recheck the
738 condition after the wait completes and, if necessary, wait again.
741 @deftypefun void cond_init (struct condition *@var{cond})
742 Initializes @var{cond} as a new condition variable.
745 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{lock})
746 Atomically releases @var{lock} (the monitor lock) and waits for
747 @var{cond} to be signaled by some other piece of code. After
748 @var{cond} is signaled, reacquires @var{lock} before returning.
749 @var{lock} must be held before calling this function.
752 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
753 If any threads are waiting on @var{cond} (protected by monitor lock
754 @var{lock}), then this function wakes up one of them. If no threads are
755 waiting, returns without performing any action.
756 @var{lock} must be held before calling this function.
759 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
760 Wakes up all threads, if any, waiting on @var{cond} (protected by
761 monitor lock @var{lock}). @var{lock} must be held before calling this
765 @subsubheading Monitor Example
767 The classical example of a monitor is handling a buffer into which one
768 ``producer'' thread writes characters and out of which a second
769 ``consumer'' thread reads characters. To implement this case we need,
770 besides the monitor lock, two condition variables which we will call
771 @var{not_full} and @var{not_empty}:
774 char buf[BUF_SIZE]; /* @r{Buffer.} */
775 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
776 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
777 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
778 struct lock lock; /* @r{Monitor lock.} */
779 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
780 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
782 @dots{}@r{initialize the locks and condition variables}@dots{}
784 void put (char ch) @{
785 lock_acquire (&lock);
786 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
787 cond_wait (¬_full, &lock);
788 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
790 cond_signal (¬_empty, &lock); /* @r{@var{buf} can't be empty anymore.} */
791 lock_release (&lock);
796 lock_acquire (&lock);
797 while (n == 0) /* @r{Can't read @var{buf} as long as it's empty.} */
798 cond_wait (¬_empty, &lock);
799 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
801 cond_signal (¬_full, &lock); /* @r{@var{buf} can't be full anymore.} */
802 lock_release (&lock);
806 @node Memory Barriers
807 @subsubsection Memory Barriers
809 Suppose we add a ``feature'' that, whenever a timer interrupt
810 occurs, the character in global variable @code{timer_put_char} is
811 printed on the console, but only if global Boolean variable
812 @code{timer_do_put} is true.
814 If interrupts are enabled, this code for setting up @samp{x} to be
815 printed is clearly incorrect, because the timer interrupt could intervene
816 between the two assignments:
819 timer_do_put = true; /* INCORRECT CODE */
820 timer_put_char = 'x';
823 It might not be as obvious that the following code is just as
827 timer_put_char = 'x'; /* INCORRECT CODE */
831 The reason this second example might be a problem is that the compiler
832 is, in general, free to reorder operations when it doesn't have a
833 visible reason to keep them in the same order. In this case, the
834 compiler doesn't know that the order of assignments is important, so its
835 optimization pass is permitted to exchange their order.
836 There's no telling whether it will actually do this, and it is possible
837 that passing the compiler different optimization flags or changing
838 compiler versions will produce different behavior.
840 The following is @emph{not} a solution, because locks neither prevent
841 interrupts nor prevent the compiler from reordering the code within the
842 region where the lock is held:
845 lock_acquire (&timer_lock); /* INCORRECT CODE */
846 timer_put_char = 'x';
848 lock_release (&timer_lock);
851 Fortunately, real solutions do exist. One possibility is to
852 disable interrupts around the assignments. This does not prevent
853 reordering, but it makes the assignments atomic as observed by the
854 interrupt handler. It also has the extra runtime cost of disabling and
855 re-enabling interrupts:
858 enum intr_level old_level = intr_disable ();
859 timer_put_char = 'x';
861 intr_set_level (old_level);
864 A second possibility is to mark the declarations of
865 @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This
866 keyword tells the compiler that the variables are externally observable
867 and allows it less latitude for optimization. However, the semantics of
868 @samp{volatile} are not well-defined, so it is not a good general
871 Usually, the best solution is to use a compiler feature called a
872 @dfn{memory barrier}, a special statement that prevents the compiler
873 from reordering memory operations across the barrier. In Pintos,
874 @file{threads/synch.h} defines the @code{barrier()} macro as a memory
875 barrier. Here's how we would use a memory barrier to fix this code:
878 timer_put_char = 'x';
883 The compiler also treats invocation of any function defined externally,
884 that is, in another source file, as a limited form of a memory barrier.
885 Specifically, the compiler assumes that any externally defined function
886 may access any statically or dynamically allocated data and any local
887 variable whose address is taken. This often means that explicit
888 barriers can be omitted, and, indeed, this is why the base Pintos code
889 does not need any barriers.
891 A function defined in the same source file, or in a header included by
892 the source file, cannot be relied upon as a memory barrier.
893 This applies even to invocation of a function before its
894 definition, because the compiler may read and parse the entire source
895 file before performing optimization.
897 @node Interrupt Handling
898 @subsection Interrupt Handling
900 An @dfn{interrupt} notifies the CPU of some event. Much of the work
901 of an operating system relates to interrupts in one way or another.
902 For our purposes, we classify interrupts into two broad categories:
906 @dfn{External interrupts}, that is, interrupts originating outside the
907 CPU. These interrupts come from hardware devices such as the system
908 timer, keyboard, serial ports, and disks. External interrupts are
909 @dfn{asynchronous}, meaning that their delivery is not
910 synchronized with normal CPU activities. External interrupts
911 are what @func{intr_disable} and related functions
912 postpone (@pxref{Disabling Interrupts}).
915 @dfn{Internal interrupts}, that is, interrupts caused by something
916 executing on the CPU. These interrupts are caused by something
917 unusual happening during instruction execution: accessing invalid
918 memory (a @dfn{page fault}), executing invalid instructions, and
919 various other disallowed activities. Because they are caused by CPU
920 instructions, internal interrupts are @dfn{synchronous} or
921 synchronized with CPU instructions. @func{intr_disable} does not
922 disable internal interrupts.
925 Because the CPU treats all interrupts largely the same way, regardless
926 of source, Pintos uses the same infrastructure for both internal and
927 external interrupts, to a point. The following section describes this
928 common infrastructure, and sections after that give the specifics of
929 external and internal interrupts.
931 If you haven't already read chapter 3 in @bibref{IA32-v1}, it is
932 recommended that you do so now. You might also want to skim chapter 5
936 * Interrupt Infrastructure::
937 * Internal Interrupt Handling::
938 * External Interrupt Handling::
941 @node Interrupt Infrastructure
942 @subsubsection Interrupt Infrastructure
944 When an interrupt occurs while the kernel is running, the CPU saves
945 its most essential state on the stack and jumps to an interrupt
946 handler routine. The 80@var{x}86 architecture allows for 256 possible
947 interrupts, each of which can have its own handler. The handler for
948 each interrupt is defined in an array called the @dfn{interrupt
949 descriptor table} or IDT.
951 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
952 IDT so that each entry points to a unique entry point in
953 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
954 @var{NN} is the interrupt number in
955 hexadecimal. Because the CPU doesn't give
956 us any other way to find out the interrupt number, this entry point
957 pushes the interrupt number on the stack. Then it jumps to
958 @func{intr_entry}, which pushes all the registers that the processor
959 didn't already save for us, and then calls @func{intr_handler}, which
960 brings us back into C in @file{threads/interrupt.c}.
962 The main job of @func{intr_handler} is to call any function that has
963 been registered for handling the particular interrupt. (If no
964 function is registered, it dumps some information to the console and
965 panics.) It does some extra processing for external
966 interrupts that we'll discuss later.
968 When @func{intr_handler} returns, the assembly code in
969 @file{threads/intr-stubs.S} restores all the CPU registers saved
970 earlier and directs the CPU to return from the interrupt.
972 A few types and functions apply to both internal and external
975 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
976 This is how an interrupt handler function must be declared. Its @var{frame}
977 argument (see below) allows it to determine the cause of the interrupt
978 and the state of the thread that was interrupted.
981 @deftp {Type} {struct intr_frame}
982 The stack frame of an interrupt handler, as saved by CPU, the interrupt
983 stubs, and @func{intr_entry}. Its most interesting members are described
987 @deftypecv {Member} {@struct{intr_frame}} uint32_t edi
988 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esi
989 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebp
990 @deftypecvx {Member} {@struct{intr_frame}} uint32_t esp_dummy
991 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ebx
992 @deftypecvx {Member} {@struct{intr_frame}} uint32_t edx
993 @deftypecvx {Member} {@struct{intr_frame}} uint32_t ecx
994 @deftypecvx {Member} {@struct{intr_frame}} uint32_t eax
995 @deftypecvx {Member} {@struct{intr_frame}} uint16_t es
996 @deftypecvx {Member} {@struct{intr_frame}} uint16_t ds
997 Register values in the interrupted thread saved by @func{intr_entry}.
998 The @code{esp_dummy} value isn't actually used (refer to the
999 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
1002 @deftypecv {Member} {@struct{intr_frame}} uint32_t vec_no
1003 The interrupt vector number, ranging from 0 to 255.
1006 @deftypecv {Member} {@struct{intr_frame}} uint32_t error_code
1007 The ``error code'' pushed on the stack by the CPU for some internal
1011 @deftypecv {Member} {@struct{intr_frame}} void (*eip) (void)
1012 The address of the next instruction to be executed by the interrupted
1016 @deftypecv {Member} {@struct{intr_frame}} {void *} esp
1017 The interrupted thread's stack pointer.
1020 @deftypefun {const char *} intr_name (uint8_t @var{vec})
1021 Returns the name of the interrupt numbered @var{vec}, or
1022 @code{"unknown"} if the interrupt has no registered name.
1025 @node Internal Interrupt Handling
1026 @subsubsection Internal Interrupt Handling
1028 When an internal interrupt occurs, it is because the running kernel
1029 thread (or, starting from project 2, the running user process) has
1030 caused it. Thus, because it is related to a thread (or process), an
1031 internal interrupt is said to happen in a ``process context.''
1033 In an internal interrupt, it can make sense to examine the
1034 @struct{intr_frame} passed to the interrupt handler, or even to modify
1035 it. When the interrupt returns, modified members
1036 in @struct{intr_frame} become changes to the thread's registers.
1037 We'll use this in project 2 to return values from system call
1040 There are no special restrictions on what an internal interrupt
1041 handler can or can't do. Generally they should run with interrupts
1042 enabled, just like other code, and so they can be preempted by other
1043 kernel threads. Thus, they do need to synchronize with other threads
1044 on shared data and other resources (@pxref{Synchronization}).
1046 @deftypefun void intr_register_int (uint8_t @var{vec}, int @var{dpl}, enum intr_level @var{level}, intr_handler_func *@var{handler}, const char *@var{name})
1047 Registers @var{func} to be called when internal interrupt numbered
1048 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1051 If @var{level} is @code{INTR_OFF} then handling of further interrupts
1052 will be disabled while the interrupt is being processed. Interrupts
1053 should normally be turned on during the handling of an internal
1056 @var{dpl} determines how the interrupt can be
1057 invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
1058 kernel threads. Otherwise @var{dpl} should be 3, which allows user
1059 processes to invoke the interrupt as well (this is useful only
1060 starting with project 2).
1063 @node External Interrupt Handling
1064 @subsubsection External Interrupt Handling
1066 Whereas an internal interrupt runs in the context of the thread that
1067 caused it, external interrupts do not have any predictable context.
1068 They are asynchronous, so it can be invoked at any time that
1069 interrupts have not been enabled. We say that an external interrupt
1070 runs in an ``interrupt context.''
1072 In an external interrupt, the @struct{intr_frame} passed to the
1073 handler is not very meaningful. It describes the state of the thread
1074 or process that was interrupted, but there is no way to predict which
1075 one that is. It is possible, although rarely useful, to examine it, but
1076 modifying it is a recipe for disaster.
1078 The activities of an external interrupt handler are severely
1079 restricted. First, only one external interrupt may be processed at a
1080 time, that is, nested external interrupt handling is not supported.
1081 This means that external interrupts must be processed with interrupts
1082 disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
1083 enabled at any point during their execution.
1085 Second, an interrupt handler must not call any function that can
1086 sleep, which rules out @func{thread_yield}, @func{lock_acquire}, and
1087 many others. This is because external interrupts use space on the
1088 stack of the kernel thread that was running at the time the interrupt
1089 occurred. If the interrupt handler tried to sleep and that thread
1090 resumed, then the two uses of the single stack would interfere, which
1093 Because an external interrupt runs with interrupts disabled, it
1094 effectively monopolizes the machine and delays all other activities.
1095 Therefore, external interrupt handlers should complete as quickly as
1096 they can. Any activities that require much CPU time should instead
1097 run in a kernel thread, possibly a thread whose activity is triggered
1098 by the interrupt using some synchronization primitive.
1100 External interrupts are also special because they are controlled by a
1101 pair of devices outside the CPU called @dfn{programmable interrupt
1102 controllers}, @dfn{PICs} for short. When @func{intr_init} sets up the
1103 CPU's IDT, it also initializes the PICs for interrupt handling. The
1104 PICs also must be ``acknowledged'' at the end of processing for each
1105 external interrupt. @func{intr_handler} takes care of that by calling
1106 @func{pic_end_of_interrupt}, which sends the proper signals to the
1109 The following additional functions are related to external
1112 @deftypefun void intr_register_ext (uint8_t @var{vec}, intr_handler_func *@var{handler}, const char *@var{name})
1113 Registers @var{handler} to be called when external interrupt numbered
1114 @var{vec} is triggered. Names the interrupt @var{name} for debugging
1115 purposes. The handler will run with interrupts disabled.
1118 @deftypefun bool intr_context (void)
1119 Returns true if we are running in an interrupt context, otherwise
1120 false. Mainly used at the beginning of functions that might sleep
1121 or that otherwise should not be called from interrupt context, in this
1124 ASSERT (!intr_context ());
1128 @deftypefun void intr_yield_on_return (void)
1129 When called in an interrupt context, causes @func{thread_yield} to be
1130 called just before the interrupt returns. This is used, for example,
1131 in the timer interrupt handler to cause a new thread to be scheduled
1132 when a thread's time slice expires.
1135 @node Memory Allocation
1136 @subsection Memory Allocation
1138 Pintos contains two memory allocators, one that allocates memory in
1139 units of a page, and one that can allocate blocks of any size.
1146 @node Page Allocator
1147 @subsubsection Page Allocator
1149 The page allocator declared in @file{threads/palloc.h} allocates
1150 memory in units of a page. It is most often used to allocate memory
1151 one page at a time, but it can also allocate multiple contiguous pages
1154 The page allocator divides the memory it allocates into two pools,
1155 called the kernel and user pools. By default, each pool gets half of
1156 system memory, but this can be changed with a kernel command line
1157 option (@pxref{Why PAL_USER?}). An allocation request draws from one
1158 pool or the other. If one pool becomes empty, the other may still
1159 have free pages. The user pool should be used for allocating memory
1160 for user processes and the kernel pool for all other allocations.
1161 This will only become important starting with project 3. Until then,
1162 all allocations should be made from the kernel pool.
1164 Each pool's usage is tracked with a bitmap, one bit per page in
1165 the pool. A request to allocate @var{n} pages scans the bitmap
1166 for @var{n} consecutive bits set to
1167 false, indicating that those pages are free, and then sets those bits
1168 to true to mark them as used. This is a ``first fit'' allocation
1171 The page allocator is subject to fragmentation. That is, it may not
1172 be possible to allocate @var{n} contiguous pages even though @var{n}
1173 or more pages are free, because the free pages are separated by used
1174 pages. In fact, in pathological cases it may be impossible to
1175 allocate 2 contiguous pages even though @var{n} / 2 pages are free!
1176 Single-page requests can't fail due to fragmentation, so
1177 it is best to limit, as much as possible, the need for multiple
1180 Pages may not be allocated from interrupt context, but they may be
1183 When a page is freed, all of its bytes are cleared to @t{0xcc}, as
1184 a debugging aid (@pxref{Debugging Tips}).
1186 Page allocator types and functions are described below.
1188 @deftp {Type} {enum palloc_flags}
1189 A set of flags that describe how to allocate pages. These flags may
1190 be combined in any combination.
1193 @defvr {Page Allocator Flag} @code{PAL_ASSERT}
1194 If the pages cannot be allocated, panic the kernel. This is only
1195 appropriate during kernel initialization. User processes
1196 should never be permitted to panic the kernel.
1199 @defvr {Page Allocator Flag} @code{PAL_ZERO}
1200 Zero all the bytes in the allocated pages before returning them. If not
1201 set, the contents of newly allocated pages are unpredictable.
1204 @defvr {Page Allocator Flag} @code{PAL_USER}
1205 Obtain the pages from the user pool. If not set, pages are allocated
1206 from the kernel pool.
1209 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1210 Obtains and returns a single page, allocating it in the manner specified by
1211 @var{flags}. Returns a null pointer if no pages are
1215 @deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1216 Obtains @var{page_cnt} contiguous free pages, allocating them in the
1217 manner specified by @var{flags}, and returns them. Returns a null
1218 pointer if no pages are free.
1221 @deftypefun void palloc_free_page (void *@var{page})
1222 Frees @var{page}, which must have been obtained using
1223 @func{palloc_get_page} or @func{palloc_get_multiple}.
1226 @deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1227 Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
1228 All of the pages must have been obtained using @func{palloc_get_page}
1229 or @func{palloc_get_multiple}.
1232 @node Block Allocator
1233 @subsubsection Block Allocator
1235 The block allocator, declared in @file{threads/malloc.h}, can allocate
1236 blocks of any size. It is layered on top of the page allocator
1237 described in the previous section. Blocks returned by the block
1238 allocator are obtained from the kernel pool.
1240 The block allocator uses two different strategies for allocating
1241 memory. The first of these applies to ``small'' blocks, those 1 kB or
1243 fourth of the the page size). These allocations are rounded up to the
1244 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1245 grouped into a page used only for allocations of the smae
1248 The second strategy applies to allocating ``large'' blocks, those larger
1250 These allocations (plus a small amount of overhead) are rounded up to
1251 the nearest page in size, and then the block allocator requests that
1252 number of contiguous pages from the page allocator.
1254 In either case, the difference between the allocation requested size
1255 and the actual block size is wasted. A real operating system would
1256 carefully tune its allocator to minimize this waste, but this is
1257 unimportant in an instructional system like Pintos.
1259 As long as a page can be obtained from the page allocator, small
1260 allocations always succeed. Most small allocations will not require a
1261 new page from the page allocator at all. However, large allocations
1262 always require calling into the page allocator, and any allocation
1263 that needs more than one contiguous page can fail due to fragmentation,
1264 as already discussed in the previous section. Thus, you should
1265 minimize the number of large allocations in your code, especially
1266 those over approximately 4 kB each.
1268 The interface to the block allocator is through the standard C library
1269 functions @func{malloc}, @func{calloc}, and @func{free}.
1271 When a block is freed, all of its bytes are cleared to @t{0xcc}, as
1272 a debugging aid (@pxref{Debugging Tips}).
1274 The block allocator may not be called from interrupt context.