Pp. 31–42 of the Proceedings

Christopher Small and Stephen Manley

Abstract

In an operating system kernel, critical sections of code must be protected from interruption. This is traditionally accomplished by masking the set of interrupts whose handlers interfere with the correct operation of the criti cal section. Because it can be expensive to communicate with an off-chip interrupt controller, more complex opti mistic techniques for masking interrupts have been pro posed.

In this paper we present measurements of the behavior of the NetBSD 1.2 kernel, and use the measurements to explore the space of kernel synchronization schemes. We show that (a) most critical sections are very short, (b) very few are ever interrupted, (c) using the traditional synchronization technique, the synchronization cost is often higher than the time spent in the body of the critical section, and (d) under heavy load NetBSD 1.2 can spend 9% to 12% of its time in synchronization primitives.

The simplest scheme we examined, disabling all interrupts while in a critical section or interrupt handler, can lead to loss of data under heavy load. A more complex optimistic scheme functions correctly under the heavy workloads we tested and has very low overhead (at most 0.3%). Based on our measurements, we present a new model that offers the simplicity of the traditional scheme with the performance of the optimistic schemes.

Given the relative CPU, memory, and device performance of today's hardware, the newer techniques we examined have a much lower synchronization cost than the traditional technique. Under heavy load, such as that incurred by a web server, a system using these newer techniques will have noticeably better performance.

1 Introduction

Most, if not all, conventional hardware platforms allow device interrupts to be prioritized and assigned levels; a pending interrupt from a lower-level device can not interrupt the processing of an interrupt from a higher-level device. This method protects critical sections (by disabling interrupts from all devices) and device drivers (by disabling interrupts from the same device). Interrupts can then be prioritized by their frequency and the time required to handle them.

At Harvard we are in the process of developing a new operating system, the VINO kernel [Selt96]. In order to explore the space of kernel synchronization methods, we constructed analytic models of four basic interrupt handling schemes. We then used the NetBSD 1.2 kernel to analyze the performance of each scheme, by measuring:

• how often NetBSD enters critical sections,
• how long critical sections last,
• how often they are interrupted,
• the frequency of different types of interrupts, and
• the frequency with which these interrupts are delivered.

On many system architectures interrupt processing is handled by an off-chip programmable interrupt controller. On a Pentium PC the time required to access the off-chip interrupt controller is quite high, approximately three hundred cycles (2.5ms on a 120MHz Pentium).

In Section 2, we discuss related work on synchronization. In Section 3, we propose our four schemes for handling interrupts. In Section 4 we discuss our experimental setup, and then in Section 5 measure the overhead of the four schemes. Section 6 examines the behavioral correctness of the on-chip schemes we propose, measuring the frequency of, and amount of time spent in, interrupt handlers. In Section 7 we discuss our results and propose our new scheme, and conclude in Section 8.

2 Related Work

Synchronization does not require locking; other techniques have been proposed. For example, non- blocking synchronization [Herl90, Mass91, Green96], lock-free data structures [Wing92], and restartable atomic sequences [Bers92] are novel techniques proposed for synchronization. Some of these schemes require special hardware support, such as a compare- and-swap instruction, which is not available on all processors (e.g., the MIPS R3000 and the Intel i386). These techniques are designed to work in environments where it is expensive (or impossible) to disable interrupts, and work best in environments where contention is minimal. The cost and complexity of these schemes is higher than the on-chip schemes we propose, and our analysis shows that under typical loads, such complexity is unnecessary.

Similarly, Stodolsky et al. [Stod93] proposed decreasing the cost of synchronization by taking an optimistic approach. When the kernel makes a request to raise the global priority level, instead of communicating with the interrupt controller, the kernel saves the desired priority level in a variable. The critical section is then run, and on completion, the former priority level is restored. If no interrupts occurred during the critical section, the kernel was able to save the (high) cost of communicating with the interrupt controller, paying instead the (lower) cost of saving and restoring the logical priority level.

If an interrupt is delivered while the kernel is in a critical section, the interrupt handler compares the logical priority level with the interrupt priority level. If the interrupt is higher priority, it is handled immediately; if it is lower priority, the system queues the interrupt and falls back to the pessimistic scheme, setting the actual priority level to match the logical level. The cost of setting the global flag is quite low compared to the cost of communicating with the interrupt controller, so if the kernel is rarely interrupted while in a critical section the performance of the optimistic technique is superior to that of the standard pessimistic technique. In the case of a null RPC microbenchmark, they saw a 14% performance improvement.

