Lock

Basics 
Locks are synchronization abstraction specifically meant for mutual exclusion only.
Usually a lock is  associated with a region of data or code sequence  that multiple threads strife to access. At most one thread may own the lock.
When thread A attempts to acquire a lock held by thread B, A must wait, or block, until B releases it. If B never releases the lock, A waits forever.
So, the lock allows threads to perform complicated atomic operations on a specific region of code and data.          
Here are a few terms to help better understand the theory behind mutual exclusion:

Reentrancy - defines lock’s ability to be acquired by a thread that already has acquired it without  releasing it. In other words if a thread tries to acquire a lock that it already holds, the request succeeds. Reentrancy means that locks are acquired on a per-thread rather than per-invocation basis.
 
Freedom from deadlock - if some thread  tries to acquire the lock then some thread  will succeed in acquiring the lock. If thread A tries to acquire the lock but never succeeds then other thread B must be holding the lock forever.
 
Freedom from starvation - every thread that attempts to acquire the lock eventually succeeds - if a thread enters the lock by acquiring it, the same thread MUST release it.

ACORN kernel implementation of a lock is based on the so called Ticket algorithm. It is the same algorithm - slightly modified though- used in the extended event system of ACORN micro kernel.
The algorithm satisfies the FIFO requirement  - each thread acquires the lock in the order it has requested it - which in terms of synchronization is called - fairness.
A thread wishing to enter its protected section takes the next available ticket and waits until its ticket becomes valid, at which point it can safely enter its critical section . When it exits ,it discards its ticket and validates the next invalid ticket in order even if this ticket has not been taken yet.

Memory structure
The memory  a lock structure occupies is 2 bytes of RAM (fig 1). It is fragmented in 2 major byte fields.

 

{v} - a byte used to define the next valid ticked.
{t} - a ticket reserved by the next thread to acquire the lock.
It is obvious that 256 different threads could request lock acquisition. I doubt anyone would want to use that many threads in an 8 bit MCU ….

 

Implementation

The ACORN kernel lock was designed to be small - both in code and memory footprint Unfortunalty ATMEL 8 bit MCU assembler does not have atomic Read-Modify-Write instructions so we will have to use interrupt disable/enable instructions in order to secure code execution automicity. The rule however,  is to keep the code without interrupts as short as possible!!!! 

Portion {1;6} marks the initialization region of the lock acquisition - it must be atomic, that is why interrupts are disabled. It reserves a free ticket number {t} and calculates the next available one. It is a bounded number - up to 256 numbers could be reserved. It overflows to zero when the upper limit is reached.
Portion {7;11} marks the spinning part - there the task waits until its ticket becomes “valid”. Right now the task yields its time quantum but i am considering task suspension in future releases.Task suspension will reduce the CPU overhead in the spinning part of each lock but the implementation will require more RAM usage.
Portion {12;13} marks the end of the protected region and validates the next ticket by incrementing {v}.This portion operates on {v} byte in RAM and is the only place where {v} is written by the task that posses the lock.What we have is - single writer, multiple readers in the spinning part - no need to disable interrupts.The less we disable interrupts the better the design of the system.

The lock implementation in ACORN micro kernel could be found in a separate file Lock.inc
Basic Lock macros:

• _LOCK_ACQUIRE - called by the task that wants to enter the lock. Marks the beginning of the protected region.
• _LOCK_RELEASE - called by the task that has acquired the lock in order to release it Marks the end of the protected region.

It could be used in each version of the kernel, provided that there are 2 bytes of extra RAM for it.
The lock will be available in the next kernel release(2.1 and higher).