After I posed the riddle, more than a week ago, several people contributed suggestions and points of view.
- Shachar Shemesh suggested to implement a queue without locks. - Moish amended it with a suggestion to use a circular queue. - Baruch Siach suggested to try the userspace RCU library (http://lttng.org/urcu). - Ori Berger suggested a scheme utilizing a counter, a shadow value and a shadow counter. In a personal e-mail message, he made additional suggestions (such as having a look into http://www.concurrencykit.org/). - Guy Keren requested that the riddle be defined more precisely. - Also Ehud Karni contributed to the discussion. I found the RCU information to be fascinating. It validated my gut feeling that it is possible to utilize special cases of inter-process/thread information transfer to optimize the communication method. Once the communication method is optimized, it is possible to avoid a lot of process/thread synchronization overhead. As requested by Guy Keren, I'll restate the riddle. >>> Riddle restatement <<< System ------ Given an embedded system with real time processes. The system may have multiple processors (or multiple cores in the same processor) and it may be possible to execute instructions and memory accesses out of order. Processes --------- One process (process M - measurement) monitors some quantity (say, temperature) and makes measured values of the quantity available for another process (process A - action). Process A retrieves the measured quantity (such as temperature) once in a while and takes some action accordingly (such as turning a heater on or off). Goal ---- Devise a low-overhead mechanism for synchronizing between processes M and A to ensure that process A gets only consistent data from process M. Neither process shall be starved by the synchronization mechanism. Compromises ----------- Process M is activated periodically. However, if the system is loaded, it may skip some activations of M. Same - with process A. It is OK for process A's action to take place some time after the temperature has reached the threshold value/s for that action. It is OK for process A to skip some measurements and/or use a slightly out of date measurement value. It is also OK for process A to read more than once a single measurement made by process M. Therefore, it is not logically necessary to have a queue which stores all measurements made by process M for making them available, one by one, to process A. On the other hand, the data structure describing a measurement is several bytes long, so memory accesses, needed to update it, would not be atomic the way a one-byte long value (or 32-bit long value in a 32-bit system) can be updated atomically (all at once). All real data transfer is in one direction only (from process M to process A). Desired tradeoffs ----------------- The system has several pairs of measurement processes (like process M above) and action processes (like process A above), hence it is desirable to make any synchronization as lightweight as possible. It is also desirable to have an upper bound for the memory consumption of any queues or lists the implementation needs. It is not desirable (but harmless) to use memory barriers. >>> End of riddle restatement <<< It is probable that the theory, described in http://en.wikipedia.org/wiki/Concurrent_data_structure, would be relevant to the riddle. A paradigm, which could be useful, is described in http://en.wikipedia.org/wiki/Software_transactional_memory. --- Omer _______________________________________________ Linux-il mailing list Linux-il@cs.huji.ac.il http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