In addition to the off-chip interrupt controller, some CPUs include an on-chip instruction to mask all interrupts. On the Pentium this operation can be performed in five to ten cycles, two orders of magnitude more quickly than communicating with the interrupt controller.

If a critical section is short, the cost of going off- chip to disable and re-enable interrupts can be much greater than the time spent in the body of the critical section. For example, if the critical section adds an element to a linked list, it may only run for twenty or thirty cycles; if the kernel needs to go off-chip to synchronize, the time spent in the synchronization code is an order of magnitude more than the time spent in the body of the critical section. If we use the on-chip instructions to disable and re-enable interrupts, the synchronization cost is lowered to the point where it is less than that of the critical section code.

Optimistic synchronization techniques are particularly well-suited to short-duration critical sections that are infrequently interrupted. On entry to a critical section, instead of disabling interrupts, a global flag is set. If an interrupt is delivered while the flag is set, interrupts are only then disabled, and the interrupt is postponed until the flag is cleared. If no interrupt is delivered while the flag is set, the cost of synchronization is just the cost of setting and clearing the flag.

In this paper we model four schemes, based on two variables: where to mask interrupts (on-chip or off-chip) and how to mask them (pessimistically or optimistically).

We note that the techniques that use on-chip interrupt masking for synchronization may not be usable on multiprocessor systems. In symmetric multiprocessor systems, any processor may enter a critical section. Hence, any processor must be able to disable interrupts delivered to all processors. On this type of hardware the synchronization scheme must communicate either with the other processors (directly or through memory), or with an off-processor interrupt controller; in either case, it needs to go off-chip. An asymmetric multiprocessor (where only one processor runs operating system kernel code, and hence only one processor receives interrupts and enters critical sections) would be able to take advantage of the on-chip techniques we propose.

In the remainder of the paper we examine our four schemes in detail and compare their costs. We use our results to derive a fifth scheme which synthesizes the benefits of the others.

Our work begins with the ideas developed by Stodolsky and adds a second dimension of comparison, the performance difference seen when masking interrupts on-chip and off-chip.

Mogul and Ramakrishnan [Mogul96] have explored a related issue. Interrupt processing can be split across multiple priority levels, a high-priority level that responds to the device interrupt and a low-priority level that processes the interrupt. When this is the case, it is possible for a flood of high priority device interrupts to cause the starvation of the low-priority processing. Mogul and Ramakrishnan refer to this state as receiver livelock. When the system reaches this state, their strategy is to disable interrupts and poll for new requests as the old ones are handled.

Their techniques are most appropriate in the face of unsolicited I/O from network and serial devices. The kernel has little or no control over how quickly data is sent to this type of device. Unlike a network device, a disk device only generates interrupts in response to a request from the kernel. If the kernel is receiving disk interrupts more quickly than it can process them, the kernel can reduce the load by queueing fewer disk requests. A natural feedback loop is present; if the kernel is bogged down handling old work, little new work will be started.

Mogul and Ramakrishnan's strategy is related to ours. They find that, at times, it is more efficient to ignore new interrupts in order to process the ones that have already arrived. However, they propose dynamically switching between two schemes based on the current system load; we propose choosing a single scheme for handling all interrupts. Their work is compatible with ours; none of the synchronization schemes we analyze preclude use of their techniques.

3 Synchronization Strategies

In the following sections we describe each scheme in detail, sketch its synchronization functions, and discuss its costs and benefits.

3.1 Spl-Pessim

   crit_sec_enter()
       saved_mask = cur_mask
       PIC_mask(all)
   
   crit_sec_leave()
       PIC_mask(saved_mask)
   
   interrupt_handler(int intr_level)
       saved_mask = cur_mask
       PIC_mask(intr <= intr_level)
       handle interrupt
       PIC_mask(saved_mask) 

3.2 Spl-Optim

   crit_sec_enter()
       in_crit_sec = true
   
   crit_sec_leave()
       if (any queued interrupts)
              handle queued interrupts
       in_crit_sec = false

   interrupt_handler(int intr_level)
       if (in_crit_sec 
               || intr_level < cur_level)
                     queue interrupt
       else
                     saved_mask = cur_mask
                     PIC_mask(intr <= intr_level)
                     handle interrupt
                     PIC_mask(saved_mask)
                     handle queued interrupts

Table 1: Synchronization Strategies Explored. On the x86, NetBSD 1.2 uses spl-optim, the Linux 1.3.0 kernel uses cli-pessim, and BSD/OS 2.1 uses spl-pessim.

