Честность синхронизации потоков в .NET CLR


На главную


Автор статьи - Джеффри Рихтер (Jeffrey Richter)

(Статья на английском заимствована отсюда, перевод - Трубецкой А.)

Когда я впервые обнаружил, насколько незащищенной оставлена синхронизация потоков в библиотеке классов .NET Framework, я сразу заинтересовался методом TryEnter() из класса System.Threading.Monitor. Существует несколько перегруженных (overloaded) версий этого метода. Некоторые из версий принимают значение таймаута в качестве аргумента. Этот таймаут позволяет вызывающему метод коду задавать количество времени, в течение которого он готов ожидать возможности завладеть указанным объектом. Если вызывающий код получает владение объектом, то метод TryEnter() возвращает true, если таймаут заканчивается - метод возвращает false.

Возможно вас интересует, почему я беспокоился о методе TryEnter(). Дело в том, что в июле 1996 г. я писал колонку Win32 Q & A для журнала Microsoft Systems, где я привел мой собственный объект синхронизации, называемый Optex. Мой объект Optex предлагает функцию OPTEX_Enter(), которая позволяет вызывающему коду указать величину таймаута (подобно методу TryEnter()). Эту колонку журнала Microsoft Systems вы можете найти здесь. К сожалению после того как колонка была опубликована, я обнаружил, что в ней содержится баг. Проблема заключалась в том, что была возможность реализовать только такой объект синхронизации в режиме пользователя, который бы либо проверял возможность владения и возвращал результат сразу, либо ожидал бы бесконечное время. Причина заключается в том, что ожидание потока требует чтобы поток перешел в режим ядра. Поток не может проснуться в режиме ядра и автоматически установить переменную режима пользователя. Таким образом не исключено возникновение состояния гонок в тот момент, когда два потока одновременно ждут владения одним объектом. Состояние гонок будет возможно, поскольку один поток может думать, что другой поток владеет объектом, когда на самом деле это не так. Как только я обнаружил этот баг в моем объекте Optex, я сообщил об этом в сентябре 1996 г. в колонке журнала Microsoft Systems.

Итак, если невозможно решить проблему, то вы могли бы спросить, является ли корректным метод TryEnter() класса Monitor. В своей реализации метод TryEnter() не содержит багов. Суть его работы в том, что он спит, ожидая пока захваченный объект станет доступным. Когда поток, который владеет объектом, освобождает его, все ожидающие потоки просыпаются. Каждый из этих потоков пытается захватить освободившийся объект. Наконец один из потоков становится владельцем, а другие потоки снова засыпают. Когда поток засыпает, он вычитает время, в течение которого он уже спал, из таймаута, которое вызывающий код задал для метода TryEnter(). Таким образом вызывающему коду кажется, что поток спит столько времени, сколько ему было задано. Хотя метод TryEnter() не содержит багов, это не очень честно: возможно (и даже вполне вероятно), что несколько ожидающих потоков не будут обслуживаться в соответствии с правилом first-in-first-out.

Таким образом важно знать, что синхронизация потоков в классе Monitor не является честной [fair] и сделать ее честной невозможно. Это означает, что если у вас есть несколько потоков, которые постоянно пытаются завладеть объектом, используя класс Monitor, то возможно, что некоторые из этих потоков никогда не смогут захватить объект! Кроме того, это означает, что вы не должны использовать класс Monitor, если вы создаете приложение, моделирующее какую-либо ситуацию реального мира, в которой применяются очереди. Например, не следует моделировать супермаркет, где покупатели стоят в очереди и рассчитывают быть обслуженными по принципу first-come-first-serve, а вы хотите увидеть сколько покупателей будет обслужено за час. Если для этих целей вы используете класс Monitor, результат будет неверным, поскольку порядок очереди возможно будет нарушен.

Итак, обнаружив насколько нечестно [unfair] реализована синхронизация потоков в классе Monitor, я начал проектировать и реализовывать свою собственную корректную синхронизацию потоков для .NET Framework. Поиграв несколько часов с различными идеями, я в итоге не добился никакого результата. Все мои тесты показали, что все техники синхронизации, которые я пытался применить, также работали некорректно. В конце концов я понял, что невозможно создать честный механизм синхронизации потоков в управляемом коде. И вот почему...

CLR управляет памятью с помощью сборщика мусора. Когда CLR хочет запустить сборщик мусора, она определяет какие потоки в данный момент выполняют управляемый код, а какие потоки выполняют неуправляемый код. Определив это, CLR приостанавливает потоки, которые выполняют управляемый код. Потоки, выполяющие неуправляемый код, приостановятся сами, когда попытаются вернуться в управляемый код. Но возможна и следующая ситуация: поток выполняет управляемый код и соответственно CLR думает, что должна приостановить этот поток, а затем поток вызывает неуправляемую функцию WaitForSingleObject() или WaitForMultipleObjects() и пока он ожидает возвращения этой функции, CLR останавливает поток (который в этом момент выполняет неуправляемый код).

Когда Windows приостанавливает поток, прекращается ожидание потоком любых объектов синхронизации. Позже, когда выполнение потока возобновляется, все приостановленные потоки наперегонки возвращаются к ожиданию нужного им объекта синхронизации. Это означает, что потоки необязательно получают владение объектом по принципу first-in-first-out. Поскольку сборщик мусора может быть запущен в любой момент (и его запуск нельзя предотвратить), архитектура CLR не поддерживает честную синхронизацию потоков. Кроме того, все управляемые методы ожидания (такие как WaitOne(), WaitAll(), и WaitAny()) переводят вызывающий поток в сигнальное состояние, что позволяет насильно прекратить ожидание потоком объекта синхронизации и затем вернуть потоки в состояние ожидания в неправильном порядке.

