A node becomes owner when it requests write access to a page. When a read copy of the page is requested, the owner's access is downgraded to read. If the owner wishes to write to that page again, it must request write access from the manager, who will invalidate all the read copies.
The copyset eliminates the need to broadcast page invalidations to all the nodes. Only those nodes having a read copy of the page need to be notified.
The Fault Handlers handle page requests from local processes. The Servers handle page requests from other nodes.
Access costs are constant with this algorithm. Each request on a non-manager node requires four messages. Each write request has the additional cost of sending invalidation messages. This algorithm can result in a bottleneck at the Central Manager node as the number of processors or page faults increases. The Dynamic Distributed Manager scheme was developed to address this problem.
Data structure at each processor: PTable
one entry per page
two fields per entry:
access - type of access this processor has to this page
(read/write/nil)
lock - used to lock access to page for syncronization
Data structure at central manager processor: Info (table)
one entry per page
three fields per entry
owner - processor that owns page
(processor with most recent write access)
copyset - list of processors that have copies of page
lock - used to lock access to page for syncronization
When two processes on the same processor request the same page, the locking mechanism prevents the processor from sending two requests to the owner of the page. The second local request will be blocked on the PTable lock and when the lock is released, the page will already reside on the processor.
If the manager receives write requests for the same page from two different processors, it will change ownership of the page to the first requestor and forward the second request to the new owner, possibly before the first requestor has finished aquiring ownership. The PTable lock at the first requestor node will cause the second request to wait until the node has ownership of the page.
Lock (PTable[page].lock) ;
IF I am manager THEN BEGIN
Lock (Info[page].lock) ;
Info[page].copyset :=
Info[page].copyset U {ManagerNode} ;
receive page from Info[page].owner ;
Unlock (Info[page].lock) ;
END ;
ELSE BEGIN
ask manager for read access to page & a copy of page ;
receive page ;
send confirmation to manager ;
END ;
PTable[page].access := read ;
Unlock (PTable[page].lock) ;
Read Server
Lock (PTable[page].lock) ;
IF I am owner THEN BEGIN
PTable[page].access := read ;
send copy of page
END ;
Unlock (PTable[page].lock) ;
IF I am manager THEN BEGIN
Lock (Info[page].lock) ;
Info[page].copyset :=
Info[page].copyset U {RequestNode} ;
ask Info[page].owner to send copy of page to RequestNode ;
receive confirmation from RequestNode ;
Unlock (Info[page].lock) ;
END ;
Write Fault Handler
Lock (PTable[page].lock) ;
IF I am manager THEN BEGIN
Lock (Info[page].lock) ;
Invalidate (page, Info[page].copyset) ;
Info[page].copyset := {} ;
Unlock (Info[page].lock) ;
END ;
ELSE BEGIN
ask manager for write access to page ;
receive page ;
send confirmation to manager ;
END ;
PTable[page].access := write ;
Unlock (PTable[page].lock) ;
Write Server
Lock (PTable[page].lock) ;
IF I am owner THEN BEGIN
send copy of page
PTable[page].access := nil ;
END ;
Unlock (PTable[page].lock) ;
IF I am manager THEN BEGIN
Lock (Info[page].lock) ;
Invalidate (page, Info[page].copyset) ;
Info[page].copyset := {} ;
ask Info[page].owner to send page to RequestNode ;
receive confirmation from RequestNode ;
Unlock (Info[page].lock) ;
END ;
You will probably notice that the servers need a test added to the code following "IF I am manager" to prevent the manager from asking for a page that it owns.
IF I am not owner THEN BEGIN
ask Info[page].owner to send page to RequestNode ;
END ;