------------------------------------------
|           | Pessimistic  | Optimistic  |
==========================================
| Off-chip  | spl-pessim   | spl-optim   |
------------------------------------------
| On-chip   | cli-pessim   | cli-optim   |
------------------------------------------

The benefit of this scheme is low per-critical section overhead, and fine-grained control over which interrupts are disabled.

The cost of this scheme is communication with the off-chip interrupt controller if an interrupt is delivered when the kernel is in a critical section, and a higher code complexity than the pessimistic schemes.

3.3 Cli-Pessim

   crit_sec_enter()
       disable_all_interrupts()
   
   crit_sec_leave()
       enable_all_interrupts()
   
   interrupt_handler(int intr_level)
       crit_sec_enter()
       handle interrupt
       crit_sec_leave()

3.4 Cli-Optim

   crit_sec_enter()
       in_crit_sec = true
   
   crit_sec_leave(int level)
       if (any queued interrupts)
              handle queued interrupts
       in_crit_sec = false
   
   interrupt_handler(int intr_level)
       if (in_crit_sec)
              queue interrupt
       else
              disable_all_interrupts()
              handle interrupt
              enable_all_interrupts()

The benefit of this scheme is low per-critical section overhead. Its cost is increased risk of lost interrupts if multiple interrupts are delivered during critical sections, and possible delay of high-priority interrupts while processing a lower priority interrupt or critical section. It also has a slightly higher code complexity than the cli-pessim scheme.

3.5 Comparison of Schemes

Fortunately, it is not necessary to test all four schemes for correctness. The cli-pessim scheme is the least responsive to external interrupts; if it behaves correctly in the face of heavy load, the other systems can do no worse.

Note that use of a cli scheme does not preclude assigning priorities to interrupts. Although all interrupts are disabled while the system is in a critical section, pending interrupts can still be assigned priority levels, and higher-priority interrupts will take precedence over lower-priority interrupts when interrupts are once again enabled. (In our implementation of the cli-pessim kernel we assign the same priorities to interrupts as are used by standard NetBSD1.2, the spl-optim kernel to which we compare it.)

The costs and benefits of the four strategies depend on a number of components. First, the cost of going off- chip to set the priority level needs to be measured, as does the cost of disabling interrupts on-chip. Second, the frequency with which interrupts are received, and the frequency with which an interrupt arrives while the kernel is in a critical section, must be measured. We must also determine the time spent in critical sections in order to learn whether a cli-pessim kernel will ignore interrupts for too long a period of time, with too high a risk of losing interrupts.

The overhead of synchronization for each strategy can be described by a simple analytic model. The model must take into account:

• number of critical sections entered: number of times a critical section was entered, per second. This factor is important when computing the overhead for any of the schemes.
• number of interrupted critical sections: number of times a critical section was interrupted, per second. This is only a factor for the optimistic schemes.
• off-chip cost: the time required to communicate with the interrupt controller, first raising the priority level, then lowering it. This is only relevant for the spl schemes.
• on-chip cost: the time required to disable interrupts and re-enable them. This cost only applies to the cli schemes.
• flag setting cost: the time required to set the variable holding the mask. This cost is only a factor when using an optimistic scheme.

4 Experimental Setup

4.1 Kernels

Starting with NetBSD 1.2 as a base, we developed a cli-pessim kernel. This kernel disables all interrupts any time a critical section or interrupt handler is entered, and enables all interrupts when the critical section or interrupt handler finishes. The cli-pessim kernel allowed us to accurately measure the length of time spent in critical sections, the number of critical sections, and the time required to handle each type of interrupt.

4.2 Hardware

Pentium processors include an on-chip cycle counter, which enable very precise timing measurements. We read the counter at the start and at the end of each experiment; the difference was multiplied by the processor cycle time (8 1/3 nanoseconds) to obtain the elapsed time. The cost of reading the cycle counter is roughly 10 cycles; where significant, the timing cost has been subtracted from our measurements. We include code to read the cycle counter in the Appendix.

5 Synchronization Overhead

Table 2: Synchronization Scheme Overheads. The model describing the overhead associated with the four schemes discussed. The costs are functions of five variables: critical sections entered, critical sections interrupted, off-chip cost, on-chip cost, and flag-setting cost.

