Discrete Mathematics for Computer Science

Application: Scheduling a Meeting Facility 395

would like to begin its meeting at the same time the first organization is completing its

program committee meeting.

At any point in time, we can build a model of the resource requests and allocation for

this meeting facility using a directed graph. An edge (a, b) where

a E {Organization One, Organization Two}

and

b E {Meeting Room, Slide Projector, Lobby}

indicates that group a has requested resource b, whereas (b, a) indicates that group a has

been allocated resource b. Assuming that Organization Two has scheduled the large meet-

ing room and Organization One is completing its use of the slide projector in the lobby,

a model at the time the meeting of the second organization is about to begin is shown in

Figure 6.55.

* Lobby

Organization One • Meeting Room

Organization Two Slide Projector

allocated 4---- requested

Figure 6.55 Model of meeting facility.

From examining the model, it is clear that neither organization can continue its meet-
ing, because a resource needed by each organization is assigned to the other organization,
which has no plan to release it.
The graph of the meeting facility's resource allocation clearly is dependent on the
particular time the model represents. For example, the meeting facility would be repre-
sented by the directed graph shown in Figure 6.56 for the case that Organization One is
completing its meeting just as Organization Two is scheduled to begin its meeting.

* Lobby

Organization One • Meeting Room

Organization Two Slide Projector

allocated requested

Figure 6.56 A second model of the meeting facility.

Although this model is given in terms of organizations and meeting facilities, the same
problem arises in an operating system when two programs request the same printer, tape
drive, or disk drive at the same time.