JeffreyZhao/gist:8630308

JeffreyZhao · 2014-01-27T06:24:57Z

各位同学，不看了啊，看不过来了，各种错误好浪费时间啊，啊哈哈。

@Lautitia 尤其不看你的，你每次贴的代码都乱其八糟，每次都让我来修，这次我不修了，也不看了。

Lautitia · 2014-01-27T06:27:53Z

@JeffreyZhao 表示无辜，Preview看上去都是好的

dawnbreaks · 2014-01-27T06:32:09Z

@JeffreyZhao 我的代码有问题？

一个线程，先调用Dispose，再调用Start，那么会出现什么情况。

调用Dispose啥也不干，然后调用Start启动计数器啊。这不符合题意么？

JeffreyZhao · 2014-01-27T06:37:13Z

@dawnbreaks

调用Dispose意味着要销毁对象，对象销毁以后的任何访问，都不会执行任何操作。

airekans · 2014-01-27T06:39:43Z

按照我的理解写了一下。
不过我的版本的Start Dispose语义和老赵的就不一样了。
在老赵的要求里面，没有详细的说Start并发调用的时候，函数返回是不是保证StartCore一定是调用完了，所以暂时先按我自己的理解写了。

public class LockCalculator : CalculatorBase {

    private readonly object _gate = new object();

    private enum Status {
        NotStarted,
        Starting,
        Started,
        Disposing,
        Disposed
    }

    private Status _status = Status.NotStarted;

    public override void Start() {
        lock (_gate) {
            if (_status != Status.NotStarted) {
                return;
            }
            _status = Status.Starting;
        }

        StartCore();
        lock (_gate) {
            if (_status == Status.Starting) {
                _status = Status.Started;
                return;
            }
        }
        // _status == Status.Disposing
        DisposeCore();
        lock (_gate) {
            _status = Status.Disposed;
        }
    }

    public override void Dispose() {
        lock (_gate) {
            if (_status == Status.NotStarted || _status == Status.Disposed) {
                _status = Status.Disposed;
                return;
            }
            else if (_status == Status.Starting) {
                _status = Status.Disposing;
                return;
            }
            else if (_status == Status.Started) {
                _status = Status.Disposing;
            }
            else if (_status == Status.Disposing) {
                return;
            }
        }
        // Status.Started -> Status.Disposing
        DisposeCore();
        lock (_gate) {
            _status = Status.Disposed;
        }
    }
}

dawnbreaks · 2014-01-27T06:41:33Z

    public override void Dispose() {

        if(_status == Status.Disposed) {
            return;
        } else if( _disposingFlag.compareAndSwap(0,1)) {

            try {

                if(_status == Status.NotStarted  || _status == Status.Starting || _status == Status.Started) {
                    lock (_gate) {
                        if( _status == Status.Started) {
                            DisposeCore();
                        } 
                        _status = Status.Disposed;
                    }
                }
            }finally {
                _disposingFlag.compareAndSwap(1,0);
            }
        }
    }

那简单，dispose这么改就可以了。汗，还有这一条。

dawnbreaks · 2014-01-27T06:42:22Z

@JeffreyZhao 现在对了吧，没注意到（6）这一条。

fengyj · 2014-01-27T06:42:24Z

这样应该对了吧...只有在StartCore被调用的时候，Dispose方法需要等其被执行完毕，其他时候只用update下Status就好了。（前面想岔了，想着是Start & Stop这样的成对的操作，所以在Dispose的时候没有等StartCore执行完。）

public class BigLockCalculator : CalculatorBase
{
    private int status = 0; // 0: not started; 1: starting; 2: started; 3: disposed
    private ManualResetEventSlim startRES = new ManualResetEventSlim(false);

    public override void Start()
    {
        if (status == 3)
            return;

        if (Interlocked.CompareExchange(ref this.status, 1, 0) == 0)
        {
            StartCore();
            Interlocked.CompareExchange(ref this.status, 2, 1);
            startRES.Set();
        }
    }

    public override void Dispose()
    {
        if (Interlocked.CompareExchange(ref this.status, 3, 0) == 0)
        {
            startRES.Dispose();
            return;
        }
        if (this.status == 1)
        {
            startRES.Wait();
        }
        if (Interlocked.CompareExchange(ref this.status, 3, 2) == 2)
        {
            DisposeCore();
            startRES.Dispose();
        }
    }
}

maximesong · 2014-01-27T06:54:49Z

