Thread starvation while locking in a loop in Python

Question

I have an application which is acquiring a lock in a loop in one thread to perform some task. There's also a second thread that also wants to acquire the lock from time to time. The problem is, this second thread barely even gets the chance to perform it's work, as the first one almost always locks first. I hope the following code will clarify what I'm trying to say:

import time
from threading import Lock, Thread

lock = Lock()


def loop():
    while True:
        with lock:
            time.sleep(0.1)

thread = Thread(target=loop)
thread.start()

before = time.time()
lock.acquire()
print('Took {}'.format(time.time() - before))

If the application gets to print you'll notice that it needed way more than just 0.1s. But sometimes it also happens that it just waits indefinitely. I've tested this both in Python 2.7.11 and Python 3.4.3 on Debian Linux 8 and it works identically.

This behaviour is counter-intuitive for me. After all when the lock is released in loop, the lock.acquire was already waiting for its release and it should immediately acquire the lock. But instead it looks like the loop gets to acquire the lock first, even though it wasn't waiting for its release at all at the release moment.

The solution I've found is to sleep between each loop iteration in unlocked state, but that doesn't strike me as an elegant solution, neither does it explain to me what's happening.

What am I missing?

Answer 1

It seems that this is due to OS thread scheduling. My guess is that either OS gives very high priority to cpu intensive threads (whatever that means) or chosing a next thread to acquire the lock (done by the OS) takes more time than actually acquiring the lock by the second thread. Either way not much can be deduced without knowing the internals of the OS.

But it's not GIL since this code:

#include <mutex>
#include <iostream>
#include <chrono>
#include <thread>

std::mutex mutex;

void my_thread() {
    int counter = 100;
    while (counter--) {
        std::lock_guard<std::mutex> lg(mutex);
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
        std::cout << "." << std::flush;
    }
}

int main (int argc, char *argv[]) {
    std::thread t1(my_thread);
    auto start = std::chrono::system_clock::now();
    // added sleep to ensure that the other thread locks lock first
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));
    {
        std::lock_guard<std::mutex> lg(mutex);
        auto end = std::chrono::system_clock::now();
        auto diff = end - start;
        std::cout << "Took me " << diff.count() << std::endl;
    }
    t1.join();
    return 0;
};

which is just a C++11 version of your code gives exactly the same result (tested on Ubuntu 16.04).