Photo by chuttersnap on Unsplash

Concurrency in Python: Cooperative vs Preemptive Scheduling

Why is it that I can move the mouse pointer on my computer while watching a movie? Or open an email while on a video call? Even in the days when CPUs were single core, computers were seemingly able to manage all sorts of tasks at the same time. Yet every task — even just moving the mouse — requires some CPU time, and single core CPUs can only do one thing at a time.

The answer is that CPUs are so unimaginably fast that even though two things can’t actually happen at the same time, it is possible to give the impression that they do. This phenomenon is called concurrency.

Implementing concurrency is a software problem. Even the best hardware can feel sluggish if the software doesn’t get its concurrency model right. The key requirement for a good concurrent system is that tasks that affect user experience are actioned near instantaneously, while lower priority tasks wait.

Even the best hardware can feel sluggish if the software doesn’t get its concurrency model right.

In this article we explore the most important categorisation of concurrent programming paradigms: cooperative vs preemptive scheduling. The discussion will take place in the context of the Python ecosystem, though analogous tooling will exist in many general purpose programming languages.

Concurrency vs Parallelism

Before we begin, let’s clear up a common subject of confusion. While in the English language the words concurrency and parallelism have similar meanings, in computer science they refer to distinct ideas:

• Concurrency: utilising one CPU in such a way that it appears to the user that multiple things are happening at the same time, even though in reality the CPU is only doing one thing at a time;
• Parallelism: speeding up a computer program by dividing the work it has to do between multiple CPUs, meaning multiple CPU instructions really are being executed at the same moment.

In other words:

• Concurrency: one CPU, many tasks;
• Parallelism: many CPUs, one task.

This article is about concurrency. While parallelism is closely related to concurrency, it is a subject in its own right and warrants a separate discussion.

Multi-core CPUs

Nowadays most CPUs have multiple cores, which means computers can literally perform multiple tasks at once (parallelism). Does this make concurrency unnecessary?

The problem is that at a given moment your computer is doing not 2 things but 2,000 things. Computers are stupendously complicated, with all sorts of programs and services, some of which you probably have no idea even exist, making demands on your system’s resources. Therefore even with 8 or 16 cores to play with, the concurrency problem still arises.

Schedulers

At the heart of a concurrent programming model is a scheduler. The scheduler decides what the CPU should focus on at each moment in order to give the impression that multiple tasks are happening at once.

The scheduler’s job is akin to that of a chess grand master playing simultaneously against 10 opponents. How should the grand master divide their time between them?

A chess grand master playing simultaneously (Credit: US Air Force)

One way is to take a move against the first opponent, then the second, and so on until the tenth, and repeat this process until all games are finished. But this makes no allowance for the games to place differing demands on the grand master. Some opponents will take longer to make a move, some will be more skilled and some game positions will be more cognitively demanding.

Cooperative Scheduling

One way of improving this naive model is to empower each individual opponent to request the attention of the grand master and release the grand master when they no longer need them. This is the idea behind cooperative scheduling.

How Does a Cooperative Scheduler Work?

The easiest way to understand cooperative scheduling is to look at a simple example. Suppose I want to make a command line application that:

1. Every five seconds, prints the current time;
2. Whatever the user inputs gets echoed back in upper case.

Let’s start by writing functions to do each of these tasks on their own:

There are a few things that make running these functions concurrently difficult:

1. The while True: loops on lines 4 and 9 mean that both functions never return, precluding the possibility for any other operation to take place;
2. The time.sleep(5) on line 6 prevents anything else from happening for 5 seconds;
3. The input() on line 10 prevents anything else from happening until the user finishes providing input.

To achieve concurrency we need to fix these issues. The following code runs modified versions of these functions using a simple cooperative scheduler.

Let’s take a look at some of the key components:

• The ready queue is a queue of tasks which should be executed as soon as possible. This is initialised on line 18.
• The waiting queue is a queue of tasks which should be run at a specified future time. This is initialised on line 19. Members of the queue are a tuple where the first member is the task to run and the second member is the minimum time at which that task becomes ready.
• The event loop is a loop which (a) executes tasks on the ready queue and (b) moves tasks from the waiting queue to the ready queue. This is found on lines 28–35.

Notice that print_time and echo_input are passed the scheduler object as an argument. This means that, instead of looping indefinitely, they can simply add themselves back onto the ready queue or waiting queue before returning, thus ensuring that they will get called again in due course. In the case of print_time, it adds itself to the waiting queue with a 5 second delay to replicate the time.sleep(5) behaviour.

In the case of echo_input, we use the select module to check if there is any text available to process from stdin. This allows us to check for user input without blocking (caveat: this will not work on Windows).

The important thing to observe is that the modified versions of both print_time and echo_input always return without waiting for anything to happen. Rather than hogging the CPU until the event they are waiting for occurs, they place their trust in the scheduler to hand back control to them again at the appropriate moment.

