國外操作系統(tǒng)相關(guān)論文stabledeterministicmultithreadingthroughschedulememoization

1、Stable Deterministic Multithreading through Schedule MemoizationHeming Cui, Jingyue Wu, Chia-che Tsai, Junfeng Yang {heming, jingyue, ct2459, junfeng}@cs.columbia.edu Computer Science Department Columbia University New Y

2、ork, NY 10027AbstractA deterministic multithreading (DMT) system eliminates nondeterminism in thread scheduling, simplifying the development of multithreaded programs. However, ex- isting DMT systems are unstable; they m

3、ay force a pro- gram to (ad)venture into vastly different schedules even for slightly different inputs or execution environments, defeating many benefits of determinism. Moreover, few existing DMT systems work with serve

4、r programs whose inputs arrive continuously and nondeterministically. TERN is a stable DMT system. The key novelty in TERN is the idea of schedule memoization that memo- izes past working schedules and reuses them on fut

5、ure inputs, making program behaviors stable across different inputs. A second novelty in TERN is the idea of win- dowing that extends schedule memoization to server pro- grams by splitting continuous request streams into

6、 win- dows of requests. Our TERN implementation runs on Linux. It operates as user-space schedulers, requiring no changes to the OS and only a few lines of changes to the application programs. We evaluated TERN on a dive

7、rse set of 14 programs (e.g., Apache and MySQL) with real and synthetic workloads. Our results show that TERN is easy to use, makes programs more deterministic and stable, and has reasonable overhead.1 IntroductionMultit

8、hreaded programs are difficult to write, test, and debug. A key reason is nondeterminism: different runs of a multithreaded program may show different behaviors, depending on how the threads interleave [35]. Two main fac

9、tors make threads interleave nondeter- ministically. The first is scheduling, how the OS and hardware schedule threads. Scheduling nondeterminism is not essential and can be eliminated without affecting correctness for m

10、ost programs. The second is input, what data (input data) arrives at what time (input timing). In- put nondeterminism sometimes is essential because ma- jor changes in inputs require different schedules. How-ever, freque

11、ntly input nondeterminism is not essential and the same schedule can be used to process many dif- ferent inputs (§2.2). We believe nonessential nondeter- minism should be eliminated in favor of determinism. Determin

12、istic multithreading (DMT) systems [13, 22, 41] make threads more deterministic by eliminating scheduling nondeterminism. Specifically, they constrain a multithreaded program such that it always uses the same thread sche

13、dule for the same input. By doing so, these systems make program behaviors repeatable, in- crease testing confidence, and ease bug reproduction. Unfortunately, though existing DMT systems elimi- nate scheduling nondeterm

14、inism, they do not reduce in- put nondeterminism. In fact, they may aggravate the ef- fects of input nondeterminism because of their design limitation: when scheduling the threads to process an input, they consider only

15、this input and ignore previ- ous similar inputs. This stateless design makes schedules over-dependent on inputs, so that a slight change to in- puts may force a program to (ad)venture into a vastly dif- ferent, potential

16、ly buggy schedule, defeating many bene- fits of determinism. We call this the instability problem. This problem is confirmed by our results (§8.2.1) from an existing DMT system [13]. In fact, even with the same inpu

17、t, existing DMT sys- tems may still force a program into different schedules for minor changes in the execution environment such as processor type and shared library. Thus, developers may no longer be able to reproduce b

18、ugs by running their pro- gram on the bug-inducing input, because their machine may differ from the machine where the bug occurred. This paper presents TERN, a schedule-centric, stateful DMT system. It addresses the inst

19、ability problem us- ing an idea called schedule memoization that memoizes past working schedules and reuses them for future inputs. Specifically, TERN maintains a cache of past schedules and the input constraints require

20、d to reuse these sched- ules. When an input arrives, TERN checks the input against the memoized constraints for a compatible sched-our choice of schedule representation in TERN (§2.2), and why we can reuse schedules

21、 across inputs (§2.3).2.1 The Instability ProblemA DMT system is, conceptually, a function that maps an input I to a schedule S. The properties of this function are that the same I should map to the same S and that