public class BigLockCalculator : CalculatorBase {

private readonly object _gate = new object();
private readonly object _gate2 = new object();

private enum Status {
    NotStarted,
    Starting,
    Started,
    Disposed
}

private Status _status = Status.NotStarted;
private Status _status2 = Status.NotStarted;

public override void Start() {
    if (_status != Status.NotStarted)
        return;
    lock (_gate) {
        if (_status == Status.NotStarted) {
            _status == Status.Starting;
            StartCore();
            _status = Status.Started;
        }
    }
}

public override void Dispose() {
    if (_status != Status.Starting && _status != Status.Started)
        return;
    if (_status2 != Status.NotStarted) {
        return;
    }
    lock (_gate2) {
        if (_status2 == Status.NotStarted) {
            _status2 = Status.Started;
            lock (_gate) {
                if (_status == Status.Started) {
                    DisposeCore();
                    _status = Status.Disposed;
                }
            }
        }
    }
}

}

kmalloc · 2014-01-27T06:57:45Z

@JeffreyZhao

enum
{
   NotStart,
   Starting,
   Started,
   Disposing,
   Disposed
};

void Start()
{
   {
      // assume locker is recursive.
      Locker lock(status_guard);
      if (status != NotStart) return;

      status = Starting;
   }

   StartCore();

   {
       Locker lock(status_guard);
       int cur_status = status;
       status = Started;
       if (cur_status == Disposing) Dispose();
   }
}

void Dispose()
{
   {
       Locker lock(status_guard);
       if (status == NotStart || status == Disposing || status == Disposed)
       {
          return;
       }
       else if (status == Starting)
       {
          status = Disposing;
          return;         
       }

       status = Disposing;
   }

   DisposeCore();

   {
      Locker lock(status_guard);
      status = Disposed;
   }
}

denglinghua · 2014-01-27T07:00:08Z

// hope this one is fine.
// written by sucks java.

public class FineLockCalculator extends CalculatorBase {

private final Object gate = new Object();
private volatile int status = NotStarted;

@Override
public void Start() {
    synchronized (gate) {
        if (status != NotStarted) {
            return;
        }
        status = Starting;
    }

    if (this.status == Starting) {
        this.StartCore();
        this.status = Started;
    }
}

@Override
public void Dispose() {
    synchronized (gate) {
        if (status != Started) {
            return;
        }
        status = Disposing;
    }

    if (status == Disposing) {
        this.DisposeCore();
        status = Disposed;
    }
}

}

Yunanw · 2014-01-27T07:06:36Z

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace ClassLibrary1
{

public abstract class CalculatorBase : IDisposable
{
    protected void StartCore()
    {

    }

    protected void DisposeCore()
    {

    }


    public abstract void Dispose();

    public abstract void Start();

}



public class RWLockCalculator : CalculatorBase
{
    private ReaderWriterLock RWLock = new ReaderWriterLock();
    private const int TIMEOUT = 5000;

    private enum Status
    {
        NotStarted,
        Started,
        Disposed
    }

    private Status _status = Status.NotStarted;

    public override void Start()
    {
        try
        {
            RWLock.AcquireReaderLock(TIMEOUT);
            if (_status == Status.NotStarted)
            {
                LockCookie lc = RWLock.UpgradeToWriterLock(TIMEOUT);
                try
                {
                    if (_status == Status.NotStarted)
                    {
                        StartCore();
                        _status = Status.Started;
                    }
                }
                finally
                {
                    RWLock.DowngradeFromWriterLock(ref lc);
                }
            }
        }
        finally
        {
            RWLock.ReleaseReaderLock();
        }
    }

    public override void Dispose()
    {
        try
        {
            RWLock.AcquireReaderLock(TIMEOUT);
            if (_status == Status.Started)
            {
                LockCookie lc = RWLock.UpgradeToWriterLock(TIMEOUT);
                try
                {
                    if (_status == Status.Started)
                    {
                        DisposeCore();
                    }

                    _status = Status.Disposed;
                }
                finally
                {
                    RWLock.DowngradeFromWriterLock(ref lc);
                }
            }


        }
        finally
        {
            RWLock.ReleaseReaderLock();
        }
    }

}

}

grapef · 2014-01-27T07:15:01Z

public class Calculator : CalculatorBase
{
private enum StatusTypes
{
Bare,
Started,
Disposed
}

    private int statusInitialized = 0;
    private object statusLock = new object();
    private StatusTypes Status = StatusTypes.Bare;

