TUD Logo

TUD Startseite » ... » Lehre » Echtzeitsysteme » Zeit und Reihenfolge


against racism

Übung: Zeit und Reihenfolge

Notions of Time

  1. Time in general
    1. Describe a situation where drifting clocks in a distributed system may lead to problems.
  2. Global time
    1. Given a latency jitter of 20µs, a clock drift rate of 10-5, and a resynchronization period of 1 second, what precision can be achieved by a central master algorithm?
    2. Two events occurring with a time-lag of 150µs are received by two nodes comprising a system. Each node receives one event and ascertains the receive time. Given a drift rate of 10-5 and a latency jitter of 20µs between both clocks, how often must both clocks be synchronized if a chronological order shall be established? What precision can be achieved that way?
  3. Vector time
    1. Amend the diagram with the missing vector times. Use [0000] as initialization.
    2. Which causal dependencies can be retrieved from the diagram?
    3. Name two event pairs about which you can not retrieve dependency information and justify them with vector time properties.
    4. Move events b, d, and j to the right as far as possible, without destroying causal dependencies. Substantiate your actions.

    vector time

  4. Relative vs. Absolute Timeouts

    Imagine you should write a program whose worker function work() shall be called truly periodically every 10ms. The function takes about 1ms to execute on average. The operating system is a preemptive multitasking system with other load also. The program has soft-real-time requirements, that is, in overload situations the execution of work() may be deferred or skipped. However, there must be no permanent drift in phase.

    1. Explain the problems with the following program:
      while (1) {
    2. Explain the problems with the following program:
      while (1) {
      start = now();
      end = now();
      delay = 10ms - (end - start);
    3. Now write a program which solves the problems of a) and b). You can use the following primitives:
      now() returns the current time
      sleep(time) sleeps a certain amount of time (blocks)
      sleep_until(time) sleeps until a certain time in the future (blocks)
      atomic {
      /* code */
      executes some code statements atomically (without scheduling by the operating system)
      If you block inside this statement the atomicity guarantee only holds until you block.
      work() the work function (may block for a short time)
Stand: 21.11.2013, 18:34 Uhr
Autor: Dr.-Ing. Michael Roitzsch

Michael Roitzsch

Tel.: 463 42043
Fax: 463 38284

  • ModuleModule: INF-BAS4, INF-VERT4, DSE-E9, INF-LE-EUI
  • Credits6 Leistungspunkte
  • 2/1/0 = 3 SWS
Zeit und Ort
  • Vorlesung, wöchentlich
    TimeDo, 14:50 Uhr PlaceAPB E006
  • Übung, zweiwöchentlich
    TimeDo, 16:40 Uhr PlaceAPB E006