22.1.7 Correctness of the Watcher (Why Locks are NOT Needed)

One might wonder whether locks are needed for the implementation of the watcher. In fact, this is not the case. The reason is that the watcher changes its state fully sequentially. No concurrent actor can access the state of the watcher and thus only the watcher has access to its partially changed states. The watcher is written such that it completes a state change before it takles the next one. Hence the watcher treats state sequentially, such that locking is not neede.

If the watcher would process all items concurrently then the state of the watcher might in fact become inconsistent. Consider for instance a situation where a new information item and a new agent are created concurrently. Suppose that we had the following numbers before of agents, information items and tasks before:

agents  infos   tasks
   2       3       4     % before
 
   3       3       7     % newAgent:
                         %   agents<-@agents+1
                         %   tasks<-@tasks+@infos
 
   3       4      10     % info         
                         %   infos<-@infos+1
                         %   tasks<-@tasks+@agents

The first operation of adding a new agent adds 4 new tasks and the second operation of adding a new information item adds 3 further tasks.

But now suppose that the operations of adding new agents or new tasks can be preempted. Then we could obtain the following sequence of state changes:

agents  infos   tasks
   2       3       4     % before
 
   3       3       4     % newAgent:  
                         %    agents<-@agents+1 ...
 
   3       4       4     % info             
                         %    infos<-@infos+1 ...
 
   3       4       8     % newagent:
                         % ... tasks<-@tasks+@infos
 
   3       4      11     % info:
                         % ... tasks<-@tasks+@agents

In fact this result is wrong, since there is one tasks to much, i.e. one task has been counted twice.

Hence, we have to ensure that state change of the watcher is atomic! In the implementation given, we have made the watcher sequential for this reason. Alternativly, one can use a concurrent watcher with locks.


Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.3.99 (20050412)