Last active
March 11, 2017 08:49
-
-
Save JeffreyZhao/8630308 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /////////////////////////////////////////////////////// | |
| // 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 不知道这次有没有理解错题意
public abstract class CalculatorBase : IDisposable{
private readonly object statusLock = new Object();
//
private enum Status
{
Idle,
Running,
WaitingClear,
End
};
private Status status = Status.Idle;
//
private readonly object runningSemphore = new Object();
private bool isAutoClear = false;
public override void Start()
{
//
lock(statusLock){
if( status == Status.Idle ){
status = Status.Running;
LOCK(runningSemphore); //pseudocode
}
else{
return;
}
}
StartCore();
if( isAutoClear ){
DisposeCore();
isAutoClear = false;
status = Status.End;
}
UNLOCK(runningSemphore); //pseudocode
}
public override void Dispose()
{
//
lock(statusLock){
if( status == Status.Running){
status == Status.WaitingClear;
}
else if( status == Status.Idle){
isAutoClear = true;
}
else{
return;
}
}
//waiting for runningSemphore UNLOCK
WAITING(runningSemphore); //pseudocode
if( status != Status.End){
DisposeCore();
status == Status.End;
}
}
}
@yhliaoluan: 虽然有点乱，粗看逻辑是对的，_status没保护好，各种竞争，但居然好像也没问题。现在的问题就变成了Dispose要等StartCore完成，等得时间略长。有办法不等吗？
@dawnbreaks: 知道你的意图，但你看我说的是你错在什么地方，再仔细看看代码，看不出来就想想最简单的情况，就一个线程，先调用Dispose，再调用Start，那么会出现什么情况。
public class BigLockCalculator : CalculatorBase {
private readonly object _gate = new object();
private readonly object _work = new object();
private enum Status {
NotStarted,
Starting,
Started,
Disposed
}
private Status _status = Status.NotStarted;
public override void Start() {
if (_status != Status.NotStarted)
return;
bool do = false;
lock (_gate) {
if (_status == Status.NotStarted) {
_status = Status.Starting;
do = true;
}
}
if (do){
lock (_work) {
StartCore();
_status = Status.Started;
}
}
}
public override void Dispose() {
if (_status != Status.Started)
return;
bool do = false;
lock (_gate) {
if (_status == Status.Started) {
_status = Status.Disposed;
do = true;
}
}
if (do){
lock (_work) {
DisposeCore();
}
}
}
}
各位同学，不看了啊，看不过来了，各种错误好浪费时间啊，啊哈哈。
@Lautitia 尤其不看你的，你每次贴的代码都乱其八糟，每次都让我来修，这次我不修了，也不看了。
@JeffreyZhao 表示无辜，Preview看上去都是好的
- 调用Dispose意味着要销毁对象，对象销毁以后的任何访问，都不会执行任何操作。
按照我的理解写了一下。
不过我的版本的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;
}
}
}
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这么改就可以了。汗，还有这一条。
@JeffreyZhao 现在对了吧，没注意到（6）这一条。
这样应该对了吧...只有在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();
}
}
}
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;
}
}
}
}
}
}
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;
}
}
// 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;
}
}
}
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();
}
}
}
}
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);
}
}
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;
}
}
}
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();
}
}
}
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没看懂
@grapef: 7的意思是说，假如多个线程同时调用Start，则其中一个开始StartCore，其他立即返回就行。
@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;
};
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;
}
}
试着用队列写一个，并发性肯定没有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);
}
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@JeffreyZhao 我不同意哦，因为这是在锁保护的区域内的操作，不可能拿到了锁，居然发现计数器处于starting的状态。因为题目说了，startCore执行不会失败，只能成功。如果计数器处于starting的状态，说明锁被别的调用start线程拿走了。
其实思路主要是3点