    private void GetIntoStatus(StatusTypes targetStatus)
    {
        // The CompareExchange splits the call to two pathes:
        // Issue the first Start call.
        // Or wait for the result and issue the Dispose call if necessary.

        int originalValue = Interlocked.CompareExchange(ref this.statusInitialized, 1, 0);
        if (originalValue == 0)
        {
            // I am the first call. It must be started request and the current status must be bare.
            // Maybe we should throw if the targetStatus is Disposed. 
            System.Diagnostics.Debug.Assert(this.Status == StatusTypes.Bare);
            System.Diagnostics.Debug.Assert(targetStatus == StatusTypes.Started);

            lock (this.statusLock)
            {
                this.statusInitialized = 2;
                base.StartCore();
                this.Status = StatusTypes.Started;
            }
        }
        else
        {
            // The status will be stablized to either disposed or started eventually. Let's wait on the lock.
            // Before the wait, we need to check statusInitialized to let the starter thread to get the lock first.
            while (this.statusInitialized != 2) ; // 这这样比较会不会有问题得翻书确认下。
            lock (this.statusLock)
            {
                if (this.Status != StatusTypes.Disposed)
                {
                    if (targetStatus == StatusTypes.Disposed)
                    {
                        base.DisposeCore();
                        this.Status = StatusTypes.Disposed;
                    }
                }
            }
        }
    }

    public override void Start()
    {
        this.GetIntoStatus(StatusTypes.Started);
    }

    public override void Dispose()
    {
        this.GetIntoStatus(StatusTypes.Disposed);
    }
}

ghost · 2014-01-27T07:47:38Z

@JeffreyZhao

public class BigLockCalculator : CalculatorBase {

private readonly object _gate = new object();
private readonly object _gate2 = new object();

private enum Status4Start {
    NotStarted,
    Staring,
    Started
}
private enum Status4Dispose {
    NotDisposed,
    Disposing,
    Disposed
}

private Status _status4start = Status4Start.NotStarted;
private Status _status4dispose = Status4Dispose.NotDisposed;

public override void Start() {
    lock (_gate) {
        if (_status4start == Status4Start.Staring || 
            _status4start == Status4Start.Started || 
            _status4dispose == Status4Dispose.Disposed) {
            return ;
        }
        else {
            _status4start = Status4Start.Staring;
        }
    }

    lock (_gate2) {
        StartCore();
    }

    lock (_gate) {
        _status4start = Started;
    }
}

public override void Dispose() {
    lock (_gate) {
        if (_status4start == Status4Start.NotStarted) {
            _status4dispose = Status4Dispose.Disposed;
            return ;
        }

        if (_status4dispose == Status4Dispose.Disposing || 
            _status4dispose == Status4Dispose.Disposed) {
            return ;
        }

        if (_status4start == Status4Start.Staring) {
            _status4dispose = Status4Dispose.Disposing;
        }
    }

    lock (_gate2) {
        DisposeCore();
    }

    lock (_gate) {
        _status4dispose = Status4Dispose.Disposed;
    }
}

}

grapef · 2014-01-27T07:57:52Z

public class Calculator : CalculatorBase
{
    private bool isStartedCalling = false;
    private bool isStartedCalled = false;
    private bool isDisposeCalled = false;
    private object lockObject = new object();

    public override void Start()
    {
        bool callStart = false;
        lock (this.lockObject)
        {
            if (!isStartedCalling && !isDisposeCalled && !isStartedCalling)
            {
                isStartedCalling = true;
                callStart = true;
            }
        }

        if (callStart)
        {
            base.StartCore();
            this.isStartedCalled = true;
        }
    }

    public override void Dispose()
    {
        bool callDispose = false;
        lock (this.lockObject)
        {
            if (!isDisposeCalled)
            {
                isDisposeCalled = true;
            }
            else
            {
                callDispose = true;
            }
        }

        if (callDispose)
        {
            base.DisposeCore();
        }
    }
}

grapef · 2014-01-27T08:18:06Z

public class Calculator : CalculatorBase
{
    private bool isStartedCalling = false;
    private bool isStartedCalled = false;
    private bool isDisposeCalled = false;
    private object lockObject = new object();

    public override void Start()
    {
        bool callStart = false;
        bool callDispose = false;
        lock (this.lockObject)
        {
            if (!isStartedCalling && !isDisposeCalled && !isStartedCalling)
            {
                isStartedCalling = true;
                callStart = true;
            }
        }

        if (callStart)
        {
            base.StartCore();
            lock (this.lockObject)
            {
                if (isDisposeCalled)
                {
                    callDispose = true;
                }

                this.isStartedCalled = true;
            }
        }

        if (callDispose)
        {
            base.DisposeCore();
        }
    }

