A Simpler Solution to the Dining Philosophers Problem

Introduction

When I was first introduced to the Dining Philosophers problem, my initial reaction was that it is a silly problem with a touch of obscurantism. As I read, it was originally created by Dijkstra as an exam problem in the 1960s. Some teachers do indeed have a predilection for whimsical problem formulations, which more often than not, though, are distracting more than they are illuminating. Later on the Dining Philosophers problem was promoted to a canonical problem in computer science, arguably after Tony Hoare discussed it in his book Communicating Sequential Processes. Now it is a standard problem in any course on Operating Systems or Concurrent Programming.

In this article, I will first highlight the issue that the original problem is poorly formulated. Second, I will propose a solution that is simpler than the three typical solutions that are commonly taught, and similar in spirit to a fourth but non-canonical solution.

First of all, what bugs me the most is that this problem appears to be much deeper than it actually is, by giving it this utterly pretentious name, Dining Philosophers. It is as follows: there are five philosophers, five forks, and an infinite amount of spaghetti. For some odd reason, philosophers need two forks to eat. They cannot eat and think at the same time, and they all want to both eat and think. Since nobody eats with two forks, I’ll replace the forks with chopsticks, and the spaghetti with rice. I will still refer to them as philosophers, to retain the pretentious nature of this problem. “Guys with chopsticks” just does not have the same ring as “Dining Philosophers”.

Let me now run through the typical issues discussed in the context of the Dining Philosophers problem:

1) Deadlock: if every philosopher grabs just one chopstick, they all wait forever until a second chopstick becomes available.

2) Livelock: if every philosopher can only hold on to chopsticks only a given amount of time, and they manage to perfectly synchronize this, you end up with the situation that they all pick up and release one chopstick at the same time, over and over.

Canonical Solutions

The three canonical solutions are:

1) Resource hierarchy (Dijkstra): Number the chopsticks from 1 to 5; introduce the convention that each philosopher has to pick up a chopstick with a lower number first. This prevents deadlock because, after allocating four chopsticks to four philosophers, the last philosopher cannot pick up chopstick number 5, since 5 is the highest number.

2) Create an arbitrator: implemented as a mutex, an arbitrator gives permission to philosophers to pick up two chopsticks at a time.

3) Introduce the notion of cleanliness (Chandy/Misra): label philosophers with an id ranging from 1 to n. For each pair of philosophers fighting over one particular chopstick, give it to the philosopher with the lower id. Each chopstick can be dirty or clean, and initially they are all dirty. When a philosopher wants to eat, he needs to request chopsticks. Any philosopher who receives a request keeps a chopstick if it is clean, but if it is dirty, he relinquishes it. Before handing over a chopstick, he cleans it. After a philosopher is done eating, all chopsticks are marked as dirty.

Those are the three canonical solutions to the Dining Philosophers problem, but I came across a fourth one:

4) Remove one chair (Stallings): Take n philosophers and n chopsticks. Now, remove one chair so that only n-1 philosophers can take a seat.

A different, and simple, solution

I thought about the dining philosophers problem a bit, and came up with a solution that retains the original conventions. In that regard, it is unlike the fourth approach, even though it is similar in spirit, as it equally aims for a rather straightforward solution. Obviously, chopsticks can only be used in pairs. Thus, the solution is to simply let philosophers only take two chopsticks at a time — and we are done! Concretely, put all n philosophers in a queue P, and all n chopsticks in a separate queue C (a stack would work just as well). While C contains at least two chopsticks, the philosopher at the top of P takes two chopsticks from C and eats, and so on.

It should be obvious why this approach works. If not: The philosopher at the top of P takes two chopsticks from C, and starts eating. When he is done (feel free to have him eat until he receives a request to release his chopsticks; it does not matter), he adds both chopsticks to C again. Continue until all chopsticks have been distributed. If there are no two chopsticks available, the remaining philosophers wait for their turn. Thus, the first philosopher takes two chopsticks, and eats. Then the second philosopher takes the next two chopsticks, and eats. The third philosopher would only get one chopstick, for the time being, so he waits. Eventually, though, the first philosopher will be done eating, and subsequently put his two chopsticks back to C. Because you always take two chopsticks from C, and philosophers only eat for a finite amount of time, there is neither deadlock nor starvation.

