11.5 M/G/1 with Vacations
The previous analysis of an M/G/1 queue assumes that the server works non-stop as long as there are customers in the system. This property is also referred to as being "work conserving." In some situations, the server may decide to take a break (say to get coffee) when the system is empty. There are several natural cases where this type of situation occurs. For example, a storage subsystem may use idle periods to commit to disk all writes that are in the buffer. In this case, a newly arriving I/O request will have to wait until the buffer is flushed before it is served. As another example, a server may start a preventive maintenance procedure as soon as it becomes idle. Another example arises in enterprise grid environments, where idle processors (e.g., workstations) are claimed by remote applications. When the owner of the workstation returns, an extra delay is experienced while the remote application is checkpointed, preempted by the returning owner, and migrated back to the remote client.
The following results for an M/G/1 queue with vacations assumes that:
The average waiting time for an M/G/1 system with vacations is given in Eq. (11.5.18). The first term is the regular M/G/1 expression of Eq. (11.4.14). The second term is the average residual vacation time (i.e., the average time an arriving customer has to wait for the server to return from vacation).
A computer system serves requests that arrive from a Poisson process at a rate of 0.2 requests/sec. The processing time characteristics of a request are E[S] = 3.5 sec and Cs = 0.3. When there are no requests to be processed, the system performs a preventive maintenance procedure that lasts one second, on average, and has a coefficient of variation equal to 2. When the maintenance procedure is complete, the system resumes to serve requests if there are any in the queue. Otherwise, the system starts another maintenance procedure. What is the average waiting time of a request?
The value of r is 0.7 (= 0.2 x 3.5). In order to use Eq. (11.5.18), the second moment of the vacation time is required. Since, it follows that
Using Eqs. (11.5.18) and (11.5.19) with the numerical values given in the example, W can be computed as:
Table 11.1 gives a comparison of two M/G/1 queues: one with vacations and one without. The average vacation time is varied. As it can be seen, the average waiting time is tripled when the average vacation (i.e., maintenance) time is equal to the average service time (i.e., when E[V] = E[S] = 3.5 sec). Thus, having an otherwise idle processor begin service immediately (i.e., with no vacation time) on an arriving customer improves performance nontrivially.