LOCKS: SHARING AN OBJECT BETWEEN THREADS

When you hand an object to several threads, they all hold the same object. That is exactly what you want when they work on one shared result. But a line like total = total + 1 is really three steps: read total, add one, write it back. If two threads read the same old value at the same moment, both write back the same new one, and one of the additions is lost.

Satellite’s answer is a lock that you turn on yourself.

Turning the lock on

Every object made from a spacesuit, and every file, carries a lock, and it starts off. While it is off, nothing is ever locked and threads share the object freely, at full speed.

obj.lock() turns the lock on. That does not lock anything by itself. Instead, from then on, each statement inside the object’s own capsules takes the lock for just that one statement:

• A statement that writes the object holds the lock alone. Writing means assigning one of its fields (total = total + 1), calling a method on a field (items.append(x)), or calling a capsule.
• A statement that only reads the object shares the lock with other readers. It waits only while a write is happening, or while a writer is waiting its turn, so reads can never starve a write.
• An if, while or for holds the lock for its condition only, never for its whole body.

obj.unlock() turns the lock off again.

Here four threads each add 1 to one shared counter a thousand times. With the lock on, every addition counts:

satellite.include(satellite)

satellite.spacesuit counter()
{
    satellite.protected
    {
        satellite.variable.number total = 0
    }
    satellite.public
    {
        satellite.capsule call_add()
        {
            total = total + 1
        }
        satellite.capsule call_total()
        {
            satellite.return(total)
        }
    }
}

satellite.capsule count_to_a_thousand(counter c)
{
    satellite.statement.for(satellite.variable.number i = 1; i <= 1000; i + 1)
    {
        c.call_add()
    }
}

satellite.capsule satellite.main()
{
    counter shared()
    shared.lock()
    satellite.variable.thread a = satellite.thread.new(count_to_a_thousand(shared))
    satellite.variable.thread b = satellite.thread.new(count_to_a_thousand(shared))
    satellite.variable.thread c = satellite.thread.new(count_to_a_thousand(shared))
    satellite.variable.thread d = satellite.thread.new(count_to_a_thousand(shared))
    a.start()
    b.start()
    c.start()
    d.start()
    a.join()
    b.join()
    c.join()
    d.join()
    shared.unlock()
    satellite.console.display(shared.call_total())
    satellite.return(satellite)
}

4000

Take the shared.lock() line out and the same program comes up short, by a different amount each run: around 2,500 is typical. With a list field instead of a number, two threads changing it unlocked can even crash satl. If threads share an object and more than one of them changes it, lock it.

Locking a file

A file’s lock works the same way. With it on, each method called on the file holds the lock for that call, and reading a line with f[n] is a read. Two threads can then append to one file, and no line is lost or torn:

satellite.include(satellite)

satellite.capsule write_lines(satellite.variable.file log, satellite.variable.string who)
{
    satellite.statement.for(satellite.variable.number i = 1; i <= 50; i + 1)
    {
        log.append(who + " " + i.to_string())
    }
}

satellite.capsule satellite.main()
{
    satellite.variable.file log = satellite.file.new("log.txt")
    log.lock()
    satellite.variable.thread left = satellite.thread.new(write_lines(log, "left"))
    satellite.variable.thread right = satellite.thread.new(write_lines(log, "right"))
    left.start()
    right.start()
    left.join()
    right.join()
    satellite.console.display(log.size)
    satellite.console.display(log.contains("left 50"))
    satellite.console.display(log.contains("right 50"))
    satellite.return(satellite)
}

100
true
true

A join lets go while it waits

A statement holding a lock should not sit on it while it waits for something slow, and waiting for a thread is the slowest thing there is. So join() and wait() give back every lock their line holds, wait for the thread, then take the locks back before the line finishes. That lets a capsule of a locked object start a helper thread on the same object and wait for its answer:

satellite.include(satellite)

satellite.spacesuit counter()
{
    satellite.protected
    {
        satellite.variable.number total = 0
    }
    satellite.public
    {
        satellite.capsule call_next()
        {
            satellite.return(total + 1)
        }
        satellite.capsule call_step()
        {
            satellite.variable.thread helper = satellite.thread.new(call_next())
            helper.start()
            total = helper.join()
        }
        satellite.capsule call_total()
        {
            satellite.return(total)
        }
    }
}

satellite.capsule satellite.main()
{
    counter c()
    c.lock()
    c.call_step()
    c.call_step()
    c.call_step()
    satellite.console.display(c.call_total())
    satellite.return(satellite)
}

3

The helper reads total while call_step is waiting for it, which works only because the join let go. The one thing to keep in mind: in a line like total = total + w.join(), another thread may change total between the moment the line reads it and the moment it writes it, because the line does not hold the lock during the join.

A circle that would never end

Some waits can never finish. Here two jars are both locked. One thread fills the left jar by asking the right jar for a scoop, while the other fills the right jar from the left. Each line that changes a jar holds that jar’s lock while it asks the other jar, so each thread ends up holding one lock and waiting for the other’s. Neither can ever go on.

Satellite does not freeze. Before any thread goes to sleep, it follows the chain of who is waiting for whom, and if the chain comes back to itself, the line stops with S728 WAIT_NEVER_ENDS:

satellite.include(satellite)

satellite.spacesuit jar()
{
    satellite.protected
    {
        satellite.variable.number beans = 0
        satellite.variable.number scoop = 1
    }
    satellite.public
    {
        satellite.capsule call_fill_from(jar other)
        {
            satellite.statement.for(satellite.variable.number i = 1; i <= 2000; i + 1)
            {
                beans = beans + other.call_scoop()
            }
        }
        satellite.capsule call_scoop()
        {
            satellite.return(scoop)
        }
    }
}

satellite.capsule satellite.main()
{
    jar left()
    jar right()
    left.lock()
    right.lock()
    satellite.variable.thread x = satellite.thread.new(left.call_fill_from(right))
    satellite.variable.thread y = satellite.thread.new(right.call_fill_from(left))
    x.start()
    y.start()
    x.join()
    y.join()
    satellite.console.display("never reached")
    satellite.return(satellite)
}

--------------------------------------------------------------------------------
SATELLITE CRITICAL ERROR REPORT
--------------------------------------------------------------------------------
S728: WAIT_NEVER_ENDS
satl(run): this line needs its object's lock, and a thread holding it is waiting
-- through locks and joins -- for this one

directory: jars.satl:21
syntax: satellite.return(scoop)
        /\

this line would wait forever: the object's lock it needs is held by a thread
that is itself waiting -- through locks and joins -- for this one. Two threads
each waiting for the other never end, so satellite stops this line instead of
the program freezing (003's S1407 and S1408). A line that holds an object's lock
-- writing it, or reading it -- should not wait for a thread that needs the same
object's lock.
machine code 63 wait_never_ends -- satl exits with this.

--------------------------------------------------------------------------------

The cure is to stop one locked object’s line from waiting on another. Give the jar a plain call_add(more), and do the moving in an ordinary capsule outside the spacesuit: into.call_add(from.call_scoop()). Each jar’s lock is then held only by a line of its own that asks nothing of the other jar, so no circle can form, and the two threads finish with all 4,000 beans.

Where next

Every thread and lock word is in the FULL REFERENCE. Start with THREADS if you have not already, and see SPACESUITS for the objects being shared.