Tooling

You will be pleased to hear that in the real world writing cooperatively scheduled code is easier than the previous section makes it look. Perhaps the best known tool for doing this is asyncio, part of the standard library. Using this, our code becomes:

Notice that print_time looks very similar to the synchronous version, except we need to replace time.sleep with asyncio.sleep. For echo_input, it turns out asyncio is able to work out when stdin is ready for reading and call echo_input, so all echo_input has to do is print that input in upper case.

Three other notable tools for cooperative multitasking in Python are Trio, Curio and Greenlet.

Preemptive Scheduling

Let’s return to the chess grand master analogy. The problem with going through the opponents one by one is that the grand master might get stuck on one particularly difficult game, forcing the other opponents to wait.

A simple solution is then for the grand master to set a timeout of say 20 seconds. If they still don’t have a move, they “save” their current state and move onto the next opponent. They then cycle through the opponents in this way until all games are finished. Of course, a human being isn’t able to save the current state of their brain and come back to it later, but computers can do just that.

This is a simple example of preemptive scheduling. Here, the verb preempt means to halt the execution of a task with a view to resuming it later. This happens without the knowledge or agreement of the task being preempted.

The process described above is known as a round-robin scheduler, but many other preemptive scheduling algorithms exist, considering factors such as:

• The priority. The scheduler may allow a program to create tasks with different priorities.
• Previous behaviour. If a task tends to always run for only a very short period when it is scheduled, the scheduler may run it more frequently.
• Voluntary cooperation. Even a preemptive scheduler may provide tasks the option to explicitly give other tasks a chance to run. The scheduler may also accept “hints” from tasks about their behaviour, such as a task telling the scheduler “I will take a long time to complete”.

Threads

With cooperative scheduling, we were able to mock up a primitive scheduler in just 17 lines of code. Preemptive schedulers are more complicated. The scheduler needs to:

• Be able to interrupt running code;
• Monitor running code to understand what state it is in, such as whether it is waiting for a file to open, sleeping or running a CPU bound operation.

In both cases, only the operating system is in a position to be able to implement preemptive scheduling. This means that whereas various cooperative scheduling frameworks exist, there is only one way to achieve preemptive concurrency: threads.

Threads are an abstraction provided by operating systems to represent a series of CPU instructions. When multiple threads are running at the same time, the operating system will schedule them preemptively.

In Python, threads can be leveraged using the threading library. Here is our previous example using threads:

As if by magic, the two functions run concurrently! Why didn’t we just do this in the first place?

The thing about threading is, threads can be preempted at any time. You have to be prepared for the processor to suspend your function and work on something else on any line of code or indeed when it is part way through a particular line of code. This makes it very difficult to reason about how threaded code will behave. While our toy example works just fine, getting complex threaded applications right is notoriously difficult.

Buggy multi-threaded code creates race conditions, which are the most dangerous and time-consuming class of bugs in software. — Bobby Holley (full article)

Cooperative paradigms, on the other hand, only yield control to the scheduler at certain points in time.

Which should I use?

Advantages of Cooperative Schedulers

If a feature can be implemented using cooperative or preemptive scheduling, and you are trying to decide which to pick, go with cooperative scheduling.

• Code can hold on to the CPU’s resources for as long as it needs to without being unexpectedly interrupted. This makes it far easy to reason about the behaviour of cooperatively scheduled code.
• The overhead of switching from one task to another cooperatively is low.

The first point, as discussed in the previous section, is a huge win. Specific testing techniques exist to increase the reliability of threaded code, but still the possibility of code being preempted at any time makes it extremely difficult to consider every possible race condition that may occur. And even if you do get it right, the next contributor may be less careful.

The second point may not matter for a few tens of concurrent tasks, but for a web server, cooperative scheduling materially increases the number of concurrent connections a single machine can handle.

Superpowers of Preemptive Schedulers

There are some situations where a cooperative scheduler simply won’t work:

• If tasks are poorly behaved, they may hog all resources indefinitely. In our chess example, an opponent could request the grand master’s attention at the start and not let them go until the game had finished, forcing the other opponents to just sit waiting.
• If code cannot be modified, the logic to request and release the CPU at appropriate moments cannot be added. This is the usually the case when using a third party library that wasn’t specifically designed for cooperative scheduling — and even then, it may only work with a specified set of frameworks.

Preemptive schedulers may not be better than cooperative schedulers per se, but they have powers that cooperative schedulers simply cannot hope to wield. If either of the above apply to you, preemptive scheduling may be the only choice.

Conclusion

In this article we have explored the most important categorisation of concurrent programming paradigms: cooperative vs preemptive scheduling. We have looked at how to apply these concepts to simple Python programs and when each is appropriate.