Dining Philosophers in C++11

UPDATE: for an implementation of the Chandy/Misra solution see Dining philosophers in C++11: Chandy-Misra algorithm

The problem of the dining philosophers, first proposed by Edsger Dijkstra and reformulated by Tony Hoare, is a famous problem for concurrent programming that illustrates problems with synchronizing access to data. The description of the problem, taken from Wikipedia, is the following:

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

The idea is to find a solution so that none of the philosophers would starve, i.e. never have the chance to acquire the forks necessary for him to eat.

Below I propose a simple implementation to this problem using C++11 language and library features. The following classes are defined:

  • fork represents a fork at the table; the only member of this structure is a std::mutex that will be locked when the philosopher picks up the fork and unlocked when he puts it down.

  • table represents the round table where the philosophers are dining. It has an array of forks, but also an atomic boolean that indicates that the table is ready for the philosophers to start thinking and eating.

  • philosopher represents a philosopher dining at the table. It has a name and a reference to the forks on his left and right.

Most of the implementation of the solution is part of the philosopher class. When an object of this class is instantiated, a thread is started. This thread is joined when the object is destroyed. The thread runs a loop of thinking and eating until the dinner is signaled to end by setting the ready member of the table to false. There are three main methods in the philosopher class:

  • dine() is the thread function; this is implemented as a simple loop of thinking and eating.

  • think() is the method that represents the thinking period. To model this the thread sleeps for a random period of time.

  • eat() is the method that models the eating. The left and right forks are acquired in a deadlock free manner using std::lock. After the forks, i.e. mutexes, are acquired, their ownership is transfered to a std::lock_guard object, so that the mutexes are correctly released when the function returns. Eating is simulated with a sleep.

To see how this works, we create a table object and an array of phylosophers. Upon creating the philosopher objects their own working thread is started, but nothing happens until the table is signaled as being ready. Philosophers then compete for the forks (i.e. mutexes), eat and think until the dinner is signaled as finished by setting the ready flag of the table object back to false.

The whole implementation is show below:

The output for this program (that varies with each execution) has the following form:

Though the problem is usually described in terms of five philosophers, any number of philoposhers can be present at the table (of course, at least two are necessary for the problem to make sense). Adding more philosophers does not require any changes in the implementation.

, , , , , , Hits for this post: 8738 .

I recently encountered a problem creating new logins with SQL Server. Something that has worked for years suddenly stopped with the following error:

Password validation failed. The password does not meet Windows policy requirements because it is too short.

Since SQL Server was using Windows local security policy I went and checked that at Security Settings > Account Policies > Password Policy in Local Security Policy (available under Administrative Tools in Control Panel or by opening secpol.msc). As expected, these contained setting that I was not expecting, which were probably changed from the network by a system administrator.

However, I wanted to be able to enter shorter passwords, like 8 characters instead of 10, but this was disabled. Even if I was running as administrator, the option of changing this was disabled.

It is however still possible to modify these settings even if you cannot do it from the management console. You can do it from a command prompt as administrator.

  1. Open a command prompt running as administrator
  2. Run the following command to export the settings to a file. In my example, the target path is c:\temp\local.cfg, but it can be anything.

  3. Edit the file with notepad or another editor. The file is an INI file with sections and key-value pairs. The password settings are available under the [System Access] section. For changing the minimum length of the passwords modify the MinimumPasswordLength key.
  4. Save the file and run the following command to import the settings from the modified file.

  5. Close and open the Local Security Policy console again and check the settings.
, , , , Hits for this post: 6691 .

The new Visual C++ 2017, currently in release candidate phase, provides a series of updates and fixes to both the C++ compiler and the standard library. A comprehensive list of these improvements is available at What’s New for Visual C++ in Visual Studio 2017 RC.

