    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      http://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017package org.apache.commons.lang3.concurrent;
    018
    019import org.apache.commons.lang3.Validate;
    020
    021import java.util.concurrent.ScheduledExecutorService;
    022import java.util.concurrent.ScheduledFuture;
    023import java.util.concurrent.ScheduledThreadPoolExecutor;
    024import java.util.concurrent.TimeUnit;
    025
    026/**
    027 * <p>
    028 * A specialized <em>semaphore</em> implementation that provides a number of
    029 * permits in a given time frame.
    030 * </p>
    031 * <p>
    032 * This class is similar to the {@code java.util.concurrent.Semaphore} class
    033 * provided by the JDK in that it manages a configurable number of permits.
    034 * Using the {@link #acquire()} method a permit can be requested by a thread.
    035 * However, there is an additional timing dimension: there is no {@code
    036 * release()} method for freeing a permit, but all permits are automatically
    037 * released at the end of a configurable time frame. If a thread calls
    038 * {@link #acquire()} and the available permits are already exhausted for this
    039 * time frame, the thread is blocked. When the time frame ends all permits
    040 * requested so far are restored, and blocking threads are waked up again, so
    041 * that they can try to acquire a new permit. This basically means that in the
    042 * specified time frame only the given number of operations is possible.
    043 * </p>
    044 * <p>
    045 * A use case for this class is to artificially limit the load produced by a
    046 * process. As an example consider an application that issues database queries
    047 * on a production system in a background process to gather statistical
    048 * information. This background processing should not produce so much database
    049 * load that the functionality and the performance of the production system are
    050 * impacted. Here a {@code TimedSemaphore} could be installed to guarantee that
    051 * only a given number of database queries are issued per second.
    052 * </p>
    053 * <p>
    054 * A thread class for performing database queries could look as follows:
    055 * </p>
    056 *
    057 * <pre>
    058 * public class StatisticsThread extends Thread {
    059 *     // The semaphore for limiting database load.
    060 *     private final TimedSemaphore semaphore;
    061 *     // Create an instance and set the semaphore
    062 *     public StatisticsThread(TimedSemaphore timedSemaphore) {
    063 *         semaphore = timedSemaphore;
    064 *     }
    065 *     // Gather statistics
    066 *     public void run() {
    067 *         try {
    068 *             while(true) {
    069 *                 semaphore.acquire();   // limit database load
    070 *                 performQuery();        // issue a query
    071 *             }
    072 *         } catch(InterruptedException) {
    073 *             // fall through
    074 *         }
    075 *     }
    076 *     ...
    077 * }
    078 * </pre>
    079 *
    080 * <p>
    081 * The following code fragment shows how a {@code TimedSemaphore} is created
    082 * that allows only 10 operations per second and passed to the statistics
    083 * thread:
    084 * </p>
    085 *
    086 * <pre>
    087 * TimedSemaphore sem = new TimedSemaphore(1, TimeUnit.SECOND, 10);
    088 * StatisticsThread thread = new StatisticsThread(sem);
    089 * thread.start();
    090 * </pre>
    091 *
    092 * <p>
    093 * When creating an instance the time period for the semaphore must be
    094 * specified. {@code TimedSemaphore} uses an executor service with a
    095 * corresponding period to monitor this interval. The {@code
    096 * ScheduledExecutorService} to be used for this purpose can be provided at
    097 * construction time. Alternatively the class creates an internal executor
    098 * service.
    099 * </p>
    100 * <p>
    101 * Client code that uses {@code TimedSemaphore} has to call the
    102 * {@link #acquire()} method in each processing step. {@code TimedSemaphore}
    103 * keeps track of the number of invocations of the {@link #acquire()} method and
    104 * blocks the calling thread if the counter exceeds the limit specified. When
    105 * the timer signals the end of the time period the counter is reset and all
    106 * waiting threads are released. Then another cycle can start.
    107 * </p>
    108 * <p>
    109 * An alternative to {@code acquire()} is the {@link #tryAcquire()} method. This
    110 * method checks whether the semaphore is under the specified limit and
    111 * increases the internal counter if this is the case. The return value is then
    112 * <strong>true</strong>, and the calling thread can continue with its action.
    113 * If the semaphore is already at its limit, {@code tryAcquire()} immediately
    114 * returns <strong>false</strong> without blocking; the calling thread must
    115 * then abort its action. This usage scenario prevents blocking of threads.
    116 * </p>
    117 * <p>
    118 * It is possible to modify the limit at any time using the
    119 * {@link #setLimit(int)} method. This is useful if the load produced by an
    120 * operation has to be adapted dynamically. In the example scenario with the
    121 * thread collecting statistics it may make sense to specify a low limit during
    122 * day time while allowing a higher load in the night time. Reducing the limit
    123 * takes effect immediately by blocking incoming callers. If the limit is
    124 * increased, waiting threads are not released immediately, but wake up when the
    125 * timer runs out. Then, in the next period more processing steps can be
    126 * performed without blocking. By setting the limit to 0 the semaphore can be
    127 * switched off: in this mode the {@link #acquire()} method never blocks, but
    128 * lets all callers pass directly.
    129 * </p>
    130 * <p>
    131 * When the {@code TimedSemaphore} is no more needed its {@link #shutdown()}
    132 * method should be called. This causes the periodic task that monitors the time
    133 * interval to be canceled. If the {@code ScheduledExecutorService} has been
    134 * created by the semaphore at construction time, it is also shut down.
    135 * resources. After that {@link #acquire()} must not be called any more.
    136 * </p>
    137 *
    138 * @since 3.0
    139 */
    140public class TimedSemaphore {
    141    /**
    142     * Constant for a value representing no limit. If the limit is set to a
    143     * value less or equal this constant, the {@code TimedSemaphore} will be
    144     * effectively switched off.
    145     */
    146    public static final int NO_LIMIT = 0;
    147
    148    /** Constant for the thread pool size for the executor. */
    149    private static final int THREAD_POOL_SIZE = 1;
    150
    151    /** The executor service for managing the timer thread. */
    152    private final ScheduledExecutorService executorService;
    153
    154    /** Stores the period for this timed semaphore. */
    155    private final long period;
    156
    157    /** The time unit for the period. */
    158    private final TimeUnit unit;
    159
    160    /** A flag whether the executor service was created by this object. */
    161    private final boolean ownExecutor;
    162
    163    /** A future object representing the timer task. */
    164    private ScheduledFuture<?> task; // @GuardedBy("this")
    165
    166    /** Stores the total number of invocations of the acquire() method. */
    167    private long totalAcquireCount; // @GuardedBy("this")
    168
    169    /**
    170     * The counter for the periods. This counter is increased every time a
    171     * period ends.
    172     */
    173    private long periodCount; // @GuardedBy("this")
    174
    175    /** The limit. */
    176    private int limit; // @GuardedBy("this")
    177
    178    /** The current counter. */
    179    private int acquireCount;  // @GuardedBy("this")
    180
    181    /** The number of invocations of acquire() in the last period. */
    182    private int lastCallsPerPeriod; // @GuardedBy("this")
    183
    184    /** A flag whether shutdown() was called. */
    185    private boolean shutdown;  // @GuardedBy("this")
    186
    187    /**
    188     * Creates a new instance of {@link TimedSemaphore} and initializes it with
    189     * the given time period and the limit.
    190     *
    191     * @param timePeriod the time period
    192     * @param timeUnit the unit for the period
    193     * @param limit the limit for the semaphore
    194     * @throws IllegalArgumentException if the period is less or equals 0
    195     */
    196    public TimedSemaphore(final long timePeriod, final TimeUnit timeUnit, final int limit) {
    197        this(null, timePeriod, timeUnit, limit);
    198    }
    199
    200    /**
    201     * Creates a new instance of {@link TimedSemaphore} and initializes it with
    202     * an executor service, the given time period, and the limit. The executor
    203     * service will be used for creating a periodic task for monitoring the time
    204     * period. It can be <b>null</b>, then a default service will be created.
    205     *
    206     * @param service the executor service
    207     * @param timePeriod the time period
    208     * @param timeUnit the unit for the period
    209     * @param limit the limit for the semaphore
    210     * @throws IllegalArgumentException if the period is less or equals 0
    211     */
    212    public TimedSemaphore(final ScheduledExecutorService service, final long timePeriod,
    213            final TimeUnit timeUnit, final int limit) {
    214        Validate.inclusiveBetween(1, Long.MAX_VALUE, timePeriod, "Time period must be greater than 0!");
    215
    216        period = timePeriod;
    217        unit = timeUnit;
    218
    219        if (service != null) {
    220            executorService = service;
    221            ownExecutor = false;
    222        } else {
    223            final ScheduledThreadPoolExecutor s = new ScheduledThreadPoolExecutor(
    224                    THREAD_POOL_SIZE);
    225            s.setContinueExistingPeriodicTasksAfterShutdownPolicy(false);
    226            s.setExecuteExistingDelayedTasksAfterShutdownPolicy(false);
    227            executorService = s;
    228            ownExecutor = true;
    229        }
    230
    231        setLimit(limit);
    232    }
    233
    234    /**
    235     * Returns the limit enforced by this semaphore. The limit determines how
    236     * many invocations of {@link #acquire()} are allowed within the monitored
    237     * period.
    238     *
    239     * @return the limit
    240     */
    241    public final synchronized int getLimit() {
    242        return limit;
    243    }
    244
    245    /**
    246     * Sets the limit. This is the number of times the {@link #acquire()} method
    247     * can be called within the time period specified. If this limit is reached,
    248     * further invocations of {@link #acquire()} will block. Setting the limit
    249     * to a value &lt;= {@link #NO_LIMIT} will cause the limit to be disabled,
    250     * i.e. an arbitrary number of{@link #acquire()} invocations is allowed in
    251     * the time period.
    252     *
    253     * @param limit the limit
    254     */
    255    public final synchronized void setLimit(final int limit) {
    256        this.limit = limit;
    257    }
    258
    259    /**
    260     * Initializes a shutdown. After that the object cannot be used any more.
    261     * This method can be invoked an arbitrary number of times. All invocations
    262     * after the first one do not have any effect.
    263     */
    264    public synchronized void shutdown() {
    265        if (!shutdown) {
    266
    267            if (ownExecutor) {
    268                // if the executor was created by this instance, it has
    269                // to be shutdown
    270                getExecutorService().shutdownNow();
    271            }
    272            if (task != null) {
    273                task.cancel(false);
    274            }
    275
    276            shutdown = true;
    277        }
    278    }
    279
    280    /**
    281     * Tests whether the {@link #shutdown()} method has been called on this
    282     * object. If this method returns <b>true</b>, this instance cannot be used
    283     * any longer.
    284     *
    285     * @return a flag whether a shutdown has been performed
    286     */
    287    public synchronized boolean isShutdown() {
    288        return shutdown;
    289    }
    290
    291    /**
    292     * Acquires a permit from this semaphore. This method will block if
    293     * the limit for the current period has already been reached. If
    294     * {@link #shutdown()} has already been invoked, calling this method will
    295     * cause an exception. The very first call of this method starts the timer
    296     * task which monitors the time period set for this {@code TimedSemaphore}.
    297     * From now on the semaphore is active.
    298     *
    299     * @throws InterruptedException if the thread gets interrupted
    300     * @throws IllegalStateException if this semaphore is already shut down
    301     */
    302    public synchronized void acquire() throws InterruptedException {
    303        prepareAcquire();
    304
    305        boolean canPass;
    306        do {
    307            canPass = acquirePermit();
    308            if (!canPass) {
    309                wait();
    310            }
    311        } while (!canPass);
    312    }
    313
    314    /**
    315     * Tries to acquire a permit from this semaphore. If the limit of this semaphore has
    316     * not yet been reached, a permit is acquired, and this method returns
    317     * <strong>true</strong>. Otherwise, this method returns immediately with the result
    318     * <strong>false</strong>.
    319     *
    320     * @return <strong>true</strong> if a permit could be acquired; <strong>false</strong>
    321     * otherwise
    322     * @throws IllegalStateException if this semaphore is already shut down
    323     * @since 3.5
    324     */
    325    public synchronized boolean tryAcquire() {
    326        prepareAcquire();
    327        return acquirePermit();
    328    }
    329
    330    /**
    331     * Returns the number of (successful) acquire invocations during the last
    332     * period. This is the number of times the {@link #acquire()} method was
    333     * called without blocking. This can be useful for testing or debugging
    334     * purposes or to determine a meaningful threshold value. If a limit is set,
    335     * the value returned by this method won't be greater than this limit.
    336     *
    337     * @return the number of non-blocking invocations of the {@link #acquire()}
    338     * method
    339     */
    340    public synchronized int getLastAcquiresPerPeriod() {
    341        return lastCallsPerPeriod;
    342    }
    343
    344    /**
    345     * Returns the number of invocations of the {@link #acquire()} method for
    346     * the current period. This may be useful for testing or debugging purposes.
    347     *
    348     * @return the current number of {@link #acquire()} invocations
    349     */
    350    public synchronized int getAcquireCount() {
    351        return acquireCount;
    352    }
    353
    354    /**
    355     * Returns the number of calls to the {@link #acquire()} method that can
    356     * still be performed in the current period without blocking. This method
    357     * can give an indication whether it is safe to call the {@link #acquire()}
    358     * method without risking to be suspended. However, there is no guarantee
    359     * that a subsequent call to {@link #acquire()} actually is not-blocking
    360     * because in the mean time other threads may have invoked the semaphore.
    361     *
    362     * @return the current number of available {@link #acquire()} calls in the
    363     * current period
    364     */
    365    public synchronized int getAvailablePermits() {
    366        return getLimit() - getAcquireCount();
    367    }
    368
    369    /**
    370     * Returns the average number of successful (i.e. non-blocking)
    371     * {@link #acquire()} invocations for the entire life-time of this {@code
    372     * TimedSemaphore}. This method can be used for instance for statistical
    373     * calculations.
    374     *
    375     * @return the average number of {@link #acquire()} invocations per time
    376     * unit
    377     */
    378    public synchronized double getAverageCallsPerPeriod() {
    379        return periodCount == 0 ? 0 : (double) totalAcquireCount
    380                / (double) periodCount;
    381    }
    382
    383    /**
    384     * Returns the time period. This is the time monitored by this semaphore.
    385     * Only a given number of invocations of the {@link #acquire()} method is
    386     * possible in this period.
    387     *
    388     * @return the time period
    389     */
    390    public long getPeriod() {
    391        return period;
    392    }
    393
    394    /**
    395     * Returns the time unit. This is the unit used by {@link #getPeriod()}.
    396     *
    397     * @return the time unit
    398     */
    399    public TimeUnit getUnit() {
    400        return unit;
    401    }
    402
    403    /**
    404     * Returns the executor service used by this instance.
    405     *
    406     * @return the executor service
    407     */
    408    protected ScheduledExecutorService getExecutorService() {
    409        return executorService;
    410    }
    411
    412    /**
    413     * Starts the timer. This method is called when {@link #acquire()} is called
    414     * for the first time. It schedules a task to be executed at fixed rate to
    415     * monitor the time period specified.
    416     *
    417     * @return a future object representing the task scheduled
    418     */
    419    protected ScheduledFuture<?> startTimer() {
    420        return getExecutorService().scheduleAtFixedRate(new Runnable() {
    421            @Override
    422            public void run() {
    423                endOfPeriod();
    424            }
    425        }, getPeriod(), getPeriod(), getUnit());
    426    }
    427
    428    /**
    429     * The current time period is finished. This method is called by the timer
    430     * used internally to monitor the time period. It resets the counter and
    431     * releases the threads waiting for this barrier.
    432     */
    433    synchronized void endOfPeriod() {
    434        lastCallsPerPeriod = acquireCount;
    435        totalAcquireCount += acquireCount;
    436        periodCount++;
    437        acquireCount = 0;
    438        notifyAll();
    439    }
    440
    441    /**
    442     * Prepares an acquire operation. Checks for the current state and starts the internal
    443     * timer if necessary. This method must be called with the lock of this object held.
    444     */
    445    private void prepareAcquire() {
    446        if (isShutdown()) {
    447            throw new IllegalStateException("TimedSemaphore is shut down!");
    448        }
    449
    450        if (task == null) {
    451            task = startTimer();
    452        }
    453    }
    454
    455    /**
    456     * Internal helper method for acquiring a permit. This method checks whether currently
    457     * a permit can be acquired and - if so - increases the internal counter. The return
    458     * value indicates whether a permit could be acquired. This method must be called with
    459     * the lock of this object held.
    460     *
    461     * @return a flag whether a permit could be acquired
    462     */
    463    private boolean acquirePermit() {
    464        if (getLimit() <= NO_LIMIT || acquireCount < getLimit()) {
    465            acquireCount++;
    466            return true;
    467        }
    468        return false;
    469    }
    470}