[EDIT: On Reddit is was pointed out that the stack is the arbitrator (waiter) in disguise. This is correct. There was also an issue that the chopsticks are treated as commodities, while they should be distinguishable. For instance, philosopher 1 can only take chopsticks 1 and 2, philosopher 2 only chopstick 2 and 3, and so on. To salvage my approach, which now makes it even clearer that C is just the waiter in disguise, have it store pairs of neighboring chopsticks. A more complicated bookkeeping mechanism is needed for the chopsticks, though. Anyway, using that approach, philosopher 1 takes the pair (1, 2), and leaves the waiting queue. Philosopher 2 would like to take pair (2, 3), but chopstick 2 is taken, so he has to move to the end of the waiting queue. Philosopher 3 can take chopsticks (3, 4), though, and so on. Once philosopher 1 is done, he returns the pair of chopsticks, and moves to the back of the waiting queue, etc.]

Lastly, note that there is no need to have exactly five philosophers. Presumably, this number is only used due to the historical accident of Dijkstra using that particular number. You need at least two. Some of the solutions we have seen have an administrative overhead, so it will only get more cumbersome the more philosophers we add to the table. However, by using a queue, you could feed an arbitrarily large number of philosophers without any overhead. Also note that whenever there is an odd number of chopsticks, there is one superfluous chopstick, since you cannot properly eat rice with just one chopstick. Thus, there are at least three aspects in the original problem statement that obscure the problem: the number 5, the strange convention of using two forks, and the fact that the fifth fork is superfluous. Lastly, calling the diners philosophers is potentially distracting.

Retrospective: Software Engineering Summer Internship (2015) at Jeppesen Systems AB in Gothenburg

Leave a reply

Introduction

Jeppesen is a fully owned subsidiary of Boeing, and part of their Digital Aviation business. Concretely, they provide navigational information, crew and fleet management solutions, and offer an industry-leading optimization product. The Gothenburg office started originally as Carmen Systems, which was spun off Chalmers University of Technology. Ties between Chalmers and Jeppesen are still strong. The Gothenburg office of Jeppesen employs around 350 people, of which around 300 are technical staff. Further, there are around 60 contractors in the building.

Jeppesen was not an entirely new entity to me. I had been mentored by one of their managers for about a year, though whom I met several other Jeppesen employees, including a veteran software architect with a very strong technical background, and an experienced software developer. Further, I was one of the winners of a coding competition they held this spring, and one of five students who were invited to what turned out to be an intimate recruiting event, where we were outnumbered by Jeppesen managers and employees. Several managers represented their division, the challenges they are working on, and, of course, the kind of skills they are looking for in future employees. Alas, back then they did not have any openings, but we were told that a number of full-time positions would open up in autumn, and possibly some summer internships as well. Both turned out to be the case.

The interview

I applied for a data processing project with a parallel programming component, which I will detail further below. But before I got to do any work, I had to make it through the interview. Job interviews are often cringe-worthy, particularly the “your greatest weakness”-kind. The interview experience at Jeppesen was distinctly positive, though. The hiring manager briefly came in to shake hands and exchange some niceties, but otherwise, the interview was conducted by two senior engineers. They described the project, how they work, and the technologies they use.

What I greatly appreciated was that they were looking for competence instead of buzzwords. We even talked a bit about the necessary computer science background for their project. It was helpful that I had heard of recursive descent parsing, had written a parser for a subset of C++, or implemented a compiler for a C-like language. Normally, a coding test is also part of the interview process, but I presume this was skipped due to my performance on their recent coding challenge. Still, they asked me a few ‘design’ questions, like how I would approach this or that problem, or pros and cons of concrete approaches to given problems. Thankfully, it was more about how to break down a complex task into manageable subproblems, instead of the dreaded UML and design patterns interview.

The project