---------------------------------------------------------------------------------
| Scheme      | Synchronization Overhead                                        |
=================================================================================
| spl-pessim  | (number of critical sections entered) o (off-chip cost)         |
---------------------------------------------------------------------------------
| spl-optim   | (number of critical sections entered) o (flag-setting cost) +   |
|             | (number of critical sections interrupted) o (off-chip cost)     |
---------------------------------------------------------------------------------
| cli-pessim  | (number of critical sections entered) o (on-chip cost)          |
---------------------------------------------------------------------------------
| cli-optim   | (number of critical sections entered) o (flag-setting cost) +   |
|             | (number of critical sections interrupted) o (on-chip cost)      |
---------------------------------------------------------------------------------

As shown in Table 2, the synchronization overhead of each scheme is a function of five variables: the off-chip priority setting cost, the on-chip priority setting cost, the flag-setting cost, the number of times a critical section is entered, and the number of times an interrupt arrives while the system is in a critical section. In this section we measure each component to derive the synchroniza tion overhead for the four schemes.

5.1 Critical Sections Per Second

The first two tests are the result of running the Modified Andrew Benchmark [Ouster90] on a local file system (Andrew local) and an NFS-mounted file system (Andrew NFS). The Modified Andrew Benchmark consists of creating, copying, and compiling a hierarchy of files, and was designed to measure the scalability of the Andrew filesystem [How88].

Table 3: Critical Sections Per Second. The mean and maximum number of critical sections entered, per second, measured with the cli-pessim kernel. We also measured the mean critical section duration, which is seen to be very short, especially relative to the cost of off-chip synchronization.

--------------------------------------------------------
|               | Mean       | Max        | Mean       |
|               | Critical   | Critical   | Critical   |
|               | Sections   | Sections   | Section    |
|               | per sec    | per sec    | Duration   |
|               | (std dev)  |            |            |
--------------------------------------------------------
| Andrew        | 36048      | 72521      | 3.1ms      |
| local         | (60%)      |            |            |
--------------------------------------------------------
| Andrew        | 25867      | 72940      | 4.6ms      |
| NFS           | (68%)      |            |            |
--------------------------------------------------------
| WebStone      | 34468      | 82653      | 3.3ms      |
|               | (31%)      |            |            |
--------------------------------------------------------
| Serial 115.2  | 47762      | 47807      | 0.6ms      |
|               | (0.05%)    |            |            |
--------------------------------------------------------

The third test was running the WebStone 2.0 benchmark from Silicon Graphics [SGI96]. WebStone was designed to test the performance of web servers under varying load. We installed the Apache 1.1.1 server on our test machine, and ran the WebStone clients (which generate http requests of the server) from a SparcStation 20. The maximum number of critical sections per second occurred with 50 client processes; we report the results from this test.

The fourth test measured the kernel's behavior while receiving a 64KB file via tip(1) at 115,200 bps. This test measures the behavior of the kernel when it is presented with a high rate of short-duration interrupts.

We instrumented the kernel to measure the duration of each critical section, using the Pentium cycle counter. A user-level process polled the kernel once per second to retrieve the number of critical sections and the time spent in critical sections since the last poll. We use these results to derive the numbers in Table 4.

Table 4: Interrupted Critical Sections. We measured the number of critical sections entered per second on the spl-optim kernel, and the number of times per second critical sections were interrupted (which causes the optimistic kernel to revert to pessimistic synchronization behavior). We include the percentage of critical sections interrupted.

---------------------------------------------------
|               | Mean Critical   | Interrupted   |
|               | Sections        | Critical      |
|               | per second      | Sections      |
|               | (std dev)       | per second    |
|               |                 | (% intr)      |
---------------------------------------------------
| Andrew local  | 31904 (69%)     | 15 (0.05%)    |
---------------------------------------------------
| Andrew NFS    | 25172 (67%)     | 50 (0.2%)     |
---------------------------------------------------
| WebStone      | 33890 (33%)     | 300 (0.9%)    |
---------------------------------------------------
| Serial 115.2  | 45269 (8%)      | 140 (0.3%)    |
---------------------------------------------------

Figure 1: Critical Section Duration Distribution. Distribution of critical section duration for Andrew NFS; other distributions had the same shape.

5.2 Interrupted Critical Sections

For comparison with the results of Table 4, we include the Mean Critical Sections Per Second measured using this kernel; these results are very similar to the values seen in Table 4. As we expected (based on the short duration of critical sections), we saw that a very small number of critical sections are interrupted.

5.3 Synchronization Primitive Cost

