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 |
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
public class BigLockCalculator : CalculatorBase {
}