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. At any rate,
73 After the page table is initialized, we load the CPU's control
74 registers to turn on protected mode and paging, and then we set up the
75 segment registers. We aren't equipped to handle interrupts in
76 protected mode yet, so we disable interrupts.
78 Finally it's time to load the kernel from disk. We choose a simple,
79 although inflexible, method to do this: we program the IDE disk
80 controller directly. We assume that the kernel is stored starting
81 from the second sector of the first IDE disk (the first sector
82 contains the boot loader itself). We also assume that the BIOS has
83 already set up the IDE controller for us. We read
84 @code{KERNEL_LOAD_PAGES} 4 kB pages of data from the disk directly
85 into virtual memory starting @code{LOADER_KERN_BASE} bytes past
86 @code{LOADER_PHYS_BASE}, which by default means that we load the
87 kernel starting 1 MB into physical memory.
89 Then we jump to the start of the compiled kernel image. Using the
90 ``linker script'' in @file{threads/kernel.lds.S}, the kernel has
91 arranged that it begins with the assembly module
92 @file{threads/start.S}. This assembly module just calls
93 @func{main}, which never returns.
95 There's one more trick to the loader: the Pintos kernel command line
96 is stored in the boot loader. The @command{pintos} program actually
97 modifies the boot loader on disk each time it runs the kernel, putting
98 in whatever command line arguments the user supplies to the kernel,
99 and then the kernel at boot time reads those arguments out of the boot
100 loader in memory. This is something of a nasty hack, but it is simple
103 @node Kernel Initialization
104 @subsection Kernel Initialization
106 The kernel proper starts with the @func{main} function. The
107 @func{main} function is written in C, as will be most of the code we
108 encounter in Pintos from here on out.
110 When @func{main} starts, the system is in a pretty raw state. We're
111 in protected mode with paging enabled, but hardly anything else is
112 ready. Thus, the @func{main} function consists primarily of calls
113 into other Pintos modules' initialization functions. You should
114 notice that these are usually named @func{@var{module}_init}, where
115 @var{module} is the module's name, @file{@var{module}.c} is the
116 module's source code, and @file{@var{module}.h} is the module's
119 First we initialize kernel RAM in @func{ram_init}. The first step
120 is to clear out the kernel's so-called ``BSS'' segment. The BSS is a
121 segment that should be initialized to all zeros. In C, whenever you
122 declare a variable outside a function without providing an
123 initializer, that variable goes into the BSS.@footnote{This isn't
124 actually required by the ANSI C standard, but it is the case with most
125 implementations of C on most machines.} Because it's all zeros, the
126 BSS isn't stored in the image that the loader brought into memory. We
127 just use @func{memset} to zero it out. The other task of
128 @func{ram_init} is to read out the machine's memory size from where
129 the loader stored it and put it into the @code{ram_pages} variable for
132 Next, @func{thread_init} initializes the thread system. We will defer
133 full discussion to our discussion of Pintos threads below. It is
134 called so early in initialization because the console, initialized
135 just below, tries to use locks and locks in turn require there to be a
138 Then we initialize the console so that we can use @func{printf}.
139 @func{main} calls @func{vga_init}, which initializes the VGA text
140 display and clears the screen. It also calls @func{serial_init_poll}
141 to initialize the first serial port in ``polling mode,'' that is,
142 where the kernel busy-waits for the port to be ready for each
143 character to be output. (We use polling mode until we're ready to set
144 up interrupts later.) Finally we initialize the console device and
145 print a startup message to the console.
147 @func{main} calls @func{argv_init} to parse the kernel command line.
148 This entails reading the command line out of the loader and updating
149 global variables appropriately.
151 The next block of functions we call initialize the kernel's memory
152 system. @func{palloc_init} sets up the kernel page allocator, which
153 doles out memory one or more pages at a time. @func{malloc_init} sets
154 up the allocator that handles odd-sized allocations.
155 @func{paging_init} sets up a page table for the kernel.
157 In projects 2 and later, @func{main} also calls @func{tss_init} and
158 @func{gdt_init}, but we'll talk about those later.
160 @func{main} calls @func{random_init} to initialize the kernel random
161 number generator. @func{argv_init} might already have done this (if
162 the user specified @option{-rs} on the @command{pintos} command line)
163 but calling it a second time is harmless and has no effect.
165 We initialize the interrupt system in the next set of calls.
166 @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table}
167 (IDT) to ready it for interrupt handling, then @func{timer_init} and
168 @func{kbd_init} prepare us to handle timer interrupts and keyboard
169 interrupts, respectively. In projects 2 and later, we also prepare to
170 handle interrupts caused by user programs using @func{exception_init}
171 and @func{syscall_init}.
173 Now that interrupts are set up, we can start preemptively scheduling
174 threads with @func{thread_start}, which also enables interrupts.
175 Interrupt-driven serial port I/O is also possible now, so we use
176 @func{serial_init_queue} to switch to that mode.
178 If the filesystem is compiled in, as it will be in project 2 and
179 later, we now initialize the disks with @func{disk_init}, then the
180 filesystem with @func{filesys_init}, and run any operations that were
181 requested on the kernel command line with @func{fsutil_run}.
183 Boot is complete, so we print a message.
185 For project 1, now we execute @func{test}, which runs whatever test is
186 currently compiled into the kernel. For later projects, we will
187 instead run a user program and wait for it to complete.
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.
202 * Interrupt Handling::
203 * Memory Allocation::
207 @subsection @struct{thread}
209 The main Pintos data structure for threads is @struct{thread},
210 declared in @file{threads/thread.h}. @struct{thread} has these
211 members with the given type:
215 The thread's thread identifier or @dfn{tid}. Every thread must have a
216 tid that is unique over the entire lifetime of the kernel. By
217 default, @code{tid_t} is a @code{typedef} for @code{int} and each new
218 thread receives the numerically next higher tid, starting from 1 for
219 the initial process. You can change the type and the numbering scheme
222 @item enum thread_status status;
223 The thread's state, one of these:
227 The thread is running. Exactly one thread is running at a given time.
228 @func{thread_current} returns the running thread.
231 The thread is ready to run, but it's not running right now. The
232 thread could be selected to run the next time the scheduler is
233 invoked. Ready threads are kept in a doubly linked list called
237 The thread is waiting for something, e.g.@: a lock to become
238 available, an interrupt to be invoked. The thread won't be scheduled
239 again until it transitions to the @code{THREAD_READY} state with a
240 call to @func{thread_unblock}.
243 The thread will be destroyed by the scheduler after switching to the
248 The thread's name as a string, or at least the first few characters of
251 @item uint8_t *stack;
252 Every thread has its own stack to keep track of its state. When the
253 thread is running, the CPU's stack pointer register tracks the top of
254 the stack and this member is unused. But when the CPU switches to
255 another thread, this member saves the thread's stack pointer. No
256 other members are needed to save the thread's registers, because the
257 other registers that must be saved are saved on the stack.
260 A thread priority, ranging from the lowest possible priority
261 @code{PRI_MIN} (0) to the highest possible priority @code{PRI_MAX}
262 (59). Pintos as provided ignores thread priorities, but you will
263 implement priority scheduling in problem 1-3 (@pxref{Problem 1-3
264 Priority Scheduling}).
266 @item list_elem elem;
267 A ``list element'' used to put the thread into doubly linked lists,
268 either the list of threads ready to run or a list of threads waiting
269 on a semaphore. Take a look at @file{lib/kernel/list.h} for
270 information on how to use the Pintos doubly linked list ADT.
272 @item uint32_t *pagedir;
273 Only present in project 2 and later.
275 @item unsigned magic;
276 Always set to @code{THREAD_MAGIC}, which is just a random number
277 defined in @file{threads/thread.c}, and used to detect stack overflow.
278 See below for more information.
281 Every @struct{thread} occupies the beginning of its own page of
282 memory. The rest of the page is used for the thread's stack, which
283 grows downward from the end of the page. It looks like this:
286 4 kB +---------------------------------+
300 +---------------------------------+
306 0 kB +---------------------------------+
309 The upshot of this is twofold. First, @struct{thread} must not be
310 allowed to grow too big. If it does, then there will not be enough
311 room for the kernel stack. Our base @struct{thread} is only a few
312 bytes in size. It probably should stay well under 1 kB.
314 Second, kernel stacks must not be allowed to grow too large. If a
315 stack overflows, it will corrupt the thread state. Thus, kernel
316 functions should not allocate large structures or arrays as non-static
317 local variables. Use dynamic allocation with @func{malloc} or
318 @func{palloc_get_page} instead.
320 This brings us to the purpose of @struct{thread}'s @code{magic}
321 member. If a thread's stack does overflow, then @code{magic} will be
322 the first member of @struct{thread} to be overwritten, because it is
323 closest to the kernel stack. Thus, some of the thread functions
324 (notably @func{thread_current}) check that @code{magic} has the proper
327 @node Thread Functions
328 @subsection Thread Functions
330 @file{threads/thread.c} implements several public functions for thread
331 support. Let's take a look at the most useful:
333 @deftypefun void thread_init (void)
334 Called by @func{main} to initialize the thread system. Its main
335 purpose is to create a @struct{thread} for Pintos's initial thread.
336 This is possible because the Pintos loader sets up the initial
337 thread's stack at the end of a page. Before @func{thread_init} runs,
338 @func{thread_current} will fail because the running thread's
339 @code{magic} value is incorrect. Lots of functions call
340 @func{thread_current} directly or indirectly, including
341 @func{lock_acquire} for locking a lock, so @func{thread_init} is
342 called early in Pintos initialization.
345 @deftypefun void thread_start (void)
346 Called by @func{main} to start the scheduler. Creates the idle
347 thread, that is, the thread that is scheduled when no other thread is
348 ready. Then enables interrupts, which enables the scheduler because
349 processes are rescheduled in the return path from the timer
353 @deftypefun void thread_create (const char *@var{name}, int @var{priority}, thread_func *@var{func}, void *@var{aux})
354 Creates and starts a new thread named @var{name} with the given
355 @var{priority}, returning the new thread's tid. The thread executes
356 @var{func}, passing @var{aux} as the function's single argument.
358 @func{thread_create} works by allocating a page for the thread's
359 @struct{thread} and stack and initializing its members, then setting
360 up a set of fake stack frames for it (we'll talk more about this
361 later). The thread was initialized in the blocked state, so the final
362 action before returning is to unblock it, allowing the new thread to
366 @deftypefun void thread_block (void)
367 Transitions the running thread from the running state to the blocked
368 state. This thread will not run again until @func{thread_unblock} is
369 called on it, so you'd better have some way arranged for that to
373 @deftypefun void thread_unblock (struct thread *@var{thread})
374 Transitions @var{thread}, which must be in the blocked state, to the
375 ready state, allowing it to continue to run. This is called when the
376 event that the thread is waiting for happens, such as the lock that
377 the thread is waiting on becoming available.
380 @deftypefun struct thread *thread_current (void)
381 Returns the running thread.
384 @deftypefun void thread_exit (void) NO_RETURN
385 Causes the current thread to exit. Never returns (hence
386 @code{NO_RETURN}: @pxref{UNUSED NO_RETURN NO_INLINE PRINTF_FORMAT}).
389 @deftypefun void thread_yield (void)
390 Yields the CPU to the scheduler, which picks a new thread to run. The
391 new thread might be the current thread, so you can't depend on this
392 function to keep this thread from running for any particular length of
396 @node Thread Switching
397 @subsection Thread Switching
399 @func{schedule} is the function responsible for switching threads. It
400 is internal to @file{threads/thread.c} and called only by the three
401 public thread functions that need to switch threads:
402 @func{thread_block}, @func{thread_exit}, and @func{thread_yield}.
403 Before these functions call @func{schedule}, they all disable
404 interrupts (or ensure that they are already disabled) and then change
405 the running thread's state to something other than running.
407 The actual @func{schedule} implementation is simple. It records the
408 current thread in local variable @var{cur}, determines the next thread
409 to run as local variable @var{next} (by calling
410 @func{next_thread_to_run}, and then calls @func{switch_threads} to do
411 the actual thread switch. The thread we switched to was also running
412 inside @func{switch_threads}, as are all the threads not currently
413 running in Pintos, so the new thread now returns out of
414 @func{switch_threads}, returning the previously running thread.
416 @func{switch_threads} is an assembly language routine in
417 @file{threads/switch.S}. It saves registers on the stack, stores the
418 CPU's current stack pointer into the current @struct{thread}'s @code{stack}
419 member, restores the new thread's @code{stack} into the CPU's stack
420 pointer, restores registers from the stack, and returns.
422 The rest of the scheduler is implemented as @func{schedule_tail}. It
423 marks the new thread as running. If the thread we just switched from
424 is in the dying state, then it also frees the page that contained the
425 dying thread's @struct{thread} and stack, which couldn't be freed
426 before the thread switch because the switch needed to use it.
428 Running a thread for the first time is a special case. When
429 @func{thread_create} creates a new thread, it goes through a fair
430 amount of trouble to get it started properly. In particular, a new
431 thread hasn't started running yet, so there's no way for it to be
432 running inside @func{switch_threads} as the scheduler expects. To
433 solve the problem, @func{thread_create} creates some fake stack frames
434 in the new thread's stack:
438 The topmost fake stack frame is for @func{switch_threads}, represented
439 by @struct{switch_threads_frame}. The important part of this frame is
440 its @code{eip} member, the return address. We point @code{eip} to
444 The next fake stack frame is for @func{switch_entry}, an assembly
445 language routine in @file{threads/switch.S} that adjusts the stack
446 pointer,@footnote{This is because @func{switch_threads} takes
447 arguments on the stack and the 80@var{x}86 SVR4 calling convention
448 requires the caller, not the called function, to remove them when the
449 call is complete. See @bibref{SysV-i386} chapter 3 for details.}
450 calls @func{schedule_tail} (this special case is why
451 @func{schedule_tail} is separate from @func{schedule}), and returns.
452 We fill in its stack frame so that it returns into
453 @func{kernel_thread}, a function in @file{threads/thread.c}.
456 The final stack frame is for @func{kernel_thread}, which enables
457 interrupts and calls the thread's function (the function passed to
458 @func{thread_create}). If the thread's function returns, it calls
459 @func{thread_exit} to terminate the thread.
462 @node Synchronization
463 @subsection Synchronization
465 Situations often arise in threaded programs in which threads want to
466 share resources. If resource sharing is not handled in a careful,
467 controlled fashion, then threads can end up making a big mess.
468 This is especially the case in operating system kernels, where
469 faulty sharing can crash the entire machine. Pintos provides several
470 synchronization primitives to help out.
473 * Disabling Interrupts::
476 * Condition Variables::
479 @node Disabling Interrupts
480 @subsubsection Disabling Interrupts
482 The crudest way to do synchronization is to disable interrupts, that
483 is, to temporarily prevent the CPU from responding to interrupts. If
484 interrupts are off, no other thread will preempt the running thread,
485 because thread preemption is driven by the timer interrupt. If
486 interrupts are on, as they normally are, then the running thread may
487 be preempted by another at any time, whether between two C statements
488 or even within the execution of one.
490 Incidentally, this means that Pintos is a ``preemptible kernel,'' that
491 is, kernel threads can be preempted at any time. Traditional Unix
492 systems are ``nonpreemptible,'' that is, kernel threads can only be
493 preempted at points where they explicitly call into the scheduler.
494 User programs can be preempted at any time in both models. As you
495 might imagine, preemptible kernels require more use of
498 You should have little need to set the interrupt state directly. Most
499 of the time you should use the other synchronization primitives
500 described in the following sections.
502 Types and functions for disabling and enabling interrupts are in
503 @file{threads/interrupt.h}.
505 @deftp Type {enum intr_level}
506 One of @code{INTR_OFF} or @code{INTR_ON}, denoting that interrupts are
507 disabled or enabled, respectively.
510 @deftypefun {enum intr_level} intr_get_level (void)
511 Returns the current interrupt state.
514 @deftypefun {enum intr_level} intr_set_level (enum intr_level @var{level})
515 Turns interrupts on or off according to @var{level} and returns the
516 previous interrupt state.
519 @deftypefun {enum intr_level} intr_enable (void)
520 Turns interrupts on and returns the previous interrupt state.
523 @deftypefun {enum intr_level} intr_disable (void)
524 Turns interrupts off and returns the previous interrupt state.
528 @subsubsection Semaphores
530 A semaphore is a nonnegative integer along with two atomic operators
531 for manipulating it, which are:
535 ``Down'' or ``P'': wait for the value to become positive, then
539 ``Up'' or ``V'': increment the value (and wake up one waiting thread,
543 A semaphore initialized to 1 is typically used for controlling access
544 to a resource. Before a block of code starts using the resource, it
545 ``downs'' the semaphore, then after it is done with the resource it
546 ``ups'' the resource. In such a case a lock, described below, may be
549 A semaphore initialized to 0 can be useful for waiting for an event
550 that will happen exactly once. For example, suppose thread @var{A}
551 starts another thread @var{B} and wants to wait for @var{B} to signal
552 that some activity is complete. @var{A} can create a semaphore
553 initialized to 0, pass it to @var{B}, and then ``down'' the semaphore.
554 When @var{B} finishes its activity, it ``ups'' the semaphore.
556 Pintos declared its semaphore type and operations on them in
557 @file{threads/synch.h}.
559 @deftp {Type} {struct semaphore}
560 Represents a semaphore.
563 @deftypefun void sema_init (struct semaphore *sema, unsigned value, const char *name)
564 Initializes @var{sema} as a new semaphore with the given initial
565 @var{value}. Gives @var{sema} the specified @var{name} for use in
569 @deftypefun void sema_down (struct semaphore *@var{sema})
570 Executes the ``down'' or ``P'' operation on the semaphore, waiting for
571 its value to become positive and then decrementing it by one.
574 @deftypefun void sema_up (struct semaphore *@var{sema})
575 Increments @var{sema}'s value. If any threads are waiting on
576 @var{sema}, wakes one of them up.
579 Semaphores are internally built out of interrupt disabling
580 (@pxref{Disabling Interrupts}), thread blocking and unblocking
581 (@func{thread_block} and @func{thread_unblock}). Semaphores maintain
582 a doubly linked list of waiting threads using the linked list
583 implementation in @file{lib/kernel/list.c}.
588 A lock is a specialization of a semaphore (@pxref{Semaphores}) with an
589 initial value of 1. The difference between a lock and such a
590 semaphore is twofold. First, a semaphore can have a value greater
591 than 1, but a lock can only be owned by a single thread at a time.
592 Second, a semaphore does not have an owner, meaning that one thread
593 can ``down'' the semaphore and then another one ``up'' it, but with a
594 lock the same thread must both acquire and release it. When these
595 restrictions prove onerous, it's a good sign that a semaphore should
596 be used, instead of a lock.
598 Locks in Pintos are not ``recursive,'' that is, it is an error for the
599 thread currently holding a lock to try to acquire that lock.
601 Lock types and functions are declared in @file{threads/synch.h}.
603 @deftp {Type} {struct lock}
607 @deftypefun void lock_init (struct lock *@var{lock}, const char *@var{name})
608 Initializes @var{lock} as a new lock and gives it the specified
609 @var{name} for use in debugging.
612 @deftypefun void lock_acquire (struct lock *@var{lock})
613 Acquires @var{lock} for use by the current thread, first waiting for
614 any current owner to release it if necessary.
617 @deftypefun void lock_release (struct lock *@var{lock})
618 Releases @var{lock}, which the current thread must own.
621 @deftypefun bool lock_held_by_current_thread (const struct lock *@var{lock})
622 Returns true if the running thread owns @var{lock},
626 @node Condition Variables
627 @subsubsection Condition Variables
629 A condition variable allows one piece of code to signal a condition
630 and cooperating code to receive the signal and act upon it. Each
631 condition variable is associated with a lock. A given condition
632 variable is associated with only a single lock, but one lock may be
633 associated with any number of condition variables. A lock along with
634 all of its condition variables is known as a ``monitor.''
636 A thread that owns the monitor lock is said to be ``in the monitor.''
637 The thread in the monitor has control over all the data protected with
638 the lock. It may freely examine or modify this data. If it discovers
639 that it needs to wait for some condition to become true, then it
640 ``waits'' on the associated condition, which releases the lock and
641 waits for the condition to be signaled. If it, on the other hand, has
642 caused one of these conditions to become true, it ``signals'' the
643 condition to wake up one waiter, or ``broadcasts'' the condition to
646 The classical example of a monitor is handling a buffer into which one
647 ``producer'' thread writes characters and out of which a second
648 ``consumer'' thread reads characters. To implement this case we need,
649 besides the monitor lock, two condition variables which we will call
650 @var{not_full} and @var{not_empty}:
653 char buf[BUF_SIZE]; /* @r{Buffer.} */
654 size_t n = 0; /* @r{0 <= n <= @var{BUF_SIZE}: # of characters in buffer.} */
655 size_t head = 0; /* @r{@var{buf} index of next char to write (mod @var{BUF_SIZE}).} */
656 size_t tail = 0; /* @r{@var{buf} index of next char to read (mod @var{BUF_SIZE}).} */
657 struct lock lock; /* @r{Monitor lock.} */
658 struct condition not_empty; /* @r{Signaled when the buffer is not empty.} */
659 struct condition not_full; /* @r{Signaled when the buffer is not full.} */
661 @dots{}@r{initialize the locks and condition variables}@dots{}
663 void put (char ch) @{
664 lock_acquire (&lock);
665 while (n == BUF_SIZE) /* @r{Can't add to @var{buf} as long as it's full.} */
666 cond_wait (¬_full);
667 buf[head++ % BUF_SIZE] = ch; /* @r{Add @var{ch} to @var{buf}.} */
669 cond_signal (¬_empty); /* @r{@var{buf} can't be empty anymore.} */
670 lock_release (&lock);
675 lock_acquire (&lock);
676 while (n == 0) /* @r{Can't read from @var{buf} as long as it's empty.} */
677 cond_wait (¬_empty);
678 ch = buf[tail++ % BUF_SIZE]; /* @r{Get @var{ch} from @var{buf}.} */
680 cond_signal (¬_full); /* @r{@var{buf} can't be full anymore.} */
681 lock_release (&lock);
685 As the code above illustrates, Pintos monitors are ``Mesa'' style, not
686 ``Hoare'' style, that is, sending and receiving a signal are not an
687 atomic operation. Thus, typically the caller must recheck the
688 condition after the wait completes and, if necessary, wait again.
690 Condition variable types and functions are declared in
691 @file{threads/synch.h}.
693 @deftp {Type} {struct condition}
694 Represents a condition variable.
697 @deftypefun void cond_init (struct condition *@var{cond}, const char *@var{name})
698 Initializes @var{cond} as a new condition variable and gives it the
699 specified @var{name} for use in debugging.
702 @deftypefun void cond_wait (struct condition *@var{cond}, struct lock *@var{name})
703 Atomically releases @var{lock} (the monitor lock) and waits for
704 @var{cond} to be signaled by some other piece of code. After
705 @var{cond} is signaled, @var{lock} is reacquired before returning.
706 @var{lock} must be held before calling this function.
709 @deftypefun void cond_signal (struct condition *@var{cond}, struct lock *@var{lock})
710 If any threads are waiting on @var{cond} (protected by monitor lock
711 @var{lock}), then this function signals one of them to wake up from
712 its wait. @var{lock} must be held before calling this function.
715 @deftypefun void cond_broadcast (struct condition *@var{cond}, struct lock *@var{lock})
716 Wakes up all threads, if any, waiting on @var{cond} (protected by
717 monitor lock @var{lock}). @var{lock} must be held before calling this
721 @node Interrupt Handling
722 @subsection Interrupt Handling
724 An @dfn{interrupt} notifies the CPU of some event. Much of the work
725 of an operating system relates to interrupts in one way or another.
726 For our purposes, we classify interrupts into two broad categories:
730 @dfn{External interrupts}, that is, interrupts originating outside the
731 CPU. These interrupts come from hardware devices such as the system
732 timer, keyboard, serial ports, and disks. External interrupts are
733 @dfn{asynchronous}, meaning that they don't occur in a fashion
734 synchronized with anything going on in the CPU. External interrupts
735 are what @func{intr_disable} and related functions can arrange to
736 temporarily ignore (@pxref{Disabling Interrupts}).
739 @dfn{Internal interrupts}, that is, interrupts caused by something
740 executing on the CPU. These interrupts are caused by something
741 unusual happening during instruction execution: accessing invalid
742 memory (a @dfn{page fault}), executing invalid instructions, and
743 various other disallowed activities. Because they are caused by CPU
744 instructions, internal interrupts are @dfn{synchronous} or
745 synchronized with CPU instructions. @func{intr_disable} does not
746 disable internal interrupts.
749 Because the CPU treats all interrupts largely the same way, regardless
750 of source, Pintos uses the same infrastructure for both internal and
751 external interrupts, up to a point. The next section describes this
752 common infrastructure. But external and internal interrupts are
753 actually quite different, so we also follow up that section with one
754 specific to each category.
756 If you haven't already read chapter 3 in @bibref{IA32-v1}, it is
757 recommended that you do so now. You might also want to skim chapter 5
761 * Interrupt Infrastructure::
762 * Internal Interrupt Handling::
763 * External Interrupt Handling::
766 @node Interrupt Infrastructure
767 @subsubsection Interrupt Infrastructure
769 When an interrupt occurs while the kernel is running, the CPU saves
770 its most essential state on the stack and jumps to an interrupt
771 handler routine. The 80@var{x}86 architecture allows for 256 possible
772 interrupts, each of which can have its own handler. The handler for
773 each interrupt is defined in an array called the @dfn{interrupt
774 descriptor table} or IDT.
776 In Pintos, @func{intr_init} in @file{threads/interrupt.c} sets up the
777 IDT so that each entry points to a unique entry point in
778 @file{threads/intr-stubs.S} named @func{intr@var{NN}_stub}, where
779 @var{NN} is the interrupt number in
780 hexadecimal.@footnote{@file{threads/intr-stubs.S} is so repetitive
781 that it is actually generated by a Perl script,
782 @file{threads/intr-stubs.pl}. Thus, you will actually find
783 @file{threads/intr-stubs.S} in your @file{threads/build/threads}
784 directory, not in plain @file{threads}.} Because the CPU doesn't give
785 us any other way to find out the interrupt number, this entry point
786 pushes the interrupt number on the stack. Then it jumps to
787 @func{intr_entry}, which pushes all the registers that the processor
788 didn't save for us, and then calls @func{intr_handler}, which
789 brings us back into C in @file{threads/interrupt.c}.
791 The main job of @func{intr_handler} is to call any function that has
792 been registered for handling the particular interrupt. (If there's no
793 function registered, it dumps some information to the console and
794 panics the kernel.) It does some extra processing for external
795 interrupts that we'll discuss later.
797 When @func{intr_handler} returns, the assembly code in
798 @file{threads/intr-stubs.S} restores all the CPU registers saved
799 earlier and directs the CPU to return from the interrupt.
801 A few types and functions apply to both internal and external
804 @deftypefun void intr_register (uint8_t @var{vec}, int @var{dpl}, enum intr_level @var{level}, intr_handler_func *@var{func}, const char *@var{name})
805 Registers @var{func} to be called when the interrupt numbered
806 @var{vec} is triggered. Names the interrupt @var{name} for debugging
809 If @var{level} is @code{INTR_OFF} then handling of further interrupts
810 will be disabled while the interrupt is being processed. If @var{vec}
811 denotes an external interrupt, then @var{level} must be
812 @code{INTR_OFF}. Otherwise, interrupts should normally be turned on
813 during the handling of an internal interrupt.
815 For internal interrupts, @var{dpl} determines how the interrupt can be
816 invoked. If @var{dpl} is 0, then the interrupt can be invoked only by
817 kernel threads. Otherwise @var{dpl} should be 3, which allows user
818 processes to invoke the interrupt as well (this is useful only
819 starting with project 2). @var{dpl} has no effect on external
823 @deftp {Type} {void intr_handler_func (struct intr_frame *@var{frame})}
824 This is the type of an interrupt handler function. Its @var{frame}
825 argument (see below) allows it to determine the cause of the interrupt
826 and the state of the thread that was interrupted.
829 @deftp {Type} {struct intr_frame}
830 The stack frame of an interrupt handler. Its most interesting members
836 @item uint32_t esp_dummy;
843 Register values in the interrupted thread saved by @func{intr_entry}.
844 The @code{esp_dummy} value isn't actually used (refer to the
845 description of @code{PUSHA} in @bibref{IA32-v2b} for details).
847 @item uint32_t vec_no;
848 The interrupt vector number, ranging from 0 to 255.
850 @item uint32_t error_code;
851 The ``error code'' pushed on the stack by the CPU for some internal
854 @item void (*eip) (void);
855 The address of the next instruction to be executed by the interrupted
859 The interrupted thread's stack pointer.
863 @deftypefun {const char *} intr_name (uint8_t @var{vec})
864 Returns the registered name of the interrupt numbered @var{vec}, or
865 @code{"unknown"} if the interrupt's name is not known.
868 @node Internal Interrupt Handling
869 @subsubsection Internal Interrupt Handling
871 When an internal interrupt occurs, it is because the running kernel
872 thread (or, starting from project 2, the running user process) has
873 caused it. Thus, because it is related to a thread (or process), an
874 internal interrupt is said to happen in a ``process context.''
876 In an internal interrupt, it can make sense to examine the
877 @struct{intr_frame} passed to the interrupt handler. In cases where
878 the interrupted thread intentionally caused the interrupt, it can even
879 make sense to modify it. When the interrupt returns, modified members
880 in @struct{intr_frame} become changes to the thread's registers.
881 We'll use this in project 2 to return values from system call
884 There are no special restrictions on what an internal interrupt
885 handler can or can't do. Generally they should run with interrupts
886 enabled, just like other code, and so they can be preempted by other
887 kernel threads. Thus, they do need to synchronize with other threads
888 on shared data and other resources (@pxref{Synchronization}).
890 @node External Interrupt Handling
891 @subsubsection External Interrupt Handling
893 Whereas an internal interrupt runs in the context of the thread that
894 caused it, external interrupts do not have any predictable context.
895 They are asynchronous, so it can be invoked at any time that
896 interrupts have not been enabled. We say that an external interrupt
897 runs in an ``interrupt context.''
899 In an external interrupt, the @struct{intr_frame} passed to the
900 handler is not very meaningful. It describes the state of the thread
901 or process that was interrupted, but there is no way to predict which
902 one that is. It is possible, though rarely useful, to examine it, but
903 modifying it is a recipe for disaster.
905 The activities of an external interrupt handler are severely
906 restricted. First, only one external interrupt may be processed at a
907 time, that is, nested external interrupt handling is not supported.
908 This means that external interrupts must be processed with interrupts
909 disabled (@pxref{Disabling Interrupts}) and that interrupts may not be
910 enabled at any point during their execution.
912 Second, an interrupt handler must not call any function that can
913 sleep, which includes @func{thread_yield}, @func{lock_acquire}, and
914 many others. This is because external interrupts use space on the
915 stack of the kernel thread that was running at the time the interrupt
916 occurred. If the interrupt handler tried to sleep and that thread
917 resumed, then the two uses of the single stack would interfere, which
920 Because an external interrupt runs with interrupts disabled, it
921 effectively monopolizes the machine and delays all other activities.
922 Therefore, external interrupt handlers should complete as quickly as
923 they can. Any activities that require much CPU time should instead
924 run in a kernel thread, possibly a thread whose activity is triggered
925 by the interrupt using some synchronization primitive.
927 External interrupts are also special because they are controlled by a
928 device external to the CPU called a @dfn{programmable interrupt
929 controller} or @dfn{PIC} for short. When @func{intr_init} sets up the
930 CPU's IDT, it also initializes the PIC for interrupt handling. The
931 PIC also has to be ``acknowledged'' at the end of processing for each
932 external interrupt. @func{intr_handler} takes care of that by calling
933 @func{pic_end_of_interrupt}, which sends the proper signals to the
936 The following additional interrupts functions are related to external
939 @deftypefun bool intr_context (void)
940 Returns true if we are running in an interrupt context and false
941 otherwise. Mainly used at the beginning of functions that might sleep
942 or that otherwise should not be, in this form:
944 ASSERT (!intr_context ());
948 @deftypefun intr_yield_on_return (void)
949 When called in an interrupt context, causes @func{thread_yield} to be
950 called just before the interrupt returns. This is used, for example,
951 in the timer interrupt handler to cause a new thread to be scheduled
955 @node Memory Allocation
956 @subsection Memory Allocation
958 Pintos contains two memory allocators, one that allocates memory in
959 units of a page, and one that can allocate blocks of any size.
966 @node Page Allocation
967 @subsubsection Page Allocation
969 The page allocator declared in @file{threads/palloc.h} allocates
970 memory in units of a page. It is most often used to allocate memory
971 one page at a time, but it can also allocate multiple contiguous pages
974 The page allocator divides the memory it allocates into two pools,
975 called the kernel and user pools. By default, each pool gets half of
976 system memory, but this can be changed with a kernel command line
977 option (@pxref{Why PAL_USER?}). An allocation request draws from one
978 pool or the other. If one pool becomes empty, the other may still
979 have free pages. The user pool should be used for allocating memory
980 for user processes and the kernel pool for all other allocations.
981 This will only become important starting with project 3. Until then,
982 all allocations should be made from the kernel pool.
984 Each pools is managed with a bitmap of used pages, one bit per page in
985 the pool. An allocation request for @var{n} pages scans the bitmap,
986 starting from the beginning, for @var{n} consecutive bits set to
987 false, indicating that those pages are free, and then sets those bits
988 to true to mark them as now used. This is a ``first fit'' allocation
991 The page allocator is subject to fragmentation. That is, it may not
992 be possible to allocate @var{n} contiguous pages even though @var{n}
993 or more pages are free, because the free pages are separated by used
994 pages. In fact, in pathological cases it may be impossible to
995 allocate 2 contiguous pages even though @var{n} / 2 pages are free!
996 However, single-page requests can't fail due to fragmentation. Thus,
997 it is best to limit the need to allocate more than one contiguous page
1000 The interesting page allocator types and functions are described
1003 @deftp {Type} {enum palloc_flags}
1004 A set of flags that describe how to allocate pages. These flags may
1005 be combined in any combination:
1009 If the pages cannot be allocated, panic the kernel. This is only
1010 appropriate during kernel initialization, because user processes
1011 should never be permitted to panic the kernel.
1014 Clear the pages to all zeros before returning them. If not set,
1015 newly allocated pages' contents are unpredictable.
1018 Obtain the pages from the user pool. If not set, pages are allocated
1019 from the kernel pool.
1023 @deftypefun {void *} palloc_get_page (enum palloc_flags @var{flags})
1024 Obtains a single free page, allocating it in the manner specified by
1025 @var{flags}, and returns it. Returns a null pointer if no pages are
1029 @deftypefun {void *} palloc_get_multiple (enum palloc_flags @var{flags}, size_t @var{page_cnt})
1030 Obtains @var{page_cnt} contiguous free pages, allocating them in the
1031 manner specified by @var{flags}, and returns them. Returns a null
1032 pointer if no pages are free.
1035 @deftypefun void palloc_free_page (void *@var{page})
1036 Frees @var{page}, which must have been obtained using
1037 @func{palloc_get_page} or @func{palloc_get_multiple}.
1040 @deftypefun void palloc_free_multiple (void *@var{pages}, size_t @var{page_cnt})
1041 Frees the @var{page_cnt} contiguous pages starting at @var{pages}.
1042 All of the pages must have been obtained using @func{palloc_get_page}
1043 or @func{palloc_get_multiple}.
1046 @node Block Allocator
1047 @subsubsection Block Allocator
1049 The block allocator, declared in @file{threads/malloc.h}, can allocate
1050 blocks of any size. It is layered on top of the page allocator
1051 described in the previous section. Blocks returned by the block
1052 allocator are obtained from the kernel pool.
1054 The block allocator uses two different strategies for allocating
1055 memory. The first of these applies to blocks no larger than 1 kB (one
1056 fourth of the the page size). These allocations are rounded up to the
1057 nearest power of 2, or 16 bytes, whichever is larger. Then they are
1058 grouped into a page used only for allocations of that power of 2
1061 A different strategy applies to allocating blocks larger than 1 kB.
1062 These allocations (plus a small amount of overhead) are rounded up to
1063 the nearest page in size, and then the block allocator requests that
1064 number of contiguous pages from the page allocator.
1066 In either case, the difference between the allocation requested size
1067 and the actual block size is wasted. A real operating system would
1068 carefully tune its allocator to minimize this waste, but this is
1069 unimportant in an instructional system like Pintos.
1071 As long as a page can be obtained from the page allocator, small
1072 allocations always succeed. Most small allocations will not require a
1073 new page from the page allocator at all. However, large allocations
1074 always require calling into the page allocator, and any allocation
1075 that needs more than one contiguous page can fail due to fragmentation,
1076 as already discussed in the previous section. Thus, you should
1077 minimize the number of large allocations in your code, especially
1078 those over approximately 4 kB each.
1080 The interface to the block allocator is through the standard C library
1081 functions @func{malloc}, @func{calloc}, and @func{free}.