Because these tests were run in a tight loop, a minimal number of cache misses and other side-effects are seen in these results, hence the synchronization times we use are somewhat optimistic. Cache misses could have a large percentage impact on the on-chip and flag-setting measurements, because these instruction sequences are very short. However, because they are so short, even if all of the instructions and data referenced by the code cause cache misses, the total absolute additional cost (in cycles) would be very small.

Table 5: Synchronization Primitive Cost: Time required to set priority level off-chip, on-chip, and to set a global flag saving the logical priority level. The Pentium has a write buffer, so the flag-setting cost does not include time to write to main memory.

----------------------------------------------------------
| Synchronization Primitive        | Time                |
==========================================================
| off-chip (spl-pessim)            | 2.5ms (304 cycles)  |
----------------------------------------------------------
| on-chip (cli-pessim)             | 0.18ms (21 cycles)  |
----------------------------------------------------------
| set flag (spl-optim, cli-optim)  | 0.05ms (6 cycles)   |
----------------------------------------------------------

The synchronization cost of each of the four schemes is directly driven by the costs shown in Table 5. The off-chip cost is the synchronization cost of the spl- pessim kernel (304 cycles, 2.5ms), on-chip gives the synchronization cost the cli-pessim kernel (21 cycles, 0.18ms), and the flag setting cost is the synchronization cost of the optimistic kernels (6 cycles, 0.05ms). As we immediately see by comparing the costs in Table 5 with the critical section durations seen in Table 4, the mean critical section duration seen is less than twice the off- chip synchronization cost, and more than three times the mean Serial 115.2 critical section cost.

5.4 Synchronization Overhead

Table 6: Synchronization Scheme Overhead. Percentage of time spent synchronizing critical sections using the described techniques. Computed using equations in Table 2 and measurements from Table 3, Table 4, and Table 5.

----------------------------------------------------------------
|             | Synchronization  |         |        |          |
|             | Overhead         |         |        |          |
----------------------------------------------------------------
| Scheme      | Andrew           | Andrew  | Web    | Serial   |
|             |  local           |  NFS    | Stone  | 115.2    |
================================================================
| spl-pessim  | 9.0%             | 6.5%    | 8.6%   | 11.9%    |
----------------------------------------------------------------
| spl-optim   | 0.2%             | 0.1%    | 0.3%   | 0.3%     |
----------------------------------------------------------------
| cli-pessim  | 0.7%             | 0.5%    | 0.6%   | 0.9%     |
----------------------------------------------------------------
| cli-optim   | 0.2%             | 0.1%    | 0.2%   | 0.2%     |
----------------------------------------------------------------

We see that with the large number of critical sections per second seen under the Serial 115.2 test, the spl-pessim kernel can spend nearly 12% of its time in synchronization primitives. Even under the lightest measured load, the system spends more than 6% of its time in synchronization primitives.

Another thing to note is that the other three techniques all have an overhead that is an order of magnitude less than that of the spl-pessim technique. Even though the spl-optim technique goes off-chip for synchronization, because so few critical sections are interrupted (from 0.05% to 0.9%) the difference is negligible (between 0.2%-0.7%).

6 Correctness

The optimistic schemes do not delay high-priority interrupts, nor does the spl-pessim scheme; the cli- pessim scheme is the only one that masks all interrupts while in a critical section or interrupt handler. If the cli- pessim scheme can operate correctly, the other schemes will also operate correctly.

In Table 3 we saw that the mean critical section duration is between 0.6 and 4.6ms. We are concerned that handling a device interrupt could take much longer, especially with programmed I/O devices, such as the IDE disk, which copy data from the device to the kernel one word at a time.

We are concerned that high-frequency interrupts are not overly delayed while in long-duration interrupt handlers. We gathered data on both long-duration handlers (IDE disk interrupts) and high-frequency interrupts (serial lines at 115.2Kbps).

We measured the time required to process interrupts from a variety of devices attached to our test system. Our tests involve reading from or writing to each device and measuring the amount of time required to perform the test and the number of interrupts delivered while performing the test. We ran the following tests:

• ide disk: write 8MB to IDE disk.
• scsi disk: write 8MB to SCSI disk.
• scsi cd-rom: read 8MB from SCSI CD-ROM.
• serial-300: read 8KB (via tip) at 300bps.
• serial-38.4: read 64KB (via tip) at 38.4Kbps.
• serial-115.2: read 64KB (via tip) at 115.2Kbps.
• floppy: read 1MB from raw floppy disk.
• ether-small: flood ping of 1000 64 byte packets.
• ether-large: flood ping of 1000 1024 byte packets.

6.1 IDE, SCSI, and Floppy Interrupts