Если вы создаете приложение, которое обязательно требует честной синхронизации потоков, вы вообще не должны использовать .NET Framework. Если потоки вашего приложения, требуют синхронного доступа к ресурсам только время от времени, тогда недостатки CLR скорее всего не будут проблемой для вашего приложения. В действительности большинство приложений прекрасно работает без честной синхронизации потоков, но по крайней мере вам следует знать об этой проблеме.



Оригинальный текст статьи:

Thread Synchronization Fairness in the .NET CLR

When I first started learning how thread synchronization was exposed in the .NET Framework's class library, I was immediately concerned about the System.Threading.Monitor class's TryEnter method. There are several overloaded versions of the TryEnter method, some of which accept a timeout argument. This timeout argument allows the caller to specify an amount of time that the caller is willing to wait to gain ownership of the specified object. If the caller gains ownership of the specified object, then TryEnter returns true; if the timeout expires, then TryEnter returns false.

You might be wondering why I was concerned about the TryEnter method. Well, in July of 1996, I wrote a Win32 Q & A column for Microsoft Systems Journal where I implemented my own synchronization object called an Optex. My Optex object offered an OPTEX_Enter function that allowed the called to specify a timeout value (just like Monitor's TryEnter method). This MSJ column can be found here. Unfortunately, after the column was published, I realized that it contained a bug. The problem was that it is only possible to implement a user -mode synchronization object that either tests for ownership and returns immediately or waits for ownership infinitely. The reason is because making a thread wait requires that the thread jump to kernel mode and there is no way for a thread to wake up from kernel mode and set a user-mode variable atomically. So a race condition is possible when two threads simultaneously wait on the same object. This race condition will allow a thread to think another thread owns the object when, in fact, it doesn't. Once I discovered this bug in my Optex code, I published the discovery in my September 1996 MSJ column.

So, if it's not possible to fix this problem, then you might ask if Monitor's TryEnter method is buggy or not. Well, as it turns out, Monitor's TryEnter is not buggy. Internally, TryEnter sleeps waiting for an owned object to become available. When the thread that owns the object releases it, all waiting threads are awakened. Each of the waiting threads loops around trying to gain ownership of the object again. One of the waiting threads will become the owner and the other threads will go back to sleep. When a thread goes back to sleep, it subtracts the amount of time that the thread has already slept from the amount of time the caller specified to the TryEnter method. So, to the caller, it looks like the thread is sleeping the correct amount of time. While TryEnter is not buggy, it is not fair: It's entirely possible (and quite likely) that multiple threads waiting to own an object will not be serviced in a first-in-first-out fashion.

So, the important thing for you to be aware of is that thread synchronization using the Monitor class is not fair in the .NET Framework and there is no way to make it fair. This means that if you have threads that are constantly trying to own an object using a Monitor, it is possible that some threads will never gain ownership! This also means that you should not use the Monitor if you are building an application that tries to simulate some kind of real-world situation that involves a queue. For example, you should not try to build a supermarket simulation where customers are standing in line at a cash register trying to be serviced on a first-come-first-serve basis and you want to see how many customers can be serviced per hour. If you use a Monitor for this, the simulation will be broken because it would allow customers to jump in front of other customers in the line.

So, after discovering how unfair synchronizing threads via the Monitor class was, I started designing and implementing my own, fair thread synchronization code for the .NET Framework. After several hours of playing around with different ideas, I was having no luck at all. All my tests showed that every synchronization technique I tried ended up producing another unfair mechanism. Then, finally, it dawned on me; it's not possible to have a fair thread synchronization mechanism in the managed world. Here's why...

The CLR manages memory via garbage collection. When the CLR wants to start a garbage collection, it will determine which threads are currently executing managed code and which threads are currently executing unmanaged code. After making this determination, the CLR will suspend the threads executing managed code. Threads that are currently executing unmanaged code will self-hijack themselves when they attempt to return back to managed code. There is a small window of time where a thread is currently in managed code, the CLR thinks it needs to suspend this thread, and then the thread calls into the unmanaged Win32 WaitForSingleObject or WaitForMultipleObjects functions and while in one of these functions, the CLR suspends the thread.

When Windows suspends a thread, it stops the thread from waiting for any thread synchronization object. Later, when the thread is resumed, all the suspended threads race back to wait on the object that it was waiting on before it got suspended. This means that threads are not guaranteed to gain ownership of an object on a first-in-first-out basis. Since a garbage collection can start at any time (and cannot be prevented), the architecture of the CLR just doesn't support fair thread synchronization — period. In addition, all managed wait methods (such as WaitHandle's WaitOne, WaitAll, and WaitAny methods) put the calling thread into an alertable state, which can also force a thread to stop waiting on an object and to re-queue its wait in a different order.

If you are building an application that absolutely requires fair thread synchronization, you should not use the .NET Framework at all. If your application's threads require synchronized access to resources only periodically, then the CLR's unfairness will most likely not be a problem for your application. In fact, most applications will run fine without fair thread synchronization but, at least, you should be aware of this issue.

На главную

Rambler's Top100
Хостинг от uCoz