    public override void Dispose()
    {
        bool callDispose = false;
        lock (this.lockObject)
        {
            if (!isDisposeCalled)
            {
                isDisposeCalled = true;
                if (isStartedCalled)
                {
                    callDispose = true;
                }
            }
        }

        if (callDispose)
        {
            base.DisposeCore();
        }
    }
}

7没看懂

JeffreyZhao · 2014-01-27T08:32:17Z

@grapef: 7的意思是说，假如多个线程同时调用Start，则其中一个开始StartCore，其他立即返回就行。

wangjild · 2014-01-27T09:46:19Z

@JeffreyZhao 轻拍~

#include <atomic>

using namespace std;

public class Calculator : CaculatorBase {

  public :

    explicit Calculator() : status_(NOTSTART) {
    }

    ~Caculator() {
      Dispose();
    }

    override void StartCore() {
      // start code

      status_.store(STARTED, memory_order_release);
      return ;
    }

    override void DisposeCore() {
      // 试图满足条件3， 顺序执行 StartCore -> DisposeCore
      while (status_.compare_exchange_weak(STARTED, DISPOSED, memory_order_consume) == false) {
        usleep(10);
      }

      // dispose code
      return ;
    }

    override void Start() {
      if (status_.compare_exchange_strong(NOTSTART, STARTING, memory_order_consume)) {
        StartCore();
      }
    }

    override void Dispose() {
      // 试图满足 
      // 条件1，只调用一次
      // 条件5，一旦调用StartCore则必须调用DisposeCore
      if (status_.compare_exchange_strong(STARTING, DISPOSING, memory_order_consume)
        || status_.compare_exchange_strong(STARTED, DISPOSING, memory_order_consume)) {
        DisposeCore();
      }
    }

    void caculate(...) {
      // 试图满足 条件6, 未完成初始化和已销毁的对象，不做任何操作
      if (STARTED != status_) {
        return ;
      }

      // ... handle
    }

  private :
    atomic<int> status_;
    int NOTSTART = 0, STARTING = 1, STARTED = 2, DISPOSING = 3, DISPOSED = 4;
};

ivenxu · 2014-01-27T13:59:53Z

public class SimpleCalculator : CalculatorBase {

    private static readonly AutoResetEvent _event = new AutoResetEvent(true);

    private enum StatusEnum {
        NotStarted,
        Started, // 按照题意，该项应该命名为Completed或Done更直观
        Disposed
    }

    private StatusEnum Status {
        get {
            return (StatusEnum)Interlocked.CompareExchange(ref _status, 0, 0);
        }
        set {
            Interlocked.Exchange(ref _status, (int)value);
        }
    }

    private int _status = (int)StatusEnum.NotStarted;

    public override void Start() {
        // 这里和BigLockCalculator行为有所不同：BigLockCaculator里面只要有一个线程获得了lock，其它Start也得等，
        // 也就是哪怕StartCore没有完成并设置状态为Started, 也不允许其他线程进入，这似乎违背了并非执行Start的设计初衷
        // 我对题目的理解是：允许所有线程开始StartCore只要没有任何一个返回并把状态改为Started
        if (this.Status == StatusEnum.NotStarted) {
            _event.Reset();
            StartCore();
            this.Status = StatusEnum.Started;
            _event.Set();
        }
    }

    public override void Dispose() {
        _event.WaitOne();
        if (this.Status == StatusEnum.Started) {
            DisposeCore();
        }
        this.Status = StatusEnum.Disposed;
    }
}

haohaolee · 2014-01-28T02:56:58Z

试着用队列写一个，并发性肯定没有CAS的好，但是单线程的状态机似乎好维护些

public class QueueCalculator : CalculatorBase
{
    private enum Status
    {
        NotStarted,
        Starting,
        StartingButNeedsDisposal,
        Started,
        Disposing,
        Disposed
    }

    private enum Operation
    {
        ToStart,
        ToFinishStart,
        ToDispose,
        ToFinishDispose
    }

    private Status _status = Status.NotStarted;

    private BlockingCollection<Operation> _bc = new BlockingCollection<Operation>();