Of course I signed and NDA can therefore not be too specific, so I am only going to describe the problem in general terms. Let’s say your software runs on dozens or possibly even hundreds of machines at a customer site. Each copy of the program produces partly unstructured log files, recording all kinds of things. In order to extract useful information from those log files, you have to run a parser that understands the structure of the files, and extracts relevant information, which may be processed further. To make this even more fun, let the client machines run around the clock, and update log files continually. This sounds fairly complicated already. However, keep in mind that you have more than one customer, many more than one parser, and currently you only execute one parser after another in a sequential order via a cron job once a day, for historical reasons, maybe because the programs predate the many-core CPU era.

The goal of the project I was given was to write a framework that parses all log files — think in orders of magnitudes of tens of thousands of files — in pseudo-real time, so that you can extract more useful information from the existing data. For instance, if you take a metric like ‘active instances’ once a day, you’ll learn a lot less than if you are able to update this metric every few minutes.

Concretely, the framework I developed unified the existing parsers for several Jeppesen products. Understanding and modifying existing parsers required a little bit of background in programming languages. This was pretty fun, but the most interesting aspect was trying to find ways to effectively parallelize the execution of the parsers. The hardware at our disposal was pretty decent. Thus, running a single-threaded program on a many-core CPU is a bit of a waste, to put it mildly. My approach was to avoid all shared state. Once this problem was solved, the actual parallelization was easy to achieve. The machine I was mostly working on was an Intel Xeon with 16 cores and over 100 GB RAM, which was far from being the most powerful machine I had access to. Even on that one, we easily hit our performance target.

In my last two weeks, I had plenty of time to ensure the documentation was comprehensive. At the same time, my main supervisor put the project successfully into production at two customer sites, both major European airlines. At both sites we encountered minimal issues that were easily resolved. In one case, the volume was much greater than the fairly large test data directory I had been working with, so I needed to use a more efficient data structure, and make use of memoization at one point in order to resolve a bottleneck. At the other customer site, a slightly different naming convention for some files was used, which was an even easier fix. My last update was that this product has been successfully rolled out to two more customers.

The software development process

While Jeppesen is officially committed to “Agile”, they nonetheless have a strong engineering culture, which entails that they make use of software processes not for their own sake but when there is a clear benefit. The first few days on the job, I was expected to do the daily “stand up” song and dance, and report on everything I’ve done, what I intended to do that day, and give various estimates about the next few days. Personally, I found this more annoying than helpful. After I showed a proof of concept of this product after a few days, instead of the planned two weeks, my supervisors concluded that I can apparently work well on my own, and scrapped daily meetings. Instead, we had the occasional demo session, or just casually discussed progress during company breakfast.

I did like that, after proving myself, I was given relatively free reign with regards to the development, of course while still conforming to the overall vision of the product, which I received at the beginning in the form of a succinct document. The eventual software development process was somewhat reminiscent of Iterative and incremental development.

The work environemnt

Based on my experience at a previous employer, and from various company visits, I would say that Jeppesen has a clearly above average office environment. It’s not uncommon that three or four employees share their own, reasonably spacious office. However, there are also several open-plan office areas, the kind that is claimed to foster cooperation and communication, even though they are “damaging to the workers’ attention spans, productivity, creative thinking, and satisfaction”. Well, Joe Programmer, no matter where on the world he works, sadly does not command enough status to get his own office. Thus, companies are, quite literally, squandering money by not giving people access to (genuinely) quiet working environments.

Still, thanks to artificial dividers, plants, and a reasonable amount of space, the open-space areas at Jeppesen are quite okay. I was sitting in one of the larger ones in the building, among around 15 employees, all fairly well spread-out. The main office hours are a bit busy, with infrequent distractions. However, if you come in very early or stay late, you can enjoy a quiet working environment and get a lot done. During the busier hours of the day, you may notice decreased productivity, compared to, say, intently working on something in the privacy of your home.

A few perks are offered, too. Every morning, there is free basic breakfast, which is also a great opportunity to talk to people outside of your department. Further, bowls of fruit are placed all over the building. This being Sweden, there is also a strong tradition of having ‘fika’, i.e. a short break for consuming coffee and pastries. Noteworthy is that a masseuse visits the office in regular intervals, for which you can sign up at reception, and get the cost deducted from your pay. Regular employees are even entitled to some free money (friskvård) for that purpose, or other health-related expenditures.

