Browse Prior Art Database

Semaphore that can avoid deadlock within thread

IP.com Disclosure Number: IPCOM000177258D
Original Publication Date: 2008-Dec-08
Included in the Prior Art Database: 2008-Dec-08
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Abstract

Semaphores are used very broadly in software. In a complex system, it will take a lot of time and effort to aviod the dead-locks within threads. This publication proposes a method to avoid within thread semaphores.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 3

Semaphore that can avoid deadlock within thread

Semaphores are used very broadly in software. A critical problem is the deadlock. Deadlock in a thread is a kind of hard problem. For example, there's a semaphore P1. And there're three functions of F1,F2,F3. All of these three functions need to acquire this semaphore for work. And these functions may invoke each other. The pseudo code could be as follows:

Semaphore P1;

Function F1{

Get

_semaphore(P1);

do work; Release

_semaphore(P1);

}

Function F2{

Get

_semaphore(P1)

do work;
invoke Function F1; do work;

Release

_semaphore(P1);

}

The execution flow is described by the following figure:

Time

F2: get semaphore

Semaphore: semaphore count-1 to 0 Return success.

F2: invoke F1

F2:F1:get semaphore

Semaphore: count is zero. Can't grant

F2:F1: wait …

Dead Lock

Figure 1. With-in thread dead lock

The deadlock will happen. Function F1

will be blocked by Get

_semaphore(P1) for the reason that it

has been acquired by F2 and will never be released. And we can't remove the semaphore operation in function F1 because F1 may be invoked by some other functions which may not acquire semaphore P1 before the invocation.

The known solutions are to add parameters to the functions. Use these parameters to indicate

whether the semaphore has been acquired. It's hard to deal with this kind of case especially in

complicated software that have lots of functions and semaphores.

This invention is to avoid this kind of in-thread dead lock caused by semaphores.

1

Page 2 of 3

The Robot worker will be taken as an example to show the usage of this mechanism.

As a product, robot work manufacture may offer a set of API for customers to develop control software. This is so-called development kit. The kit may contain some functions of basic operations like step

_forward(), step

_backward(), turn

_around(), lit

_left

_hand(), lit

_right

_hand() and so on. And

also it will offer some add-on APIs for assisting the development like waltz()

which would invoke lots of

basic operation functions to make robot have a dance.

All of the APIs will be packaged as a development kit for shipping. To ensure the correctness of the program, all of these APIs need to gain the semaphore of robot motor. As a dev kit, it would never ask customers to gain those semaphores instead because that's dangerous and may cause serious problems to the hardware.

In this example, the same problem as what F1 and F2 have arises. Basic operations like step

_forward() are in the role of F1. It would be called

by add-on APIs like waltz()

which is in the role

of F2.

The current solution may be to add a new parameter (e.g. got

_semaphore, indicating whether the

semaphore has been acquired already.) to those functions. If the value of got

_semaphore is TRUE,

the invoked function would not try to gain the semaphore again. The problem is that it will bring the code into chaos when the system grows and has a lot of semaphores....