X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=doc%2Freference.texi;h=3d7d9bcbd2bbb2df58152293f4b09173cb60aff4;hb=cf90ac565e9533a17c5d4edff1e250a312396184;hp=bc0e3ad156190a3ac7d680fa101d2db9d9d4365e;hpb=2c1c5ee2a8df5b9282b17b596bf48cbc33462478;p=pintos-anon diff --git a/doc/reference.texi b/doc/reference.texi index bc0e3ad..3d7d9bc 100644 --- a/doc/reference.texi +++ b/doc/reference.texi @@ -177,7 +177,9 @@ The next set of calls initializes the interrupt system. @func{intr_init} sets up the CPU's @dfn{interrupt descriptor table} (IDT) to ready it for interrupt handling (@pxref{Interrupt Infrastructure}), then @func{timer_init} and @func{kbd_init} prepare for -handling timer interrupts and keyboard interrupts, respectively. In +handling timer interrupts and keyboard interrupts, respectively. +@func{input_init} sets up to merge serial and keyboard input into one +stream. In projects 2 and later, we also prepare to handle interrupts caused by user programs using @func{exception_init} and @func{syscall_init}. @@ -550,7 +552,7 @@ synchronization primitives to help out. * Semaphores:: * Locks:: * Monitors:: -* Memory Barriers:: +* Optimization Barriers:: @end menu @node Disabling Interrupts @@ -842,59 +844,88 @@ char get (void) @{ @} @end example -@node Memory Barriers -@subsection Memory Barriers +Note that @code{BUF_SIZE} must divide evenly into @code{SIZE_MAX + 1} +for the above code to be completely correct. Otherwise, it will fail +the first time @code{head} wraps around to 0. In practice, +@code{BUF_SIZE} would ordinarily be a power of 2. + +@node Optimization Barriers +@subsection Optimization Barriers @c We should try to come up with a better example. @c Perhaps something with a linked list? -Suppose we add a ``feature'' that, whenever a timer interrupt -occurs, the character in global variable @code{timer_put_char} is -printed on the console, but only if global Boolean variable -@code{timer_do_put} is true. +An @dfn{optimization barrier} is a special statement that prevents the +compiler from making assumptions about the state of memory across the +barrier. The compiler will not reorder reads or writes of variables +across the barrier or assume that a variable's value is unmodified +across the barrier, except for local variables whose address is never +taken. In Pintos, @file{threads/synch.h} defines the @code{barrier()} +macro as an optimization barrier. -If interrupts are enabled, this code for setting up @samp{x} to be -printed is clearly incorrect, because the timer interrupt could intervene -between the two assignments: +One reason to use an optimization barrier is when data can change +asynchronously, without the compiler's knowledge, e.g.@: by another +thread or an interrupt handler. The @func{too_many_loops} function in +@file{devices/timer.c} is an example. This function starts out by +busy-waiting in a loop until a timer tick occurs: @example -timer_do_put = true; /* INCORRECT CODE */ -timer_put_char = 'x'; +/* Wait for a timer tick. */ +int64_t start = ticks; +while (ticks == start) + barrier (); @end example -It might not be as obvious that the following code is just as -incorrect: +@noindent +Without an optimization barrier in the loop, the compiler could +conclude that the loop would never terminate, because @code{start} and +@code{ticks} start out equal and the loop itself never changes them. +It could then ``optimize'' the function into an infinite loop, which +would definitely be undesirable. + +Optimization barriers can be used to avoid other compiler +optimizations. The @func{busy_wait} function, also in +@file{devices/timer.c}, is an example. It contains this loop: @example -timer_put_char = 'x'; /* INCORRECT CODE */ -timer_do_put = true; +while (loops-- > 0) + barrier (); @end example -The reason this second example might be a problem is that the compiler -is, in general, free to reorder operations when it doesn't have a -visible reason to keep them in the same order. In this case, the -compiler doesn't know that the order of assignments is important, so its -optimization pass is permitted to exchange their order. -There's no telling whether it will actually do this, and it is possible -that passing the compiler different optimization flags or changing -compiler versions will produce different behavior. - -The following is @emph{not} a solution, because locks neither prevent -interrupts nor prevent the compiler from reordering the code within the -region where the lock is held: +@noindent +The goal of this loop is to busy-wait by counting @code{loops} down +from its original value to 0. Without the barrier, the compiler could +delete the loop entirely, because it produces no useful output and has +no side effects. The barrier forces the compiler to pretend that the +loop body has an important effect. + +Finally, optimization barriers can be used to force the ordering of +memory reads or writes. For example, suppose we add a ``feature'' +that, whenever a timer interrupt occurs, the character in global +variable @code{timer_put_char} is printed on the console, but only if +global Boolean variable @code{timer_do_put} is true. The best way to +set up @samp{x} to be printed is then to use an optimization barrier, +like this: @example -lock_acquire (&timer_lock); /* INCORRECT CODE */ timer_put_char = 'x'; +barrier (); timer_do_put = true; -lock_release (&timer_lock); @end example -Fortunately, real solutions do exist. One possibility is to -disable interrupts around the assignments. This does not prevent -reordering, but it makes the assignments atomic as observed by the -interrupt handler. It also has the extra runtime cost of disabling and -re-enabling interrupts: +Without the barrier, the code is buggy because the compiler is free to +reorder operations when it doesn't see a reason to keep them in the +same order. In this case, the compiler doesn't know that the order of +assignments is important, so its optimizer is permitted to exchange +their order. There's no telling whether it will actually do this, and +it is possible that passing the compiler different optimization flags +or using a different version of the compiler will produce different +behavior. + +Another solution is to disable interrupts around the assignments. +This does not prevent reordering, but it prevents the interrupt +handler from intervening between the assignments. It also has the +extra runtime cost of disabling and re-enabling interrupts: @example enum intr_level old_level = intr_disable (); @@ -903,35 +934,34 @@ timer_do_put = true; intr_set_level (old_level); @end example -A second possibility is to mark the declarations of +A second solution is to mark the declarations of @code{timer_put_char} and @code{timer_do_put} as @samp{volatile}. This keyword tells the compiler that the variables are externally observable and restricts its latitude for optimization. However, the semantics of @samp{volatile} are not well-defined, so it is not a good general -solution. +solution. The base Pintos code does not use @samp{volatile} at all. -Usually, the best solution is to use a compiler feature called a -@dfn{memory barrier}, a special statement that prevents the compiler -from reordering memory operations across the barrier. In Pintos, -@file{threads/synch.h} defines the @code{barrier()} macro as a memory -barrier. Here's how we would use a memory barrier to fix this code: +The following is @emph{not} a solution, because locks neither prevent +interrupts nor prevent the compiler from reordering the code within the +region where the lock is held: @example +lock_acquire (&timer_lock); /* INCORRECT CODE */ timer_put_char = 'x'; -barrier (); timer_do_put = true; +lock_release (&timer_lock); @end example -The compiler also treats invocation of any function defined externally, -that is, in another source file, as a limited form of a memory barrier. -Specifically, the compiler assumes that any externally defined function -may access any statically or dynamically allocated data and any local -variable whose address is taken. This often means that explicit -barriers can be omitted, and, indeed, this is why the base Pintos code -does not need any barriers. +The compiler treats invocation of any function defined externally, +that is, in another source file, as a limited form of optimization +barrier. Specifically, the compiler assumes that any externally +defined function may access any statically or dynamically allocated +data and any local variable whose address is taken. This often means +that explicit barriers can be omitted. It is one reason that Pintos +contains few explicit barriers. A function defined in the same source file, or in a header included by -the source file, cannot be relied upon as a memory barrier. +the source file, cannot be relied upon as a optimization barrier. This applies even to invocation of a function before its definition, because the compiler may read and parse the entire source file before performing optimization.