Working hours are quite flexible. You are expected to put in 40 hours per week. As a rank-and-file employee you have to be present during core business hours (9:00 to 15:00), but you do have some flexibility otherwise. For instance, taking the occasional long lunch break, and staying longer some other days is certainly something you can discuss with your manager, just like taking half a day off and putting in a few more hours on some other days to make up for it. Overall, they try to achieve a good work/life balance.

Summary

This was a very enjoyable internship, and a summer well-spent. The end result was that I wrote, relatively independently, a medium-sized application weighing in at thousands of lines of code, all tested and well-documented. It was a good mixture of intellectual challenge and more mundane practical aspects. In the beginning, intellectual challenges were more dominant, like the entire design of the product, or figuring out effective parallelization. Later on, the focus was much more on polishing the code base, and eventually deploying it. The latter was not quite as mentally stimulating, but on the other hand it was immensely gratifying to see the project hitting or exceeding all performance targets, as well as its successful deployment.

A graduate’s perspective on the Software Engineering and Management Bachelor’s program at the University of Gothenburg

9 Replies

Introduction

I graduated from the University of Gothenburg with a Bachelor’s degree in Software Engineering and Management (SEM) in June. When I applied, in 2012, there was relatively little authentic information available online. The university websites surely were informative, and the PDF flyers well-produced. On the other hand, students did not seem overly vocal online. Thus, I would like to give my personal perspective, which may help future applicants. The information below should be useful for at least the next five to seven years, considering the pace at universities. For the past few years there has been an initiative in the department to further evolve the curriculum, though. This will lead to some changes, but from what I gather the changes will be of an evolutionary nature.

The target student

I assume that you, the reader, are a non-Swede and, for whatever reason, want to move to Sweden to pursue an IT-related education. If you are flexible with regards to the location, and can afford paying tuition fees, you certainly should explore other options as well. My motivation for coming to Sweden was to live with my girlfriend. Indeed, talking to other international students, male and female alike, this seems to be a fairly common motivation.

If you don’t speak Swedish, your options with regards to Bachelor’s degrees in Sweden are rather limited. In 2012 there were very few options available, and the SEM program seemed the most promising. Proper computer science programs were, and still are, taught in Swedish. It seems the issue a lack of willingness to provide access to certain programs to foreigners. For instance, almost every course in the computer science program here in Gothenburg is taught in English. Yet, a very small number of introductory courses in that program are offered only in Swedish, which thus precludes foreigners from enrolling. The language is hardly the problem, considering that you may take courses in the SEM program that are officially taught in English, but by people who do not have a proper grasp of the language. On the other hand, some of the introductory courses in the CS program are taught by academics who speak excellent English, but for whom Swedish is only their third language.

Whatever the reason, fact of the matter is that your options with regards to English-speaking Bachelor’s programs in Sweden are limited. The SEM program is one of very few choices. Thus, the question is whether it is good enough. In my opinion, even though my view is not entirely positive, for reasons I will elaborate later on, it is a decent program that tries hard to teach relevant knowledge and skills, with the aim of turning you into a productive cog in the wheel in the IT industry. They are not turning out superstars, but given that there’s a perennial Amateur Hour in large parts of the software industry, with all their “ninjas” and “gurus” who barely grasp the basics of their craft, they don’t have to.

Prerequisites

Formally, the SEM program does not expect students to have any kind of programming experience. However, it would be rather naive to enter a program like this without having done any programming at all, since it will be a major part of your education. Quite frankly, if you have never programmed in your life, and you nonetheless consider BSc programs related to IT or CS, you should set your priorities straight. Computer science is one of if not the most democratic discipline at university, since there are no artificial barriers. All the information you would need to educate yourself is available for free online. Nowadays you can even find entire university courses online. In short, there is absolutely no excuse not to have at least basic programming knowledge. If you don’t then you may end up in the rather uncomfortable position to find out that programming is not quite as trivial as you imagined it to be.

Let me point out that the word, management, in the name of this degree program is potentially misleading. The management part in the SEM program is concerned with managing software projects, but not with general management. If you are interested in an education in business, this is the wrong degree to pursue. Sadly, this is apparently not at all self-evident. If you are “more of an ideas guy” and have wet dreams of bossing nerds around, then business school is where it’s at. Unfortunately, there is at least a handful of incoming students who come to class impeccably dressed for a few weeks, and who eventually realize that the content of the SEM program does not meet their expectations.

