TUD Logo

TUD Home » ... » Teaching » Real-Time Systems » Time and Order

Operating Systems

Exercise: Time and Order

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 types of events are received by two nodes comprising a system. Each node receives one event type and logs the receive time. From those logs, we want to later establish chronological order, whenever two events arrived at least 150µs apart. Given a drift rate of 10-5 and a latency jitter of 20µs between both clocks, how often must both clocks be synchronized? 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)
Last modified: 20th Nov 2017, 5.58 PM
Author: Dr.-Ing. Michael Roitzsch

Michael Roitzsch

Phone: 463 42043
Fax: 463 38284
e-mail contact form

  • ModuleModules: INF-BAS4, INF-VERT4, DSE-E9, INF-LE-EUI
  • Credits6 Credit Points
  • 2/1/0 = 3 SWS
Time and Place

This course is not being offered in this term.