创建一个类,模拟一个信号量,但许可证数永远不应超过0。

huangapple go评论64阅读模式
英文:

Creating a class that mimics a semaphore but the number of permits should never exceed 0

问题

我遇到了一个问题,需要使用信号量设计一个队列,以便所有获取它的线程在某个线程释放它们之前必须等待。但是关键在于,如果在没有线程等待的情况下调用释放操作,则不应产生任何影响,就像真正的信号量一样,不会添加额外的许可。我开始尝试像这样的方法:

public class QueueOfThreads {
	
	private Semaphore valve = new Semaphore(0);
	volatile int count = 0;
	
	public void acquire() throws InterruptedException {
		synchronized(this) {
			count++;
		}
		valve.acquire();
	}
	
	public void release() {
		synchronized(this) {
			if(count > 0) {
				valve.release();
				count--;
			}
			else {
				System.out.println("将不会释放,因为没有线程在等待");
			}
		}
	}
}

但是我发现这是错误的,因为如果在count++之后抢占了线程,那么在获取之前可能会调用释放。

我花了很多时间尝试找到一种方法,以确保至少在任何释放操作之前调用一次获取操作。但我总是遇到同样的问题,我无法在获取信号量后向其他线程发出获取信号的信号,因为当前线程将处于等待状态。但是,如果我在获取信号量之前发出信号,那么在线程实际获取信号量之前,可能会发生抢占。

如果可能的话,请告诉我如何编写这样的类,以及如何解决这个问题?

这个问题来自于一本名为《The Little Book of Semaphores》的书中的评论,作者是Allen B. Downey,在评论中提到:

“信号量还可以用来表示队列。在这种情况下,初始值为0,并且通常编写的代码不可能在没有线程等待的情况下发出信号,因此信号量的值永远不会是正数。”

英文:

I came across a problem to design a queue using a semaphore such that all threads that acquire it must wait until some thread releases them. But the catch here is that if release is called when no thread is waiting then it should not have any effect unlike a real semaphore where an extra permit will be added. I started trying something like this:

public class QueueOfThreads {
	
	private Semaphore valve = new Semaphore(0);
	volatile int count = 0;
	
	
	public void acquire() throws InterruptedException {
		synchronized(this) {
			count++;
		}
		valve.acquire();
	}
	
	public void release() {
		synchronized(this) {
			if(count > 0) {
				valve.release();
				count--;
			}
			else {
				System.out.println("will not release since no thread is waiting");
			}
		}
	}

}

But I can see that this is wrong since if a thread is preempted after count++ then the release can be called before acquire.

I spent a lot of time trying to find a way to make sure that at least one acquire is called before any release. But I always end up with the same problem, I can not signal to other threads about acquiring the semaphore after the semaphore is acquired since the current thread will be in waiting state. But if I signal before acquiring the semaphore then the thread can be preempted before the semaphore is actually acquired.

Please let me know if writing a class like this is possible and how to do it?

This problem came to me from a comment in a book called "The Little Book of Semaphores" By Allen B. Downey where it is mentioned that:

"Semaphores can also be used to represent a queue. In this case, the initial value is 0, and usually the code is written so that it is not possible to signal unless there is a thread waiting, so the value of the semaphore is never positive."

答案1

得分: 1

你可以利用 Object.notify(),它会释放一个等待的线程(如果有的话):

public class QueueOfThreads {

  public synchronized void acquire() throws InterruptedException {
    wait();
  }

  public synchronized void release() {
    notify();
  }
}

然而,这只在没有虚假唤醒(spurious wakeup)的 JVM 上起作用。
如果可能会发生虚假唤醒,那么实现就会更复杂:

public class QueueOfThreads {
  int threadCount = 0;
  boolean notified = false;

  public synchronized void acquire() throws InterruptedException {
    threadCount++;
    do {
      wait();
    } while (!notified);
    threadCount--;
    notified = false;
  }

  public synchronized void release() {
    if (threadCount==0) {
      return;
    }
    notified = true;
    notify();
  }
}
英文:

You can exploit Object.notify() which frees exactly one waiting thread, if any:

public class QueueOfThreads {

  public synchronized void acquire() throws InterruptedException {
    wait();
  }

  public synchronized void release() {
    notify();
  }
}

However, this works only on JVM without spurious wakeups.
If spurious wakeup can happen, then the implementation is more complex:

public class QueueOfThreads {
  int threadCount = 0;
  boolean notified = false;

  public synchronized void acquire() throws InterruptedException {
    threadCount++;
    do {
      wait();
    } while (!notified);
    threadCount--;
    notified = false;
  }

  public synchronized void release() {
    if (threadCount==0) {
      return;
    }
    notified = true;
    notify();
  }
}

huangapple
  • 本文由 发表于 2020年9月21日 01:17:27
  • 转载请务必保留本文链接:https://go.coder-hub.com/63981682.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定