I don’t think you necessarily have to like or “love” programming. For most people in this industry software development is a job. Their studies were a series of hoops they had to jump through, but their craft is nothing they have any, to use a horribly overused word, “passion” for. That’s okay, though. The commoditization of software development has been going on for about two decades. If you’re a True Believer, you might even find some worthy cause in that movement. Otherwise, you are either fortunate to be employed by a company that does interesting work, or you use your brain in your spare time. No matter where you might be on this spectrum, at the very least you should have done enough programming so that you can assess whether you have some aptitude for it. It’s okay if you find it tedious — mainstream programming languages are indeed tedious to work in. However, if you happen to dislike programming and struggle with basic concepts like control flow or boolean operators, you won’t do yourself any favour by pleasing your parents who think that a career in IT is a sound choice in the early 21st century.

The curriculum

Considering that computer science tends to have the reputation of being too theoretical, one can easily make the claim that the SEM program is too practical. Indeed, the curriculum is strongly geared towards teaching skills that make you employable in the IT sector. Each semester has a particular theme. You get exposed to several mainstream languages: Java, C++, and C, as well as one particular off-beat language that is part of the curriculum because a local employer infrequently needs people with that skill: Erlang, which is used within Ericsson. If you try hard, you can avoid learning Python or JavaScript, but normally students use at least one of these in some of the projects, even though there will only be very little formal instruction, or none at all.

Considering that the SEM program does not expect students to have any kind of programming experience, you will spend the first semester on basics: Java, relational databases, but also a bit of software engineering theory where you learn about some common software development processes, and get your first dose of Agile/Scrum indoctrination. Half of the entire course load is dedicated to a group project where you build a simple CRUD application. The first semester will be the most chaotic of the program, due to large numbers of students dropping out, and others hanging on for too long. This tends to affect the group project as well. In my cohort, so many students dropped out, and others found out that they tremendously dislike each other, that several groups had to be dissolved, rearranged, joined, or split.

In the second semester, in a second course on programming, you will learn about basic algorithms and data structures, which takes 25 % of the course load. Another 25 % is spent on software engineering courses that may make your eyes glaze over, and 50 % on a relatively open ended group project where you build a “system”, which is supposed to mean that your code shall make a piece of hardware do something non-trivial. In my class, we got to play around with the educational robot NAO by Aldebaran. Among others, we managed to make it navigate a maze. One of the more ambitious recent projects consisted of building a quadcopter and making it do some things you may easily take for granted if you buy one off the shelf, for instance making it stabilize itself if you throw it off balance.

In the third semester you will be exposed to functional programming. You will have the privilege to learn Erlang and gain practical experience in building a medium-sized distributed application in it. You can also learn that putting Erlang on your LinkedIn profile has the side effect that recruiters from the UK will start contacting you. The software engineering courses on software architecture and software management will provide you with the right vocabulary for interviews at typical software development companies. Considering that most of the SEM program is spent on mainstream technologies, a semester mainly devoted to functional programming in Erlang is a welcome breath of fresh air.

Working in a more expressive language like Erlang might have changed how you view programming. Dropping down several levels of abstraction to manipulating bits in C might have the very same effect. In the fourth semester you will start with programming a microcontroller and gain intimate acquaintance with segmentation faults. The semester project is by far the most ambitious of the SEM program: you are supposed to build a self-driving miniature car. In a course on testing you will, among others, get exposed to randomised testing using QuickCheck, which might make you question why people bother with unit tests.

In the fifth semester you get exposed to some rather questionable software engineering modules, with a focus on change management. Quite frankly, I saw very little value in it. Thankfully, if you have any experience with academic writing, none of the courses should take much of your time. Part-time work isn’t so easy to find in Gothenburg, so if this is not an option for you, then taking computer science courses, or working on your technical skill set may be worth thinking about.