Surprisingly, although the specifications of the IDE and SCSI disks is very similar, it took nearly three times as long to transfer 8MB to the SCSI disk as it did to transfer it to the IDE disk. We believe that this is an artifact of the NetBSD 1.2 disk drivers; we saw similar performance with the generic NetBSD 1.2 kernel and our cli-pessim kernel. We do not believe that this reflects the underlying performance of the disk or the controller; under BSD/OS 2.1 the performance of the two disks was much closer (in fact, the SCSI disk was about 10% faster than the IDE disk).

The mean time required to process an IDE interrupt (1.5ms) is substantially greater than any other interrupt processing time we measured. We discuss the possibility of timing conflicts between IDE interrupts and other interrupts in Section 6.4.

Table 7: Behavior ofspl-optim kernel during device tests. Frequency of device interrupts and time to handle an interrupt from each device was measured. Although the spread between minimum and maximum is large, the median is in all cases other than floppy is within 2% of the mean. Each test measured the reception of several thousand interrupts.

------------------------------------------------------------------------------------------------------------------------
| Test               | Duration   | Total       | Interrupts  | Mean time    | Min time    | Median      | Max time    |
|                    | of Test    | Interrupts  |  per        | to handle    | to handle   | time        | to handle   |
|                    | (seconds)  |             | second      | interrupt    | interrupt   | to handle   | interrupt   |
|                    |            |             |             | (std dev)    |             | interrupt   |             |
========================================================================================================================
| ide disk           | 3.2s       | 1027        | 321         | 1519ms (7%)  | 15ms        | 1545ms      | 2003ms      |
------------------------------------------------------------------------------------------------------------------------
| scsi disk          | 8.8s       | 553         | 61          | 65ms (15%)   | 16ms        | 64ms        | 86ms        |
------------------------------------------------------------------------------------------------------------------------
| scsi cd-rom        | 13.4s      | 3931        | 293         | 27ms (7%)    | 20ms        | 26ms        | 40ms        |
------------------------------------------------------------------------------------------------------------------------
| floppy             | 64.2s      | 506         | 8           | 169ms (57%)  | 4ms         | 200ms       | 271ms       |
------------------------------------------------------------------------------------------------------------------------
| serial-300 (8K)    | 274s       | 8221        | 30          | 9ms (5%)     | 9ms         | 9ms         | 12ms        |
------------------------------------------------------------------------------------------------------------------------
| serial-38.4 (64K)  | 17.4s      | 8195        | 471         | 27ms (2%)    | 19ms        | 27ms        | 42ms        |
------------------------------------------------------------------------------------------------------------------------
| serial-115 (64K)   | 5.8s       | 8176        | 1410        | 27ms (4%)    | 11ms        | 27ms        | 54ms        |
------------------------------------------------------------------------------------------------------------------------
| ethernet-small     | 2.4s       | 1003        | 418         | 78ms (25%)   | 44ms        | 78ms        | 370ms       |
------------------------------------------------------------------------------------------------------------------------
| ethernet-large     | 3.4s       | 1703        | 501         | 487ms (8%)   | 45ms        | 491ms       | 1194ms      |
------------------------------------------------------------------------------------------------------------------------

The standard deviation of floppy interrupt processing time is quite large (57%). It is caused by the several different types of interrupts generated by the floppy device, from seek completion notification (4ms), to transfer completion notification (25ms), to data transfer (250ms). The maximum time seen, 271ms, is short enough that we are not concerned about floppy interrupts.

6.2 Serial Interrupts

When we tested higher-rate serial connection (at 115.2 bps) we saw roughly the same number of interrupts as we saw in the serial-38.4 test (8195 vs. 8176) and the same mean interrupt handling time (27ms), implying the same number of characters processed per interrupt, but the total test took one third as long. The high rate of interrupts during the serial- 115.2 test may conflict with the large amount of time required to process an ide-disk interrupt; we discuss this possibility in Section 6.4.

6.3 Network Interrupts

Interrupt processing time is independent of protocol because the higher-level protocol processing (where we would see differences between TCP, UDP, and ping) does not take place when the packet arrives; instead, the packet is queued for processing by a higher-level "soft" interrupt handler which runs once the hardware interrupt has completed.

We ran additional tests with varying packet sizes. We saw the expected relationship between packet size and processing time (which more or less scaled linearly with packet size).

Faster network technologies (e.g., 100Mbps Ethernet and ATM) would generate interrupts much more frequently than our 10Mbps Ethernet interface. However, as we see below, the rate at which the serial device generates interrupts is sufficient to preclude use of the cli schemes. Based on this, the interrupt generation rate of ATM is a moot point.

