SERIALIZER

- by Charles Peri

Serializers were first developed by Carl E. Hewitt and Russell R. Atkinson in 1976 as a tool for synchronization technique in operating systems.

Definition:
Serializers are abstract data types defined by a set of procedures ( or operations ) and can encapsulate the shared resources to form a protected resource object.

Serializers are abstract data types very similar to monitors. As in a Monitor only one process can have accesses or control over a serializer at a given time. The operations users invoke to access a resource are actually the operations of the serializers. When a process access a serializer it gains control of the serializer and is said to be in possession of the serializer. But in the procedures of a serializer there are certain regions in which multiple process can be active. These regions are known as Hollow regions. As soon as a process enters a hollow region, it releases the serializer so that some other process can access it. Thus concurrency is achieved in the hallow regions of a serializer. Remember that in a hollow region the process just releases the serializer and does not exit it. So that the process can regain control when it gets out of the hollow region.

whenever a process requests to gain or regain access of a serializer certain conditions are checked. The process is held in a waiting queue until the condition is true. This is accomplished using an enque operation. The syntax of the enque command is

	enque (<priority>, <queue-name>) until (<condition>)

The queue name specifies the name of the queue in which the process has to be held and the priority options specifies the priority of the process to be delayed.

A hallow region in a procedure is specified by a join-crowd operation. The syntax of the join-crowd command is

	join-crowd (<crowd>) then <body> end

On invocation of a join-crowd operation, possession of the serializer is released, the identity of the process invoking the join-crowd is recorded in the crowd, and the list of statements in the body is executed.

When the process completes execution of the body, a leave-crowd operation is executed. As a result of the leave-crowd operation the process regains control of the serializer. Please note that, if the serializer is currently in possession of some other process then the process executing the leave crowd operation will result in a wait queue.

The operation of a serializer can be explained by the following figure:

As shown in the above figure, every operation in a serializer can be identified as an event. An Entry event can be a request for serializer, in which a condition will be checked. ( For eg., Is the serializer free for the process to enter ? ) If the condition is true the process gains control of the serializer. Then before the process accesses the resource, a guarantee event is executed. The guarantee event results in an established event if the condition is true, else the process releases the control of the serializer and waits in its queue. When a resource is available the process enters (Join-Crowd event) the Crowd and accesses the process. After completing the job with the resource, the process leaves (Leave-Crowd event) the crowd and regains control of the serializer ( if the serializer is available, else it has to wait).

serializers also allow a timeout event which can avoid processes waiting for a condition longer than the specified period.

Readers - Writers Problem

The readers priority solution to the Readers - Writers problem is given by the following code:


readerwriter :  serializer
Var

	readq : queue ;
	writeq : queue ;
	rcrowd : crowd ; (* readers crowd *)
	wcrowd : crowd ; (* writers crowd *)
	db : database ;   (* the shared resource *)

Procedure read (k:key; var data : datatype) ;

	begin
	enque (readq)  until empty(wcrowd) ; 
	joincrowd (rcrowd) then

	     data := read-opn(db[key]) ;
	     end

	return(data) ;

end read ;



Procedure write (k:key; var data : datatype) ;

        begin
        enque (writeq)  until 
	(empty(wcrowd) AND empty(rcrowd) AND empty(readq)) ;;
        joincrowd (wcrowd) then

             write-opn(db[key]), data ;
             end

end write ;

The enque operation in the above code acts as a combination of both the entry and guarantee event. The enque operation in the read procedure ensures that the writers crowd is empty before a reader can enter the serializer. In the write procedure the condition makes sure that both the readers and writers crowd are empty. Thus for a writer to access the database, he should be the only user of the resource. But the condition enables the readers to access the database concurrently.

In the readers-writers problem we don't have a leave crowd operation, since when the process completes the operation with the resource it does not require to regain control of the serializer. When a reader or writer finishes accessing the database, they release the resource and simply exit from the serializer.

The conditions in the enque operation can be changed for different priorities. In the above solution as long as there is a reader in the crowd, another reader can also start reading. Also the reader is favored in all situations, making it a readers priority solution. If the enque command in the write procedure is changed as follows,

	enque (writeq) until 
	(empty(wcrowd) AND empty(rcrowd)) ;

then the solution is a weak reader's priority. That is, a writer does not have to wait for the readq to become empty. Thus when a writer completes execution and leaves, either a writer or reader (if both are waiting) will be chosen randomly.

Similarly the conditions can be changed to obtain a writers priority solution.

Automatic Signalling

As we can see in the above example, when a process releases the serializer, no explicit signal is sent to other waiting processes. The signalling is done automatically in a serializer. The programmer does not worry about the signalling process and it is implemented at the operating systems level. One way of implementing the automatic signal is to check periodically whether the condition is met for the waiting process. A better implementation is to check the queue conditions whenever the serializer or the resource is released.

We have to check for the both the release of the serializer and resource. For eg., When a reader enters the crowd, the serializer is released. The conditions checks true at this time for another reader to enter the crowd. But when a writer enters the crowd the serializer is released, but no other process can enter the crowd. Another process can enter only when the writer leaves the crowd by releasing the resource. Thus it is necessary to check for both the release of the serializer and the resource.

Monitors vs Serializers

Serializers have several advantages over the monitors.

Only one process can execute inside a monitor.
Only one process can have possession of the serializer at a time. But in the hollow regions the process releases the control and thereby facilitates several process to execute concurrently inside the hollow region of the serializers.
Nesting of monitors can cause deadlock. If inner process is waiting the outer one will be tied up.
Nesting of serializers are allowed in the hollow regions.
In monitors the conditions are not clearly stated to exit from a wait state.
The conditions are clearly stated for an event to occur in a serializer.
In monitors - explicit signalling.
In serializers implicit signalling.

Drawbacks

More complex and hence less efficient.
wcrowd and rcrowd are not merely counter but complex data structures that store the identity of the processes.
Automatic signalling process increases overhead, since whenever a resource or serializer is released all the conditions are to be checked for the waiting processes.

Questions

How do serializers solve several deficiencies of monitors ?
In the solution for the readers writers problem, as long as there is a reader in the crowd another reader will join and this might cause a writer to wait indefinitely. Explain how this can be avoided.
Explain with an example why it is necessary to check for both the release of resource and serializer in the implementation of automatic signalling.
Is it possible that no process can have possession of a serializer at a given time. Explain your answer.

References

Hewitt, C.E. and R. R. Atkinson, "Specification and Proof Techniques for Serializers," IEEE Transactions on Software Engineering, Jan. 1979, pp. 10-23.
Singhal, Mukesh, & Shivaratri, N. G., "Advanced Concepts in Operating Systems," Chapter 2, pp. 26 - 29.

Go Back to the Operating Systems page.