Recently I came across another interesting synchronization problem. Assume there are n rooms. Threads can enter and leave rooms. A room can hold arbitrary number of threads. If a room holds at least one thread it is considered occupied. Only one room can be occupied at a time. With each room exit action is associated that must be executed when the last thread left it. No threads are allowed to enter any room before exit action is executed to the end. Threads that are waiting to enter a room must eventually enter it. It is assumed that threads also at some point leave the room.
There are several cases for a thread attempting to enter a room:
Leaving room requires careful thought as well:
Waiting and waking part can be done using Monitor.Wait and Monitor.PulseAll. Doing so using single sync object is simple but quite inefficient as every pulse all will wakeup all waiting threads (potentially waiting for different rooms) to see that they are not allowed to enter yet as only single room can be occupied at a time. Instead each room will have its own local sync object to wait and pulse on. This will allow to wake up only threads that are now allowed to enter the room they've been waiting on.
But this is where difficulties come. The decision to be made by entering thread spans across rooms. So the decision is still needs to made using global lock. Now the tricky part is that once the decision is made to wait how not to miss wakeup. Attempting to do it like
lock (global) { // Make decision to wait or return bool wait = ...; if (!wait) return; } // Somewhere here wakeup may be missed lock (local) { // Wait on local based on the decision made above Monitor.Wait(local); }
is doomed to suffer from missed wakeups as in between global lock is released and local is acquired the last leaving room thread may try to wakeup waiters. So instead local lock will be acquired while still holding global lock and releasing it only after that.
var locked = false; try { Monitor.Enter(global, ref locked); // Make decision to wait or return bool wait = ...; if (!wait) return; // Acquifre local hiwle holding global lock (local) { // Release global Monitor.Exit(global); locked = false; // Wait on local based on the decision made above Monitor.Wait(local); } } finally { if (locked) Monitor.Exit(global); }
Threads indicate that are willing to enter the room by maintaining wait count for each room. It also used to allow threads enter the room in bulk. When the last leaving thread picks up a room to get occupied next, adjusts the count and wakes up waiting threads by pulsing room local sync object.
In order to make sure that waiting threads enter a room eventually (guaranteeing starvation freedom) the following mechanism is used:
Here goes the thing.
public class SharedRoomsLock { // Holds room local locks private readonly object[] m_locks; // Holds number of threads waiting on to // enter indexed by room numbers private readonly int[] m_waiting; // Holds actions to be excuted for each room // upon exit private readonly Action[] m_actions; // Holds number of threads currently in the // occupied room private int m_count; // Holds index of the room currently occupied private int m_occupied = -1; public SharedRoomsLock(IEnumerable<Action> actions) { m_actions = actions.ToArray(); var count = m_actions.Length; m_waiting = new int[count]; m_locks = Enumerable.Range(0, count) .Select(_ => new object()).ToArray(); } // Lock ownership is omitted for clarity however // can be added using ThreadLocal<T> public void Enter(int i) { var locked = false; try { Monitor.Enter(m_locks, ref locked); if ( // If no room is occupied or m_occupied < 0 || ( // Occupied room that thread is trying // to enter m_occupied == i && // and there is still someone in there m_count > 0 && // and no one waiting to enter other rooms !m_waiting.Any(w => w > 0))) { m_occupied = i; m_count++; return; } // Otherwise indicate desire to enter the room m_waiting[i]++; // Acquire room local lock before releasing main // to avoid missed or incorrect wakeups lock (m_locks[i]) { // Release main lock to allow others to // proceed including waking thread Monitor.Exit(m_locks); locked = false; // Wait to be woken up by some last to leave // room thread, not necessarily immediately Monitor.Wait(m_locks[i]); // Once woken up thread can safely enter // the room as count already adjusted } } finally { if (locked) Monitor.Exit(m_locks); } } public void Exit(int i) { lock (m_locks) { // Indicate that thread left the room if (--m_count > 0) // And leave it if not last return; } // If last execute exit action however not under // the lock as it quite dangerous due to reentracy m_actions[i](); // At this point room is still treated as // occupied as only once exit action is executed // it can be set free var locked = false; try { Monitor.Enter(m_locks, ref locked); // By default set room as not occupied m_occupied = -1; // Run through other rooms in circles to see if any // thread is waiting thus ensuring some sort of // fairness or at least starvation freedom for (var j = 1; j <= m_waiting.Length; j++) { var next = (i + j) % m_waiting.Length; var w = m_waiting[next]; if (w > 0) { // Found room with waiting threads so it // will be occupied next m_occupied = next; break; } } // If no one is waiting if (m_occupied < 0) // There is nothing that can done return; // At this there are threads waiting to enter // the room so they are allowed to enter in one // shot m_count = m_waiting[m_occupied]; // Closing the doors right after them m_waiting[m_occupied] = 0; // Acquire room local lock before releasing main // to avoid missed or incorrect wakeups lock (m_locks[m_occupied]) { // Releasing main lock is safe because the // decision made under main lock will still be // true as no other thread except for those // already wating will be able to wait on room // local lock that is currently held Monitor.Exit(m_locks); locked = false; // Wake up waiting to enter threads Monitor.PulseAll(m_locks[m_occupied]); } } finally { if (locked) Monitor.Exit(m_locks); } } }
Single Responsibility Principle states:
A class should have only one reason to change. Responsibilities are reasons to change.
Violations of this principle leave you face to face with fragile design and all the maintenance nightmares it implies. Unfortunately there is no hundred percent way to prevent it from happening – it is just the nature of design.
Common sense often helps to spot multiple responsibilities mixed within a single class. However some cases are tricky and require careful attention. This is where design assessment comes in. An object can be looked at from two perspectives:
Uncontrolled growth in any of the groups can lead to god class (data or behavior forms respectively).
What it knows?
Keeping related data and behavior in one place is essential to building consistent abstractions. Failing to do so may lead to:
Following Information Expert pattern promotes the idea:
Assign a responsibility to the class that has the information needed to fulfill it.
Consider an example below where publicly visible person name could be incorrectly used to distinguish people (as names are not unique). Thus it makes sense to let Person type to define what equality means as it has all the necessary information (social security number). This will prevent introduction of several inconsistent equality behaviors across the code base.
class Person { private string name; // Keep social security number in private private string ssn; // Names are not unique public string Name { get { return name; } } public override bool Equals(object obj) { if (obj == null || obj.GetType() != typeof(Person)) return false; // Names cannot be used to identify people unlike // social security number return ssn == ((Person) obj).ssn; } }
Keeping related data and behavior in one place is as important as not letting not related sets of data/behavior to be put into the same class. Most of the methods defined on a class should be using most of the data members most of the time.
Many of you started to work still being a student. Employer needs your abilities to work and most likely he isn’t interested in that you still studying.
// Smart student - works and studies class Student { private string name; private int knowledge; private Func<Course, bool> preferences; private int experience; public string Name { get { return name;} } public void Study() { knowledge++; } public void Enlist(IEnumerable<Course> courses) { // Select appropriate courses and enlist foreach (var course in courses.Where(preferences)) course.Enlist(name); } public void Work() { experience++; } public void Sign(Contract contract) { // sign job contract with your name contract.Agree(name); } }
This class clearly has more than one responsibility and the fact that study related methods and work related methods both operate on a subset of data shows that. However separation can solve the problem.
class Student { private Person person; private int knowledge; private Func<Course, bool> preferences; public Student(Person newStudent) { person = newStudent; } public void Study() { knowledge++; } public void Enlist(IEnumerable<Course> courses) { // Select appropriate courses and enlist foreach(var course in courses.Where(preferences)) course.Enlist(person.Name); } } class Employee { private Person person; private int experience; public Employee(Person newEmployee) { person = newEmployee; } public void Work() { experience++; } public void Sign(Contract contract) { // sign job contract with person's name contract.Agree(person.Name); } }
What connections between objects it maintains?
What is connection between objects anyway? For example, a document can be seen a set of glyphs (text, graphics, structural elements like columns and rows). The connection between them is the fact they belong to the same document. So basically the document maintains connection between glyphs. So what must attract our attention in this area to spot Single Responsibility Principle violations?
If the object maintains connections between objects of different abstraction levels it is highly likely that it does someone’s job.
Consider an object model where a man wants to build a house. Man class maintains connection between tasks (got from an architect) and workers to build a house. And this where different abstraction levels (from domain model perspective) meet – a man hired foreman who is supposed to manage construction but it so happens that a man wants to control everything and treats hired foreman as a simple worker giving him tasks to do in not necessarily correct order. Basically a man got foreman’s responsibility (or in other words foreman abstraction isn't consistent).
abstract class Task { public bool Completed { get; private set; } public virtual void Do() { DoCore(); Completed = true; } protected abstract void DoCore(); } class Worker { public virtual bool CanDo(Task task) { // Can do everything worker =) return true; } public virtual void Accept(Task task) { task.Do(); } } class Foreman : Worker { IEnumerable<Worker> workers; Func<Task, bool> next; public override bool CanDo(Task task) { // Can do things only on time or otherwise the house // won't stand long return next(task); } public override void Accept(Task task) { // Foremen looks for a worker who can do the task workers.Where(w => w.CanDo(task)).First().Accept(task); } } // A man who tries to manage his new house construction class Man { IEnumerable<Task> construction; Foreman foremen; public void BuildHouse() { IEnumerable<Task> tasks; // As far as we don't know what to do next we'll ask foreman while ((tasks = construction.Where(t => foremen.CanDo(t) && !t.Completed)).Any()) { foreach (var task in tasks) { foremen.Accept(task); } } } }
A man must let foreman to manage tasks or become a foreman himself (we’ll take first approach or otherwise the house won't stand long).
class Foreman { IEnumerable<Worker> workers; Func<Task, bool> next; public void Manage(IEnumerable<Task> construction) { IEnumerable<Task> tasks; // Foreman selects tasks that are not completed and must be done next while((tasks = construction.Where(t => !t.Completed && next(t))).Any()) { foreach (var task in tasks) { workers.Where(w => w.CanDo(task)).First().Accept(task); } } } } class Man { IEnumerable<Task> construction; Foreman foremen; public void BuildHouse() { // Foreman takes the whole construction to manage foremen.Manage(construction); // Just check that everything is done if (construction.Where(t => !t.Completed).Any()) { throw new InvalidOperationException("Something isn't done!"); } } }
Now abstractions are leveled - man allows construction to be managed by foreman (foreman abstraction is now consistent).
What it decides?
It is quite uncomfortable when someone asks you for your opinion and then makes his own mind and tells you what and how to do. Why don’t tell what to do in the first place and let me decide how to do it. Isn’t that looking like you are doing my job? This is what Tell Don’t Ask Principle is about:
As the caller, you should not make decisions based on the called object’s state and then change the object’s state.
Here is couple of teenager definitions – which do you think makes more sense?
class Teenager { private int age; private List<string> clothes; // Is it age that drives your clothes preferences? public int Age { get { return age; } } // Do you really wan't your parents to dress you // just based on your age? public void TakeNew(string clothing) { clothes.Add(clothing); } } // ... or class Teenager { private List<string> clothes; // Preference is something personal private Func<string, bool> preference; // And you want to able to select clothes based on your // preferences? public bool SelectNew(IEnumerable<string> shop) { var clothing = shop.Where(preference).FirstOrDefault(); if (clothing != null) { // Got something you like clothes.Add(clothing); } // Tell your parents whether you need to go to other shop =) return clothing != null; } }
By violating Tell Don’t Ask principle caller gains responsibility on make decision instead of the called one. Busted!
What services it performs?
Service provider can do the job by itself or ask collaborators for help. Keeping dependencies on collaborators explicit facilitate controlled class growth. Classes should not contain more objects than a developer can fit in his or her short-term memory (5-7). Otherwise it is possible to introduce responsibilities into class which are either duplicated or not related. Whenever number of collaborators growth more than 5-7 you should consider whether all collaborators still help you to form single abstraction or a new one was introduced.
On the other hand it makes sense to look at consumers and in particular on how they consume supplied services. If consumers use different subsets of provided services it may be a sign that class captures more than one responsibility.
Recall the student example. Original class has two consumers: employer and university (for example). Both consumers were interested in a subset of provided methods (working and studying related respectively). And as we discovered the class captured two abstractions: employee and student.
Summary:
Inversion of Control pattern allows to decouple components (consumers) from their dependencies and takes care of dependencies location and lifetime management through delegation of these responsibilities to external (with respect to dependent type) component. This pattern actively used in composite application development.
Inversion of Control comes in two flavors (Unity provides both capabilities):
Service locator holds references to services and knows how to locate them. It is further used by dependent component to obtain necessary services. In other words consumers play active role.
interface IService { void Do(); } class ActiveConsumer { private readonly IUnityContainer m_locator; // Reference to service locator comes from outside public ActiveConsumer(IUnityContainer serviceLocator) { m_locator = serviceLocator; } public void Do() { // In order to fulfill its task active consumer relies // on service implementation that is obtained on demand // from service locator var service = m_locator.Resolve<IService>(); service.Do(); } }
Dependency injection makes dependent components passive (little or no work is done to get its dependencies). The only responsibility consumers still care about is to express their dependencies somehow (the way dependencies are expressed depends on pattern implementation, but for this example we will use single constructor automatic injection supported by Unity).
class PassiveConsumer { private readonly IService m_service; // This constructor is used to inject service dependency public PassiveConsumer(IService svc) { m_service = svc; } public void Do() { // We got this dependency from outside and done nothing // to let it happen - so just use it m_service.Do(); } } ... // At this point container resolves consumer's dependency // and injects it during construction var passiveConsumer = container.Resolve<PassiveConsumer>(); passiveConsumer.Do();
So what is the difference?
First, is dependency from service locator appropriate? If the component in question is supposed to be reused by others you may end up with putting unnecessary constraints (for example you are using some open source service locator but developers that could reuse your component are not allowed to use any open source stuff due to customer’s demand and thus won’t be able to reuse the component).
Second, dependencies visibility. Service locator makes consumer’s “real” dependencies hidden and dependency from service locator itself visible. When dependencies are explicit it is much easier to understand dependent class. Explicit dependencies allows you to assess and control the growth of the component. For example, if your component accepts 10 services in its constructor it may be a sign that it does, or knows or decides too much and it is time to split it. Consider the same thing when using service locator. In order for you to spot number of dependencies you need to look for all unique usage occurrences of service locator. It is not that hard with modern IDE but still it is not that easy as looking at component’s contract.
On the other hand, it makes sense to consider the audience of the component. If it will be reused by others and dependencies are hidden it may require deep knowledge of component’s inner workings in order to use it.
Third, consumer’s relation with dependency. Dependency injection promotes constant relations (from lifetime perspective). Consumer obtains its dependency at construction time and lives with it. On the other hand service locator compasses to temporary relations – get service instance when it is time, call its methods, discard it. Why discard? Because if the component has a constant relation why not use dependency injection otherwise which gives you explicit dependencies?
But anyway, what particular case forces locator usage? When consumer has longer lifetime than its dependency. For example, you are writing smart client application. You organized presentation layer using Model-View-Presenter pattern. Presenter calls remote service in response to user interaction. View controlled by a presenter can be opened for a long time. If presenter gets remote service proxy dependency only once it may happen that proxy will go into faulted state (for example, due to network connectivity problems) and any subsequent calls to it will result in exception. So it is better to dispose proxy every time a particular task accomplished and create new one when new task is on the way or cache it and in response to proxy going faulted create a new one (which is of course harder as long as you need to handle all cases where it used and maintain cache). Thus it seems that service locator is more appropriate in this case.
However we can make short lived dependencies explicit. Let’s assume that IService implementation instance must be disposed every time it is used.
interface IService : IDisposable { void Do(); } // This is still active consumer as it uses service locator to get service instance class ActiveConsumer { private readonly IUnityContainer m_locator; public ActiveConsumer(IUnityContainer serviceLocator) { m_locator = serviceLocator; } public void Do() { using (var service = m_locator.Resolve<IService>()) { service.Do(); } } }
Service locator has wide surface (it terms of services it can provide) and this makes consumer’s contract opaque. What we need to do is narrow the surface but still provide ability to create service instances (as long as we need to dispose them every time). Abstract factory will do the thing. Factory provides clear connection with service it creates. On the other hand we need to make consumer’s dependency from factory explicit. We will use dependency injection.
interface IServiceFactory { IService CreateService(); } // Consumer is no longer active as it gets its dependencies from outside class PassiveConsumer { private readonly IServiceFactory m_factory; // The dependency is now explicit public PassiveConsumer(IServiceFactory serviceFactory) { m_factory = serviceFactory; } public void Do() { // We still can create service instances on demand using (var service = m_factory.CreateService()) { service.Do(); } } }
How about this? That is not all. Factory clearly and explicitly states the relation between dependent component and dependency (service that is created by factory) – it is a temporary relation (as long as it provides ability to create new instances).
Sleeping barber problem is a classic synchronization problem proposed by Dijkstra that goes as follows:
A barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.
Back in the days when Dijkstra proposed this problem (it was in 1965) probably rhythm of life was hasteless and barbers had chance to sleep at work and customers could wait until he woke up.
Most of the solutions use some sort of WaitHandle to do the trick. For example, classic solution is based on semaphores. Waiting on wait handles is not free.
But now let’s assume that analogy for this problem a barber that desperately needs customers so he is running around in circles while waiting impatiently when there are no customers. Customers are also quite busy so if the waiting queue is empty they want to be served immediately otherwise they go from corner to corner while waiting.
I call this problem “crazy barber”. From the problem statement it follows that we should avoid using any “sleeping” mechanisms to do the synchronization.
Haircut we represent through an Action that barber must execute and thus it cannot be null.
Number of chairs in the waiting room is known in advance and never changes. Waiting queue can not overflow because any customer that sees no free chairs turns around and leaves barbershop. So we can represent waiting queue as circular array of fixed size. Two indices are used to represent it. Head points to next request to be serviced if not null. Tail points to next free slot where request can be put.
Barber waits next in line (the one head index points to) non null request to get serviced. To mark slot as free for itself it nullifies it once obtained reference to request. Next head index is advanced to make this slot available for use by customers. Once it completed with execution it notifies waiting customer that it is free to go by changing done flag.
Customer first checks if there are free slots. Then it competes with other customers for a free slot (the one tail index points to). If successful it puts request that combines action and done flag into waiting queue array with the index value of just advanced tail. Once successfully queued request customer waits until value in the done flag is not changed.
Here goes “crazy barber”.
class CrazyBarber { private readonly int m_capacity; // Circular array that holds queued items private volatile Request[] m_queue; // Points to next free slot private volatile int m_tail; // Points to a slot where next item to be executed // is expected private volatile int m_head; public CrazyBarber(int capacity) { m_capacity = capacity; m_queue = new Request[m_capacity]; } // Queues action for execution if there is free slot and // waits for its execution completion public bool TryGetExecuted(Action action) { if (action == null) throw new ArgumentException(); var waitToEnq = new SpinWait(); while (true) { // Load tail first as if it will change compare and // swap below will fail anyway var tail = m_tail; // Now load head and this is the linearization point // of full queue case which results in unsuccessful // attempt var head = m_head; // Check if queue has some free slots if (tail - head >= m_capacity) // The queue is full, no luck return false; // Create request before interlocked operation as // it implies full barrier and thus will prevent // partially initialized request to be visible to // worker loop var request = new Request { m_action = action }; // Compete for the tail slot if (Interlocked.CompareExchange(ref m_tail, tail + 1, tail) != tail) { // We lost due to contention, spin briefly and // retry waitToEnq.SpinOnce(); continue; } var index = tail % m_capacity; // Here is the linearization point of successfull // attempt m_queue[index] = request; var waitToExe = new SpinWait(); // Wait until enqueued action is not executed while (!request.m_done) waitToExe.SpinOnce(); return true; } } // Runs single worker loop that does the execution and // must not be called from multiple threads public void Run(CancellationToken cancellationToken) { var waitToDeq = new SpinWait(); while (true) { var head = m_head; var index = head % m_capacity; waitToDeq.Reset(); // Though array field is marked as volatile access // to its elements are not treated as volatile // however its enough to make sure loop condition // is not optimized // Wait until new item is available or cancellation // is requested while (m_queue[index] == null) { if (cancellationToken.IsCancellationRequested) return; waitToDeq.SpinOnce(); } // Get request to be serviced and nullify it to // mark slot as free for yourself var request = m_queue[index]; m_queue[index] = null; // As there is only one worker advance head without // interlocked and here is the linearization point // of making free slot m_head = head + 1; // Do not call TryGetExecuted from action or it will // deadlock request.m_action(); // Make sure ready notification is not made visible // through reordering before action is completed // and store release guarantees that here request.m_done = true; } } class Request { internal Action m_action; internal volatile bool m_done; } }
Although tail index at some point will overflow let’s assume “crazy” barber won’t try to make around 2 billion haircuts =).