3

我需要实现一个使用带有 peek() 方法的队列的共识协议，以表明可以为任意数量的线程达成共识，即带有 peek() 方法的队列具有无限的共识数

这是我的代码

import java.util.LinkedList;
import java.util.Queue;
public class PeekConsensus extends ConsensusProtocol<Integer>   
{
    Queue<Integer> queue ;
    public PeekConsensus(int threadCount)   
    {
        super(threadCount); //threadCount is a command line argument from the main class specifying the number of threads to handle this process 
        queue = new LinkedList<Integer>() //FIFO queue
    }

    public Integer decide(Integer value)    
    {
        this.propose(value); // stores "value" in a vector named proposed, at index ThreadID.get()  
        int i = ThreadID.get() ;
        queue.add(i) 
        System.out.println("Thread " + i + " : " + i) ; // Required by specifications to print thread id and the value added when an item is enqueued 
        System.out.println("Thread " + i + " : " + queue.peek()) ; // Required by specifications to print thread id and the value of peek() when when peek() is called
        return proposed.elementAt(queue.peek()) ;

    }   
}

据我了解，这应该可行，因为如果两个线程返回不同的值， peek() 将必须返回不同的线程 id 并确保有效性，因为每个线程在推送其线程 id 之前将其自己的值写入建议中。

有没有人能够弄清楚我哪里出错并指导我纠正我的代码

4

1 回答 1

3

该协议对我来说看起来不错。但是你有没有想过是如何peek()实现的？因为peek()真的是 apop()后跟 a，所以push()我们在这段代码中可能会有不好的交错。假设peek()可以以原子方式执行，该共识协议将起作用。

你怎么能改变它？

为了让您的代码运行，您可以添加synchronized到peek()，但这会破坏共识协议的目的，因为持有锁的线程可能会死掉。

尝试使用AtomicReference. 这使您可以原子地获取，甚至设置一个值。在这种情况下，指针将是head.

现在问题来了：AtomicReferenceJava是如何实现的。不幸的是，它是使用 a 实现的CAS，这再次破坏了仅使用 FIFO 队列的共识协议的目的。

最后：正式地，FIFO 队列的共识编号为 2。假设peek()是原子执行的，您的协议是有效的。但是，正确的实现需要某种CASor synchronized。

于 2017-08-22T07:57:17.860 回答