6.4 Summary

Our results show that in our environment it takes little time to handle an interrupt from any of our devices. No interrupt seen took more than 2ms to service, and in most cases the interrupt processing time was several orders of magnitude less than that.

However, we see from Table 7 that interrupts can occur very frequently. For example, the serial-115.2 interrupts arrived at 1400Hz (every 700ms). We must examine the consequences of delaying the processing of these interrupts.

As was discussed in Section 2, we can partition interrupts into two classes: solicited and unsolicited. Solicited interrupts come in response to requests from the CPU (e.g., in response to a disk request). Unsolicited interrupts are generated externally, and are not under the control of the system (e.g., serial and network traffic). The rate of solicited interrupts are under the control of the system; when a solicited interrupt is received, the system spends its time processing the interrupt rather than generating more requests. The system can thus control the rate at which solicited interrupts are generated.

The system does not control the rate at which unsolicited interrupts are generated. However, the system can indirectly impact the rate at which they are generated, either in software (by not sending acknowledgments to network packets that are dropped or processed in time), or in hardware (by use of serial- line flow control).

To block serial interrupts it is necessary for the system to communicate with the device, and to be aware that it is necessary to slow the interrupt rate. If serial interrupts are overly delayed, the system will not be aware of the possibility of overflow, and hence will not be able to stem the tide in time.

From our measurements, the longest that an interrupt will be delayed is 2ms (the longest time spent handling an ide-disk interrupt). The serial-115.2 device receives characters every 70ms (115.2 bits per sec = 14,400 bytes per sec = one byte every 70ms). This means that up to 28 characters (2ms / 70ms = 28) could arrive while an Ethernet interrupt is being processed. Although the serial port is buffered, the buffer only holds 16 characters. At this rate, characters could easily be lost on the serial line while processing an IDE interrupt.

If we could eliminate programmed I/O devices, the cli schemes would work. However, newer devices with a high interrupt rate (e.g., ATM network controllers), combined with the possibility of slow interrupt handlers shift the balance against the cli techniques. Although, in some hardware combinations, the cli schemes would work, many common configurations could easily lead to loss of data.

The failure of the strict cli schemes leads us to propose a new, hybrid scheme, cli-spl-pessim, which is described in Section 7. The cli-spl-pessim scheme combines the low cost of the cli schemes for critical section synchronization with the interrupt prioritization of the spl schemes.

7 Analysis and Proposal

The performance improvement we see is less than that seen by Stodolsky et al. with their spl-optim scheme (14%). We attribute this in part to the differences between our benchmarks and theirs; their test consisted of a highly optimized null RPC, which has a single critical section. Because the null RPC took very little time (2140 cycles), an improvement in critical section synchronization had a large performance impact. Under the more varied loads that we measured, the kernel spends a much lower percentage of its time in synchronization code.

For the cli schemes to work, critical sections and interrupt handlers must complete their work quickly. These schemes completely disable interrupts during a critical section, so a long-running interrupt handler can delay the delivery of interrupts for a long period of time, increasing the likelihood of data loss. The combination of devices whose interrupt handlers require a long time to service (e.g., IDE disks with programmed I/O) with low latency requirements (e.g., very fast serial ports) is a worst-case scenario for the cli scheme.

7.1 Proposal

• interrupts are delivered much less frequently than critical sections are entered,
• interrupt handlers take much longer than critical sections, and
• on our hardware platform, when an interrupt is delivered it is necessary to communicate with the off- chip controller,

   void crit_sec_enter(int level)
       disable all interrupts
   
   void crit_sec_leave(int level)
       enable all interrupts

   void interrupt_handler
       prev_level = cur_interrupt_level
       PIC_mask(interrupt_level)
       handle_interrupt
       PIC_mask(prev_level)

Because our model includes only the cost of synchronization of critical sections, and disregards the cost of the synchronization overhead in interrupt handlers, using our model the cost of cli-spl-pessim is identical to that of the cli-pessim scheme, with (as shown in Table 6) sub-1% synchronization overhead for the system loads that we studied.

With the performance characteristics and simplicity of the cli-pessim scheme, without its incorrect behavior under heavy load, we plan to use the cli-spl-pessim scheme in the implementation of our new operating system kernel.

7.2 Related Schemes

