Time management in human and computer systems

If you’re like me, you have a long todo list and a nagging sense that perhaps, you may not be doing your tasks in the right order. But how can you measure whether an order is better or worse, and how can you find the best one?

I first got answers to these questions when reading Algorithms to Live By, in the chapter on the parallels between scheduling tasks in operating systems and in life 1. When reading about scheduling in actual operating systems, I found that the scheduling algorithms actually used account for more cases and are closer2 to the real constraints of human task scheduling. They’re described in more detail here, along with the parallels I saw.

1 Parallels between human and OS scheduling

The more that I read about scheduling in operating systems, the more the parallels with human time management become clear. In fact, a lot of the discussion within OS scheduling is rather lucid, and sheds light in the tradeoffs of human time management.

1.1 Context switching: cognitive vs procedural

Looking at OS context switching, we see that there are actually two different costs to context switches, which I distinguish as “procedural” and “cognitive”. 3 When switching tasks in a CPU, the biggest task is just switching out the values of the registers. This would be a “procedural” cost. However, as a CPU executes, it builds up state in various caches, which must be refilled again when switching tasks. This cost, much harder to quantify, would be a “cognitive” cost.

For humans, a “procedural” cost of switching tasks involves the physical setup of a task (opening a document on the computer, setting a brushes for painting, etc), whereas the “cognitive” cost is due to switching out the working memory maintained while working on a task (e.g. what sentence to write next, in which region to paint). The human task-switching literature has focused primarily on quantifying the cognitive cost of task switching. However, this cost may in fact be irrelevant if the procedural cost is high enough. Interestingly, for operating systems, it may also be negligible for simple tasks where both tasks fit in cache. It’s possible that there are tasks simple enough that they incur almost no cognitive cost for humans as well.

1.2 Time to completion: often unknown

Something that I find really interesting in the OS literature, which is completely glossed over in Algorithms to Live By, is that most of modern scheduling algorithms don’t make any assumptions about the length of each task when scheduling them. People are notoriously bad at estimating tasks4, so having a system which can process multiple tasks of arbitrary lengths robustly seems rather interesting. In both of the modern schedulers described below, the scheduler is designed to handle a mix of long and short running tasks with minimal sacrifices on the run time of either.

1.3 Turnaround time vs response time: choose one

A natural metric to optimize for completing tasks is the “turnaround time”, defined as the time from task arrival to task completion. However, engineers of interactive systems quickly realized that considering only turnaround time leads to laggy and unresponsive interfaces. This is because, optimizing for turnaround time, the system would just run one task at time, for a long time. Thus, from the perspective of the user, their task would usually freeze up until all the other shorter tasks completed.

The solution is to measure and optimize the response time, the time from the task arrival to the first task run. I find this interesting, as in our modern social networks we are often incentivized to minimize response time, rather than turnaround time, which naturally leads to us performing tasks in round-robin style. Rather than holding turnaround time as the best metric and completely discounting round-robin scheduling, as so many “productivity gurus” often do, it can be helpful to think about the balance between response time and turnaround time, and what you might be trading off when picking one to optimize.

1.4 Input/output: blocks tasks

Another consideration when scheduling tasks is the waiting time for input/output. For instance, when the CPU is reading from or writing to a hard drive, it must wait for the hard drive to respond before continuing to execute the task, as hard drives are orders of magnitude slower than CPUs. But it could be executing other tasks during this time!

A similar principle applies for human tasks. When running the laundry, for instance, it’s more efficient to not wait for the washer to finish before starting another task. Similarly, when waiting for a reply to a message or waiting for water to boil, it’s more efficient be doing something else. You can think of delegating tasks to people or machines in this way as well. Still, how can you schedule tasks most efficiently while keeping this in mind? The modern algorithms below handle these issues naturally.

2 Modern operating system schedulers

2.1 Multi-level feedback queue

The multi-level feedback queue strikes a balance between turnaround time (how long it takes you to complete a task) and response time (how long before you start on the task), while making few assumptions about the run time of the tasks. How does it do this?