    public void RunQueue()
    {
        while (true)
        {
            Operation op = _bc.Take();
            switch (op)
            {
                case Operation.ToStart:
                {
                    if (_status == Status.NotStarted)
                    {
                        _status = Status.Starting;
                        Task.Run(() =>
                        {
                            StartCore();
                            _bc.Add(Operation.ToFinishStart);
                        });
                    }
                    break;
                }
                case Operation.ToDispose:
                {
                    if (_status == Status.Started)
                    {
                        _status = Status.Disposing;
                        Task.Run(() =>
                        {
                            DisposeCore();
                            _bc.Add(Operation.ToFinishDispose);
                        });
                    }
                    else if (_status == Status.Starting)
                    {
                        //_bc.Add(Operation.ToDispose);
                        _status = Status.StartingButNeedsDisposal;
                    }

                    break;
                }
                case Operation.ToFinishStart:
                {
                    if (_status == Status.StartingButNeedsDisposal)
                    {
                        _status = Status.Started;
                        _bc.Add(Operation.ToDispose);
                    }
                    else
                    {
                        _status = Status.Started;
                    }
                    break;
                }
                case Operation.ToFinishDispose:
                {
                    _status = Status.Disposed;
                    break;
                }

            }
        }
    }

    public override void Start()
    {
        _bc.Add(Operation.ToStart);
    }

    public override void Dispose()
    {
        _bc.Add(Operation.ToDispose);
    }
}

	///////////////////////////////////////////////////////
	// Talk is cheap. Show me the code. - Linus Torvalds
	///////////////////////////////////////////////////////

	public abstract class CalculatorBase : IDisposable {

	protected void StartCore() {
	// ...
	}

	protected void DisposeCore() {
	// ...
	}

	public abstract void Start();

	public abstract void Dispose();
	}

	// 需求：编写一个计算器，继承上面的CalculatorBase类，并实现Start和Dispose方法。
	// Start用于启动该计算器，Dispose则用于销毁，而启动和销毁的具体实现已经由基类
	// 的StartCore与DisposeCore提供，直接调用即可，确保成功，不会抛出一场。不过问
	// 题在于，Start和Dispose方法可能会被并发地执行，顺序不定，次数不定，但它们的
	// 实现必须满足：

	// 1. StartCore和DisposeCore都是相对较为耗时的操作，且最多只能被调用一次。
	// 2. StartCore和DisposeCore一旦开始执行，则无法终止，只能执行成功。
	// 3. StartCore和DisposeCore必须顺序地执行，不可有任何并行。
	// 5. 假如调用Dispose时StartCore已经执行，则必须调用DisposeCore，否则不用。
	// 6. 调用Dispose意味着要销毁对象，对象销毁以后的任何访问，都不会执行任何操作。
	// 7. Start及Dispose方法可立即返回，不必等待StartCore或DisposeCore完成。不过，
	// 8. 计算器本身不发起任何多线程或异步操作，一切都在Start和Dispose方法里完成。

	// 参考实现：一个最简单的实现方法便是用锁来保护Start和Dispose方法：

	public class BigLockCalculator : CalculatorBase {

	private readonly object _gate = new object();

	private enum Status {
	NotStarted,
	Started,
	Disposed
	}

	private Status _status = Status.NotStarted;

	public override void Start() {
	lock (_gate) {
	if (_status == Status.NotStarted) {
	StartCore();
	_status = Status.Started;
	}
	}
	}

	public override void Dispose() {
	lock (_gate) {
	if (_status == Status.Started) {
	DisposeCore();
	}
	_status = Status.Disposed;
	}
	}
	}

	// 不过这种方法的坏处也是显而易见的，假设有许多线程同时调用Start和Dispose方法，
	// 而某个Start线程稍早，则所有人都必须等待其调用完毕才能进行下一步判断。同理，假如
	// Start后进入的是个Dispose线程，则又要进行再一轮等待。

	// 那么，怎样可以做地更好呢？

	///////////////////////////////////////////////////////
	// Talk is cheap. Show me the code. - Linus Torvalds
	///////////////////////////////////////////////////////

	// 解答再此，但建议不要直接看答案，先自己想明白了再说，否则就失去意义了。
	// https://gist.github.com/JeffreyZhao/8644613

JeffreyZhao/gist:8630308

JeffreyZhao commented Jan 27, 2014

Lautitia commented Jan 27, 2014

dawnbreaks commented Jan 27, 2014

JeffreyZhao commented Jan 27, 2014

airekans commented Jan 27, 2014

dawnbreaks commented Jan 27, 2014

dawnbreaks commented Jan 27, 2014

fengyj commented Jan 27, 2014

maximesong commented Jan 27, 2014

kmalloc commented Jan 27, 2014

denglinghua commented Jan 27, 2014

Yunanw commented Jan 27, 2014

grapef commented Jan 27, 2014

ghost commented Jan 27, 2014

grapef commented Jan 27, 2014

grapef commented Jan 27, 2014

JeffreyZhao commented Jan 27, 2014

wangjild commented Jan 27, 2014

ivenxu commented Jan 27, 2014

haohaolee commented Jan 28, 2014