The Linux operating system uses a scheme similar to cli-spl-pessim. The cli and sti instructions are used to synchronize critical sections (with the concomitant high performance), and, like NetBSD 1.2, short-duration interrupt handlers are run with all interrupts disabled. Long-duration handlers are either run with no protection from interrupts (which increases their complexity) or wake a kernel task to handle the processing of the interrupt, and then return. Although this scheme efficiently synchronizes critical sections, we believe that the increased latency and complexity of waking a separate task argue against use of this technique.

8 Conclusions

Our results have driven the design of our new kernel, where we use the proposed cli-spl-pessim scheme. This scheme provides us with the simplicity of the pessimistic schemes we describe, with the low overhead of the optimistic schemes.

Comparing our scheme to those used in earlier systems, we are reminded of how quickly hardware changes: the CPU and I/O bus of today is substantially faster than the one available in 1993 [Stod93], and much, much faster than the one available on the VAX or the PDP-11 [Leff89]. Nevertheless, developers of newer systems [Cust93] find themselves re-using old, complex techniques to solve a problem that may no longer exist.

Status and Availability

All code discussed in this paper (benchmark tests and patch files for a cli-pessim NetBSD 1.2) is available at https://www.eecs.harvard.edu/~chris.

Acknowledgments

Our thanks to our advisor, Margo Seltzer, for her invalu able feedback, wordsmithing, and grasp of the subtleties of "that" and "which." We thank our reviewers, espe cially Mike Karels, our shepherd, for providing very helpful feedback. And thanks to Brad Chen, whose pre vious work on fast interrupt priority management helped inspire this work.

Bibliography

[Berg86] Berglund, E., "An Introduction to the V-System", IEEE Micro 10, 8, 35-52 (August 1986).

[Bers92] Bershad, B., Redell, D., Ellis, J., "Fast Mutual Exclusion for Uniprocessors," ASPLOS V, 223-233, Boston, MA (1992)

[Cust93] Custer, H., Inside Windows NT, Microsoft Press, Redmond, WA, 218-221 (1993).

[Green96] Greenwald, M., Cheriton, D., "The Synergy Between Non-blocking Synchronization and Operating System Structure," Second Symposium on Operating Systems Design and Implementation, 123-136, Seattle, WA (1996).

[Herl90] Herlihy, M. "A Methodology for Implementing Highly Concurrent Data Structures," Second ACM Symposium on Principles and Practice of Parallel Programming, 197-206 (1990).

[How88] Howard, J., Kazar, M., Menees, S., Nichols, D., Satyanarayanan, M., Sidebotham, R., West, M., "Scale and Performance in a Distributed File System," ACM Transactions on Computer Systems 6, 1 51-81 (1988).

[Intel95] Pentium Processor Family Developer's Manual, Volume 3: Architecture and Programming Manual, Intel Corporation, Mt. Prospect, IL (1995).

[Leff89] Leffler, S., McKusick, M. K., Karels, M., Quarterman, J., The Design and Implementation of the 4.3BSD UNIX Operating System, Addison-Wesley Publishing, Reading, MA (1989).

[Mass91] Massalin, H., Pu, C., "A Lock-Free Multiprocessor OS Kernel," Technical Report CUCS-005-91, Department of Computer Science, Columbia University (1991)

[Mogul96] Mogul, J., Ramakrishnan, K. K., "Eliminating Receiver Livelock in an Interrupt-Driven Kernel," USENIX Technical Conference, 99-111, San Diego, CA (1996).

[Ouster90] Ousterhout, John, "Why Aren't Operating Systems Getting Faster as Fast as Hardware," USENIX Summer Conference, 247-256, Anaheim, CA (1990)

[Selt96] Seltzer, M., Endo, Y., Small, C., Smith, K., "Dealing With Disaster: Surviving Misbehaving Kernel Extensions," Proceedings of the Second OSDI, Seattle, WA (1996).

[SGI96] Silicon Graphics Inc., "Webstone: World-Wide Web Server Benchmarking," https://www.sgi.com/Products/WebFORCE.

[Stan88] Stankovic, J., Ramamritham, K., "A New Hard Real- Time Kernel", Hard Real-Time Systems, IEEE, 361-370 (1988).

[Stod93] Stodolsky, D., Chen, J. B., Bershad, B., "Fast Interrupt Priority Management in Operating System Kernels," USENIX Symposium on Microkernels and Other Kernel Architectures, 105-110, San Diego, CA (1993).

[Wing92] Wing, J, Gong, C, "A Library of Concurrent Objects," CMU CS TR 90-151, School of Computer Science, Carnegie Mellon University (1992).