22、S is a feasible schedule for processing I. A stable DMT system such as TERN has an additional property: it maps similar inputs to the same schedule. Existing DMT sys- tems, however, tend to map similar inputs to differen

23、t schedules, thus suffering from the instability problem.We argue that this problem is inherent in existing DMT systems because they are stateless. They must provide the same schedule for an input across differ- ent runs

24、, using information only from the current run. To force threads to communicate (e.g., acquire locks or access shared memory) deterministically, existing DMT systems cannot rely on physical clocks. Instead, they maintain

25、a logical clock per thread that ticks determin- istically based on the code this thread has run. More- over, threads may communicate only when their logical clocks have deterministic values (e.g., smallest across the log

26、ical clocks of all threads [41]). By induction, logical clocks make threads deterministic.However, the problem with logical clocks is that for efficiency, they must tick at roughly the same rate to prevent a thread with

27、a slower clock from starving oth- ers. Thus, existing DMT systems have to tie their logical clocks to low-level instructions executed (e.g., completed loads [41]). Consequently, a small change to the input or execution e

28、nvironment may alter a few instructions exe- cuted, in turn altering the logical clocks and subsequent thread communications. That is, a small change to the input or execution environment may cascade into a much differen

29、t (e.g., correct vs. buggy) schedule.2.2 Schedule Representation and DeterminismPrevious DMT systems have considered two types of schedules: (1) a deterministic order of shared memory accesses [13, 22] and (2) a synchron

30、ization order (i.e., a total order of synchronization operations) [41]. The first type of schedules are truly deterministic even if there are races, but they are costly to enforce on commodity hard- ware (e.g., up to 10

31、times overhead [13]). The second type can be efficiently enforced (e.g., 16% overhead [41]) because most code is not synchronization code and can run in parallel; however, they are deterministic only for inputs that lead

32、 to race-free runs [41, 46].TERN represents schedules as synchronization orders for efficiency. An additional benefit is that synchroniza- tion orders can be reused more frequently than memory access orders (cf next subs

33、ection). Moreover, researchers have found that many concurrency errors are not dataProgram Input Constraints for Schedule ReusePBZip2 Same number of file blocks (NumBlocks or -b) and threads (-p) Apache For groups of typ

34、ical HTTP GET requests, same cache status and response sizes fft Same number of threads (-p) lu Same number of threads (-p), size of the matrix (-n), and block size (-b) barnes Same number of threads (NPROC) and val- ues

35、 of variables dtime and tstopTable 1: Input constraints of five programs to reuse schedules. Identifiers without a dash are configuration variables, and those with a dash are command line options.races, but atomicity and

36、 order violations [39]. These er- rors can be deterministically reproduced or avoided using only synchronization orders.Although data races may still make runs which reuse schedules nondeterministic, TERN is less prone t

37、o this problem than existing DMT systems [41] because it has the flexibility to select schedules. If it detects a race in a memoized schedule, it can simply discard this sched- ule and memoize another. This selection tas

38、k is often easy because most schedules are race-free. In rare cases, TERN may be unable to find a race-free schedule, result- ing in nondeterministic runs. However, we argue that in- put nondeterminism cannot be fully el

39、iminated anyway, so we may as well tolerate some scheduling nondeter- minism, following the end-to-end argument.2.3 Why Can We Reuse Schedules?This subsection presents an intuitive and an empirical argument to support ou

40、r insight that we can frequently reuse schedules for many programs/workloads. Intu- itively, synchronization operations map to developer in- tents of inter-thread control flow. By enforcing the same synchronization order

41、, we fix the same inter-thread “path,” but still allow many different inputs to flow down this path. (This observation is similarly made for sequen- tial paths [11, 12, 26].)To empirically validate our insight, we studie

42、d the input constraints to reuse schedules for five programs, including a parallel compression utility PBZip2; the Apache web server; and three scientific programs fft, lu, and barnes in SPLASH2. Table 1 shows the result

43、s for all programs studied. We found that the input constraints were often general, allowing frequent reuses of sched- ules. For instance, PBZip2 can use the same schedule to compress many different files, as long as the