Essentially, it schedules tasks according to the following rules5:

  1. If Priority(A) > Priority(B), A runs and B doesn’t.
  2. If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice (quantum length) of the given queue.
  3. When a job enters the system, it is placed at the highest priority (the topmost queue).
  4. Once a job uses up its time allotment at a given level, its priority is reduced (i.e., it moves down one queue).
  5. After some time period S, move all the jobs in the system to the topmost queue

This system gives a higher priority to incoming jobs. They’ll run first, maximizing response time. If they’re short, they’ll also finish quickly. However, if they turn out to be longer, they’ll get moved into a lower queue, which will only run after every other job. In order to continue running the longer jobs if there are too many interactive jobs, all the priorities are reset periodically. In some variants, the lower priority queues have longer time slices, as the non-interactive jobs are often CPU bound and this reduces context switching costs.

Pros:

  • automatic adjustment of priorities based on observed runtime
  • good tradeoff between response time and turnaround time

Cons:

  • no way to specify which jobs have higher priority permanently
  • priority reset (rule 5) feels like it would be tricky to implement for human scheduling
  • need a system to manage task priorities

2.2 Fair-share scheduler

Rather optimizing turnaround time and response time, you could try to spend the same amount of time for each task. This is the idea behind the “fair-share scheduler”, used (with some variations) in the Linux kernel. There are two main ways that people have implemented a fair-share system. In the first, you would allocate “tickets” to each task based on its priority, and then draw a ticket at random for each slot of time. In the second (and the way Linux does it), keep track of how much time you’ve spent on each task (a “virtual runtime”) and run the task you’ve spent the least time on at each slot.6

Pros:

  • ticket system is simple to implement
  • easy to tune the priority of tasks

Cons:

  • tasks which mostly wait on input do not get their fair share
  • must tune priorities manually
  • the second approach (based on “virtual runtime”) seems harder to implement in practice

3 Scheduling for humans

Between the two modern scheduling systems, the fair-share scheduling system seems like the easiest to adopt. Indeed, the author and artist Viviane Schwarz uses a fair-share scheduling system for her tasks, to great effect:

One of my most important work tools is a bingo wheel which I throw wooden balls in labelled with the projects I need to work on. […] I spin out a project, set a timer and work on it for half an hour or an hour to take it forward, then I spin again until it’s time to stop working. It sounds quite ridiculous but it beats every other system I’ve ever tried for productivity; you just have to make sure the right balls are in the cage, throw in more if a deadline is approaching or take some out if something gets less urgent.

I’m intrigued by the automatic priority management of the multilevel feedback queue as well, although using it would require logging time spent on each task. I haven’t found anyone doing this exactly, but there is some precedent in thinking of todo lists as priority queues.

Either way, I couldn’t find anything to manage todo lists in this way. It would be a useful application if someone does develop it!

Footnotes:

1

Based on the book, I also made a couple of small changes to my life, notably buying a stand for my clothes and making more heavy use of the “recently modified” heuristic when sorting things (or at least, feeling more comfortable with it as reasonably optimal). Still, the scheduling parallel is what interested me the most in the end.

2

The book covers scheduling tradeoffs at a pretty high level, focusing primarily on the earliest deadline first (EDF) and shortest job next (SJN) algorithms, and has brief discussions on priority inversion and context switching. The book’s focus is understandable given the its audience and space constraints, but the recommendations for practical time management feel somewhat shallow (e.g. beware of context switching, check prerequisites for tasks).

3

In the OS literature, “procedural” and “cognitive” costs are generally referred to as “direct” and “indirect” costs.

4

For instance, the majority of students underestimated how long it would take to finish a paper by about 50% when optimistic, and even by 12% when asked to make a pessimistic estimate. (Buehler, Griffin, Ross, 1994)

5

Lifted from Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau.

6

To continue spending time on long running tasks, you need to pretend that new tasks have been running for the minimum time you’ve spent on any current task.