0

I came across the definiton of Dovetailing which I had not heard of before and first thing that came to my mind was Concurrency. However, I couldn't find any post relating these two concepts. I also read this.

If I'm not mistaken, dovetailing is somehow related to turing machines and rather theoretical but both of them are, intuitively, about distributing a source: execute a bit of from this process and that process according to some predefined scheduling or set of rules.

My question here is, what's the difference?Or are they not comparable concepts, at all?

Community
  • 1
  • 1
MGoksu
  • 510
  • 6
  • 13

3 Answers3

1

Dovetailing isn't theoretical at all. Any OS allowing multiple processes or threads uses dovetailing. Otherwise a single-core PC wouldn't be capable of handling multiple processes or threads. Dovetailing would be a method to implement concurrent entities, like threads. But concurrency can be handled differently as well. E.g. parallel computing can be handled by GPUs and most modern CPUs have multiple cores allowing concurrent execution without dovetailing.

1

In context of threads, Dovetailing seems more close to preemptive multi-threading if we are preferring breadth-first as discussed in Wikipedia page

Preemptive multi-threading, force each thread to leave CPU (time slice) and after sometime, (nano sec) gives control to other threads. Going breadth-wise rather than depth-wise

1

The main purpose of dovetailing in theory is to show how you can reach the end point of any of an infinite list of computations/tasks (if there is such an end point, i.e. the computation stops) within a finite number of steps. If you work on the computations sequentially, then anything after the first non-halting process will not be executed any more.

If the list of processes is not infinite, then you may as well execute the first instruction o all of them, then the second and so on. The "diagonal" idea is not necessary. Infinite lists of processes are probably not so relevant in concurrency.

Peter Leupold
  • 1,162
  • 1
  • 9
  • 16