In this article, I want to shortly look at the new standard library features from VC++ 2017.

  • std::any (available in header <any>) is a class that represents a type-safe container that can hold the value of any copy-constructible object. To read the value stored in an any variable you need to use the non-member function std::any_cast.

  • std::optional (available in header <optional>) is a class template that may or may not contain a value any moment in time. If it contains a value, it is allocated as part of the optional object, and therefore does not incur any memory overhead.

  • std::variant (available in header <variant>) is a class template that represents a type-safe union. A variant can hold any number of alternatives, but they cannot be of type reference, array or void. The first alternative must be default constructible, because variants are default constructible and a default-constructed variant object contains a value of its first alternative. If the first alternative is not default-constructible, std::monostate (an empty, default-constructible class) can be used for that purpose. If it contains a value, it is allocated as part of the variant object, and therefore does not incur any memory overhead.

  • std::basic_string_view (available in header <string_view>) is a class template that represents a view of a contigous sequence of characters (defined by a pointer to the start of the sequence and a count). Several type aliases are available:

    basic_string_view has an interface almost identical to basic_string so that switching from the later is as simple as possible. A typical useage of this class template is for function parameters as a replacement for constant references to basic_string.

Additional new supported C++17 standard library features are:

  • std::apply is a function template that invokes a specified callable object with a tuple of arguments.
  • std::make_from_tuple is a function template that creates an object by invocking its constructor with the members of a specified tuple.

To have all these available the /std::c++latest compiler switch must be used. This can be also set from the project properties, at C/C++ > Language > C++ Language Support.

, , , , , , Hits for this post: 12197 .

Last week I was in Redmond for the Microsoft MVP 2016 Summit. At the same time, the ISO C++ committee was having its fall meeting in Issaquah, which is very close to Redmond. Therefore, after the summit ended, a group of VC++ MVPs, including myself, decided to make the short trip to Issaquah and attend as observers the meetings, that are actually opened for the public. It was a very interesting experience and I am glad that I had the opportunity to take it.

The committee is organized in several working groups (WG) and study groups (SG). You can actually read all about that here. These groups have separate meetings as they are focussed on different things. I have attended a meeting of the Evolution Working Group (aka EWG), as, at that point, it looked like the most interesting of them all. These meetings actually took place in the same location where the final version of C++14 was voted.

Apart from the topics that have been discussed, which I will not elaborate on here, even though they were interesting and important, it was rather the way the committee is working that it was of most interest to me. I always had the impression that discussions were held in the fashion of the debates in the British Parliament or something similar, and I was surprised to see a much more organized, though still vocal, group. People are patiently taking turns to speak, constantly come with unexpected arguments or counter examples and eventually take polls to see what is the group’s overall opinion on the discussed topic(s). It also helped understand the process proposals go through from an initial form to the one that is eventually voted, if that is the case. I realized that it is way too easy for us to complain that things take too much time to be accepted. The reality is there are so many details that have to be taken into account and it takes many people to see them all. Everything needs to be backward compatible and it takes a lot of scrutiny and proposal iterations to reach a generally accepted form.

Overall, it was definitely a trip worth making, and I am looking forward to doing that again. I also encourage all of you that are interested in that and have the opportunity to take it.

For information about the progress in Issaquah see Herb Sutter’s Trip report: Fall ISO C++ standards meeting (Issaquah).

, , , , Hits for this post: 7995 .

DISCLAIMER: the following is a pure hypothetical list of wishes I had about C++. You should treat it as it is. This is not supposed to be a collection of community agreed list of wishes, nor it is intended to make complete sense, as some of these features are available through the standard library. Please procedure further with that in mind.