Lastly, this degree program culminates in a Bachelor’s thesis project. The faculty is very supportive, which means that as long as you have the necessary skills and can write a decent thesis proposal that is related to software engineering or computer science, you can work in many areas — even theoretical computer science is possible, provided you took some additional courses. Most students work in groups of two, some in groups of three, and some on their own. Further, you can do your thesis either in an academic setting, or in collaboration with the industry. The latter may be a good opportunity to find an employer, but the downside is that you will be less flexible with regards to the choice of your thesis topic.

After graduation

The goal of this program is to prepare you for a role within the software industry. While some of the graduates work as software developers, others become testers or technical writers. If technical skills aren’t really your strong suit, then you may get the chance to enter a larger company and get promoted to the position of “Agile Coach” or “Scrum Master”. Particularly if you are a member of a protected class, several career paths may open up that are only tangentially related to technology. After all, Swedes love their ‘diversity’ and political correctness.

Judging from my graduating class, people seem to find work relatively quickly. Gothenburg is not exactly a hotbed of technology, though. In my opinion, there are not so many interesting positions available locally. On the other hand, if your prime goal is to get a job in the IT industry that pays the bills and puts food on the table, then Gothenburg has plenty to offer. For instance, there are several large consulting companies. Sigma and HiQ are relatively prominent, and readily hire graduates from this program. Other large employers in the region include Ericsson and Volvo IT. The kind of work you can get at those companies may be sleep-inducing, but it presumably beats the heat and humidity that is part of flipping burgers.

If you just want to find reasonably interesting work, then the SEM degree should do. In Sweden it is not at all uncommon to find people who work in this industry without having any degree at all, and it is still possible to enter it without any piece of paper. The only difficulty is getting a foot in the door. On the other hand, if you want to expand your horizon, and possibly prepare yourself for working in particular industry sectors, then studying towards a Master’s degree may be a good idea. In that regards, some students take the easy way out and study the Software Engineering Master’s program at Gothenburg University. I’m not sure whether SEM graduates are guaranteed a place, but even if not, it seems very easy to get admitted coming from the SEM program, which is no surprise since the Master’s program builds upon some of the Bachelor’s courses. It is much more about software engineering processes and ideologies than developing technical skills, though.

It is not at all uncommon that students move into related fields. Some pursue degrees in IT Management, others go to business school. Pursuing more technical fields is also possible. A minority of graduates moves on to study computer science in various flavors at the Master’s level. One of my former class mates, for instance, is currently studying towards an MSc in Financial Systems Engineering at University College London, for instance. The vast majority of graduates seem to want to stay in Sweden. In fact, very few even move away from the Gothenburg area.

Recommendation

In my opinion, the SEM program is a good choice for people wanting to gain a decent technical skill set. There are some disadvantages, though. Personally, I think university studies should first and foremost provide a sound theoretical foundation, and not concern themselves too much with applicability. Concretely, in the case of the SEM program, I would certainly say that there is value in doing one larger group project, where you learn to collaborate, to plan your work effectively, and practice leadership skills. However, four projects are overkill. I would have much preferred seeing a curriculum that reduced group work and instead added a few more computer science courses. That being said, if you do have solid technical skills and are able to organize your work well, then the group projects will not take up too much of your time. Thus, you can take additional courses. I managed to squeeze an additional year’s worth of mathematics and computer science courses into my three years in the SEM program, for instance.

When I started, in 2012, there were very few Swedish universities that offered Bachelor’s degrees in English. This is no longer the case. These days, though, you can study technical degrees at the Bachelor’s level at Uppsala, KTH, and Lund. Depending on your interests, those may be better choices. One downside of the SEM program is that it is relatively narrowly focused on software engineering, and only provides a small core of computer science knowledge, which may limit you in the future. On the other hand, for instance, a Bachelor’s degree in Mathematics at Lund, which leaves significant room for electives, will provide you with much greater flexibility. If you think that software development is exactly what you want to do (how would you know that?), then the SEM program is a good choice. Otherwise, I would recommend a more foundational degree, like computer science, or even mathematics. The former, though, is currently not an option in Sweden if you don’t speak Swedish.

Compiling Agda to System Fω in Theory

An FFT (Cooley–Tukey) for a synchronous dataflow extension to Feldspar