I was thinking lately what are the top language features I am missing from C++ but are available in other similar languages (such as C# or Java). After some consideration I have come up with the following list. Note that this list refers to language features only, and not library features and they are listed in a rather random order.

  • Native string type, other than char*, rather a language built-in std::string
  • Native datetime type, that would allow us to specify points of times without a built-in resolution. Obviously adding this after the chrono library makes no sense. This refers rather to a language feature that should have been available from the beginning. The reason for that is specifying date and time is a common operation we often need to do.
  • Native interfaces, other than abstract classes with pure virtual functions only as it is currently possible, because such classes can also contain data members. The reason for this is convenience in defining interface. The syntax for this should not require us to define the member functions as virtual and pure, they should be virtual implicitly. Interface member functions should also be mandatory public so we should not have to declare that either. And last, but not lease, interfaces define contracts and therefore a special interface class should not allow to define data members, not static methods.
  • Properties, basically a pair of get/set accessors over a data member. Having automatic properties to create data members and accessors would be even better. We manually write these all the time and having the compiler generate them for us would be a productivity boost.
  • Extension methods that would enable extending exiting types with new methods without modifying the type itself. This can be be achieve in different ways, but support in the language for this feature means we can extend existing code with new methods without touching it, and call these methods as they were actual member of the class.
  • Template type constraints basically what concepts will provide in the future, so I will not insist on this. Current workarounds with enable_if and SFINAE, static_assert and even deleted functions currently exist.
  • Events to enable a subject to notify observers that something has happened. Obviously this can be implemented explicitly using existing functionality, having native support for that would simplify writing code and increase productivity.
  • Switching on other types than integral types, especially on strings. In general it should be possible to switch on any compile time constant expression. The reason for this is to replace if-else statements with a simpler to write and read switch statement.
  • Finally block for a try-catch so we can specify code that should execute regardless of whether an exception occurs or not. This is supposed be achieved by implementing the RAII idiom. Resources should be released properly upon destruction, but the reality is that a lot of code does not use RAII. Having finally blocks would enable us to run clean up code either if an exception occurred or not.
  • Static classes, that can contain only static members, and static constructors, that are called before main and have access only to static members of a class (there is actually a proposal for static constructors under discussion for standardization). Helper functions may be implemented as static members of a class, and having the class as static would be a constraint on the class to only contain static members.

I do known and understand the principles of C++ and I know these may look counter intuitive. I know why string is a library container, and why time points are available through a library and why these are general purpose implementations intended to meet many needs. For instance the chrono library is resolution agnostic, which means that in the future clocks will deliver picosecond resolution we won’t need to update the library to benefit from that.

On the other hand the reality is that general purpose implementations lack many features developers use all the time, such as converting a string to upper or lower case. This is available in many languages or string libraries, but not in the standard library string. Yes, we can implement that simply in a helper function, but if extension methods were available we could call such a helper function as it was a member of the string class, which would look, arguably, more natural, and also similar to what is available in other languages.

Another reality is that many developers use more than just one language. Some of these features would enable developers coming from a background of .NET or Java development to get a faster and better grasp at C++.

The most important benefits of these feature would be less and probably more readable code and an increased productivity. There are workarounds for these and, yes, we can live without them. But I do not believe that makes at least some of them unreasonable.

I would like to hear what are the features that you miss the most and see if they also appear on this list.

, , , Hits for this post: 9184 .

My book on modern C++ programming


I am happy to announce that my book on modern C++ programming called Modern C++ Programming Cookbook, published by Packtpub, can now to pre-ordered. The book will be published around mid 2017, but pre-ordering gives you early access to the content as it is written.

As the title shows, the book is a cookbook with a collection of more than 100 recipes that will either teach you how to use modern C++ language or standard library features or solve common problems you face constantly. The book also covers useful patterns and idioms implemented in modern C++, but also several major testing frameworks. Recipes are exclusively using features from C++11/14/17. Each recipe teaches you how to do something and how that works, all with useful code examples.

What you will learn from the book:

  • Get to know about the new core language features and the problems they were intended to solve
  • Understand the standard support for threading and concurrency and know how to put them on work for daily basic tasks
  • Leverage C++’s features to get increased robustness and performance
  • Explore the widely-used testing frameworks for C++ and implement various useful patterns and idioms
  • Work with various types of strings and look at the various aspects of compilation
  • Explore functions and callable objects with a focus on modern features
  • Leverage the standard library and work with containers, algorithms, and iterators
  • Use the new utility additions to the standard library to solve common problems developers encounter
, , Hits for this post: 6597 .

C++11 added a date and time utility library called chrono, available in namespace std::chrono and header <chrono>. The problem with it is that the library is a general purpose one and therefore lacks many useful features, such as working with dates, weeks, calendars, timezones and other related features. Fortunately, a rich date and time library based on chrono has been created by Howard Hinnant and is available on github. The library is called date and is actually a collection of several small libraries:

  • date: the main library, available in header date.h, defines new date and time classes and operations with them. All the other libraries are based on this one.
  • timezones: a library for timezones, available in files tz.h/tz.cpp, based on the IANA timezone database
  • chrono_io: a library for streaming durations, available in header chrono_io.h
  • iso_week: a library that implements the ISO week calendar, available in header iso_week.h
  • julian and islamic: libraries that implement the Julian and Islamic calendars, available in headers julian.h and islamic.h

You can find all the necessary documentation on github. Here are several links:

In this article we will look at some examples for working with dates and ISO weeks. This library introduces many new types to handle various date and time representations. Among these we will look at:

  • sys_days: A count of days since std::system_clock‘s epoch. This is a time_point with a resolution of a day, and is implicitly convertible to std::system_clock::time_point, that has a much smaller resolution (millisecond or nanosecond), but not the other way around. To go the other way you must use floor().
  • year_month_day: A type that holds a day with fields for year, month (1 to 12) and day (1 to 31).
  • year_month_weekday: A type that holds a day with fields for year, month (1 to 12), a day of the week (0 to 6), and an index in the range [1, 5] that indicates the number of the week in the month.
  • year_weeknum_weekday: A type that hold a year, a weeknum (1 to 53) and a weekday (0 to 6). This can convert implicitly to and from a sys_days.

For using the library we need the following:

  • include header date.h and namespaces date and date::literals
  • for iso weeks we also need header iso_week.h and namespaces iso_week and iso_week::literals
  • NOTICE: The namespaces date::literals and iso_week::literals define types and literal operators with the same name and therefore can lead to name collisions; therefore you should only include them in the scope where you need them.

We will use the following lambda expression to print various dates to the console:

NOTICE: All the ‘today’ and related dates below are based on 2016-10-31.

Let us look at some examples:

  • create sys_days objects (including literals):

  • create year_month_day objects (including literals):

  • creating year_month_weekday literals and converting to year_month_day

  • create year_month_day values for today, yesterday and tomorrow

  • create year_month_day values for first and last day of the month

    Update: The following, as indicated by Howard Hinnant in the comments, can also be used:

  • create iso_week literals

  • get the iso week number for today

We will look at more utilities and examples in another post.

, , , , , , Hits for this post: 9817 .

In the previous post I have compared two alternative ways of transforming a string to upper case, both using std::transform: one that modifies an existing string and one that generates a new one by inserting at the end using std::back_inserter. For the second alternative I have presented two implementations, one that does an initial reservation for the newly created string and one that does not.

The curious conclusion of the tests was that the version with reserve was actually slower than the one that did not perform an initial reservation.

The solution was built with Visual Studio 2015 Update 2. As it was later noticed in the comments, the actual cause of that is a Microsoft optimization for std::string by using an array of 16 characters for strings that do not exceed this size and only dynamically allocate memory for larger strings. Since all the strings had a length between 3 and 12 characters, this optimization was used for all strings. Therefore, reserve() dynamically allocated memory that was never used and its execution time only added to the overall time.

To actually be able to test the performance of these two implementations with VC++, the strings should be larger than 16 characters. So I changed the code to generate strings between 17 and 25 characters long.

The results this time were totally different. The 3rd version with initial reserving was more performant than the one that did not do that. It can also be noticed that the more strings need to be transformed the more similar times it takes for all the versions.

No of strings time v1 time v2 time v3 Percentage of slowdown with v2 Percentage of slowdown with v3
1000 122 219 205 79.5 68.0
10000 1202 2178 2055 81.2 71.0
100000 13563 22758 21431 67.8 58.0
1000000 136160 225669 214149 65.7 57.3
10000000 1368034 2268991 2155969 65.9 57.6
100000000 23090172 27997658 27322888 21.3 18.3

In the chart below with blue it is represented the results for version 2 and with orange the results for version 3 (with initial reservation).

Note: Generating 100 milion strings between 17 and 25 characters require a lot of memory. In my tests it peaked to 13GB. So if you want to run the code you should be aware of this.

, , , Hits for this post: 6371 .

UPDATE: For an update on the implementation and the conclusions see A comparison of two std::transform alternatives revisited.

I was writing a small utility function to transform a string to uppercase. The obvious solution for that is std::transform, but as I was writing it I realized there are several alternatives:

  • transform an existing string, by setting its elements to uppercase one by one
  • iterate over an existing string, and insert a copy of its uppercased elements into another string, initially empty, using std::back_inserter

Obviously, the second approach should be slower since it has to deal with buffer reallocations. However, I was curious how slower comparing to the first approach that would be. So I decided to test it.

UPDATE: It has been suggested that in the second version I should make a reserve of the string before using std::back_inserter to add characters to the string. Therefore I added a 3rd version that does that.

This is how I implemented the two version different versions of the helper function:

To test it, I decided to randomly generate strings. The length of the strings and their content is randomly generated. Both functions are tested with the same strings after a copy is initially done.

The results, tested with a 64-bit release build with Visual Studio 2015 Update 2, look like below. Times are in microseconds.

No of strings time v1 time v2 time v3 Percentage of slowdown with v2 Percentage of slowdown with v3
1000 40 57 64 42.5 60
10000 593 568 637 42.5 53.1
100000 3894 5769 6497 48.2 66.8
1000000 40005 57852 65793 44.6 64.5
10000000 394573 584048 734463 48 86.1
100000000 4298742 6171199 7577972 43.6 76.3

I have run this several times with similar results. The following image shows how much slower the versions using std::back_inserter were comparing with the version that modifies the string directly. With blue it is represented the results for version 2 and with orange the results for version 3 (with initial reservation).

This clearly indicates that using std::back_inserter is slower, and it is actually 30 to 60% slower. However, what has surprized me is that reserving the necessary space for the string before std::back_inserter starts inserting elements is even slower (in some cases it can take twice as much time than version 1). Of course this measures the time to allocate the buffer too, not just the time for transforming the string, but the point here is to profile the entire function, not just the transform operation.

, , , Hits for this post: 6750 .

Last week I have attended ITCamp in Cluj-Napoca, Romania. The conference has already established itself as the most important community-driven technology conference in Romania and lately, as the organizers put it, its focus has shifted from being a Microsoft-centric conference to a technology-centric conference. And this year it has been larger than ever before: 600 attendants, more than 40 speakers, more than 50 sessions and open panels grouped on 5 different tracks. A little bit for everybody. And with so many tracks and session it was a little bit hard to make choices for what to attend or maybe rather what to skip.

All sessions have been recorded and will be made available some time in the future (as far as I understood). In the meanwhile I wanted to point some of the things I seen and learnt at ITCamp. I actually attended more talks than the one mentioned here. Most of them were really good and I apologize to those not mentioned, but I don’t want to mention everything here, so I will try to summarize only a few things that I found the most interesting.

  • Security
    I have attended several talks on security. Paula Januszkiewicz gave all of us creeps by showing how a skillful person can extract information such as encrypted passwords and history information that the system stores on disk without most users being really aware of it. And even though the secrets are well kept for a regular user, a malicious person or software can exploit weaknesses to extract these information. On the other hand Jayson E. Street shared his experiences with compromising security in all sorts of companies around the world. Having a 100% success rate Jayson doesn’t blame it on the employees or users (explicitly saying there is no such thing as stupid user) but on the lack of education/training on security that companies are providing (or rather not providing) for their employees. His talks made us laugh but also think a lot and hopefully be more aware of things we shouldn’t do from the point of view of security. One thing for sure, I will never plugin a USB stick that I find on my desk in a blank envelope with my name on it. Thanks Jayson!

  • Internet of Things
    Who would have though several years ago that your greenhouse could be monitored and controlled from the internet? That it could send pictures to your phone? That you can make predictions on when and how much to sprinkle based on the existing data? That’s what Laurent Ellerbach, Microsoft Technical Evangelist Lead, shown in his keynote. Sensors, Raspberry PI, cameras, Azure IoT Hub, Stream Analytics, Mobile Services, SQL Azure and others working together to create a real world system for a sprinkler for his small greenhouse at home. It was a very interesting talk with a real life project and its development over time to include more and more services.
  • PowerShell is now an OOP language
    I am not very skilled with PowerShell, though I have to use it from time to time. I had no idea though that PowerShell 5 supports many features from object-oriented programming. These includes: classes, methods, properties, inheritance, enumerations and others. Razvan Rusu delivered an entertaining talk for both developers and sysadmins showing how easy you can do things in PowerShell and what the new OOP features are. It was really interesting and will certainly look at PowerShell from a different perspective from now on.
  • .NET core
    Raffaele Rialdi gave a compelling introduction to .NET core, its components, flavors, its new deployment mechanism based on NuGet and other related topics.
, , , , , , , Hits for this post: 10185 .