Semaphores, or how to resolve access to resources in DBMS Caché

  • Tutorial
Often with multi-user or parallel access to data, a situation arises when it is necessary to block / give access to a variable or a piece of memory to several processes simultaneously. This problem is solved with the help of mutexes, semaphores, monitors, etc. In this post, we will examine how one of the methods for providing data sharing - a semaphore - is implemented in Intersystems Caché DBMS.


Semaphores are a flexible and convenient means for synchronizing and mutually excluding processes, accounting for resources. Hidden semaphores are also used in operating systems as the basis for other means of process interaction.

A semaphore is a non-negative integer variable over which two types of operations are possible:
  • A P-operation on a semaphore is an attempt to decrement the value of the semaphore by 1. If the semaphore value was greater than 0 before the P-operation, then the P-operation is performed without delay. If the semaphore value was 0 before executing the P-operation, then the process performing the P-operation is put into a wait state until the semaphore value becomes large 0.
  • A V-operation on a semaphore represents an increment of the semaphore value by 1. If there are processes delayed by the P-operation on this semaphore, one of these processes leaves the standby state and can perform its P-operation.

Semaphores come in two forms: binary (figure on the left) and general view, or counters (figure on the right). They differ in that in the first case the variable can take only two values: 0 and 1, and in the second - any non-negative integer. There are several uses for semaphores.

Mutual exception on semaphore
To implement mutual exclusion, for example, to prevent the possibility of two or more processes simultaneously changing common data, a binary semaphore S. S) (at the beginning of the section) and V (S) (at the end of the section). The process entering the critical section performs the operation P (S) and transfers the semaphore to 0. If another process is already in the critical section, then the semaphore value is already 0, then the second process that wants to enter the critical section is blocked in its P-operation until the process, which is now in the critical section, exits from it by performing the operation V (S) at the output.

Semaphore synchronization
To ensure synchronization, a binary semaphore S is created with an initial value of 0. A value of 0 means that the event has not yet occurred. The process signaling the occurrence of the event performs operation V (S), which sets the semaphore to 1. The process that waits for the event to occur performs operation P (S). If at this point the event has already occurred, the waiting process continues to be executed, if the event has not yet occurred, the process is put into a waiting state until the signaling process executes V (S).

If several processes are waiting for the same event, the process that has successfully completed the operation P (S) must execute V (S) after it in order to duplicate the signal about the event for the next waiting process.

Semaphore - resource counter
If we have N units of some resource, then to control its distribution, a common semaphore S is created with the initial value N. The allocation of the resource is accompanied by the operation P (S), the release by the operation V (S). The semaphore value thus reflects the number of free units of a resource. If the semaphore value = 0, that is, there are no more free units left, then the next process requesting the resource unit will be pending in operation P (S) until any of the processes using the resource free the resource unit by doing this V (S).

All these options can be implemented in Caché, using the % SYSTEM.Semaphore class that appeared in version 2014.2 , which encapsulates a 64-bit non-negative integer and provides methods for changing its value to all running processes. Consider the use of a semaphore counter in a model example (third use case).



Suppose that 10 slots have been allocated to the university to access an international database of scientific articles. Thus, we have a resource that we need to share among all students who want to access. Each student has his own username / password for access to the database, but only 10 people can work from the university at the same time. Each time a student logs into the database, it is necessary to reduce by 1 the number of slots available for use. Accordingly, when it leaves the database, it is necessary to return this 1 slot to the shared pool.

In order to check whether to give the student access or make him wait, we use a semaphore counter, whose initial value is 10. In order to see how the process of issuing access occurs, we use logging. The main class will initialize the variables and track the students' work process. Another class will inherit from% SYSTEM.Semaphore and implement a semaphore. A separate class is distinguished for various utilities. And the last two classes will simulate the student entering and leaving the database. Since the server "knows" the name of the user who logs into and leaves the system, to simulate this "knowledge" we will create a separate global that will store information about active users ( ^ LoggedUsers) We will write down the logins of the students who have entered it and from it we will take random names to exit the system.

Let's start with the Main class in which:
  1. create a semaphore
  2. set its initial value (equal to 10, which corresponds to 10 free slots for access to the database of scientific articles),
  3. stop the process and delete the semaphore,
  4. display the log.

SemaphoreSample.Main
Class SemaphoreSample.Main Extends %RegisteredObject [ ProcedureBlock ]
{
/// драйвер для примера
ClassMethod Run()
{
    // инициализируем глобалы для логирования
    Do ##class(SemaphoreSample.Util).InitLog()
    Do ##class(SemaphoreSample.Util).InitUsers()
    Set msg = "Старт процесса"
    Do ..Log(msg)
    // создаем и инициализируем семафор
    Set inventory = ##class(SemaphoreSample.Counter).%New()
    If ('($ISOBJECT(inventory))) {
        Set msg = "Метод класса SemaphoreSample.Counter %New() не отработал"
        Do ..Log(msg)
        Quit
    }
    // устанавливаем начальное значение семафора
    if 'inventory.Init(10) {
	    Set msg = "Возникла проблема при инициализации семафора"
    	Do ..Log(msg)
	    Quit
	    }
    // ожидаем окончания процесса
    Set msg = "Нажмите любую клавишу для прекращения доступа..."
    Do ..Log(msg)
    Read *x
    //удаляем семафор
    Set msg = "Семафор удален со статусом " _ inventory.Delete()
    Do ..Log(msg)
    Set msg = " Окончание процесса"
    Do ..Log(msg)
    do ##class(SemaphoreSample.Util).ShowLog()
    Quit
}
/// Вызов утилиты для записи лога
ClassMethod Log(msg As %String) [ Private ]
{
    Do ##class(SemaphoreSample.Util).Logger($Horolog, "Main", msg)
    Quit
}
}

The next class we will create is a class with various utilities. They will be needed for the test application to work. It will have class methods responsible for:
  1. preparing the global logging for work ( ^ SemaphoreLog ),
  2. write logs to the global,
  3. log display,
  4. registration in a global of names of the working users ( ^ LoggedUsers ),
  5. random name selection from working users,
  6. Removing a name from the global working user index.

SemaphoreSample.Util
Class SemaphoreSample.Util Extends %RegisteredObject [ ProcedureBlock ]
{
/// инициализация лога
ClassMethod InitLog()
{
    // удаляем предыдущие записи из лога
    Kill ^SemaphoreLog
    Set ^SemaphoreLog = 0
    Quit
}
/// инициализация лога
ClassMethod InitUsers()
{
	//на всякий случай удаляем всех пользователей из глобала
        if $data(^LoggedUsers) '= 0
	{
		Kill ^LoggedUsers    	
	}
	Set ^LoggedUsers = 0
}
/// непосредственно запись лога в глобал
ClassMethod Logger(time As %DateTime, sender As %String, msg As %String)
{
    Set inx = $INCREMENT(^SemaphoreLog)
    Set ^SemaphoreLog(inx, 0) = time
    Set ^SemaphoreLog(inx, 1) = sender
    Set ^SemaphoreLog(inx, 2) = msg
    Write "(", ^SemaphoreLog, ") ", msg_" в "_$ztime($PIECE(time,",",2), 1), !
    Quit
}
/// вывод сообщений на экран
ClassMethod ShowLog()
{
    Set msgcnt = $GET(^SemaphoreLog, 0)
    Write "Лог сообщений: количество записей = ", msgcnt, !, !
    Write "#", ?5, "Время", ?12, "Отправитель", ?25, "Сообщение", !
    For i = 1 : 1 : msgcnt {
        Set time = ^SemaphoreLog(i, 0)
        Set sender = ^SemaphoreLog(i, 1)
        Set msg = ^SemaphoreLog(i, 2)
        Write i, ")", ?5, $ztime($PIECE(time,",",2), 1), ?15, sender, ":", ?35, msg, !
    }
    Quit
}
/// добавление имени пользователя в список залогиненых
ClassMethod AddUser(Name As %String)
{   
	Set inx = $INCREMENT(^LoggedUsers)
	set ^LoggedUsers(inx) = Name
}
/// удаление имени пользователя из списка залогиненных
ClassMethod DeleteUser(inx As %Integer)
{	
	kill ^LoggedUsers(inx)
}
/// выбор имени пользователя из списка залогиненных пользователей
ClassMethod ChooseUser(ByRef Name As %String) As %Integer
{	
	// если все пользователи "вышли", то возвращаем признак необходимости подождать
        if $data(^LoggedUsers) = 1
	{
	   Set Name = ""
	   Quit -1
	} else
	{
		Set Temp = ""
		Set Numb = $Random(10)+5
   		For i = 1 : 1: Numb {
      		   Set Temp = $Order(^LoggedUsers(Temp))     
                   // для того, чтобы зациклить проход по одному уровню глобала
                   // по окончанию одного прохода перемещаем указатель в начало 
      		   if (Temp = "")      
      		   {
        		set Temp = $Order(^LoggedUsers(""))
      		   }
   		}   
   		set Name = ^LoggedUsers(Temp)
   		Quit Temp
       }
}
}

Next is the class with the implementation of the semaphore itself. We inherit it from the system class% SYSTEM.Semaphore and add methods that implement the call
  1. a method that returns a unique semaphore name,
  2. a method of recording events in the log,
  3. callback methods for creating and destroying a semaphore (we simply note the fact of creation / destruction in them),
  4. a method for creating and initializing a semaphore.

SemaphoreSample.Counter
Class SemaphoreSample.Counter Extends %SYSTEM.Semaphore
{
/// Каждый счетчик должен имет свое уникальное имя
ClassMethod Name() As %String
{
    Quit "Counter"
}
/// Вызов утилиты для записи лога
Method Log(Msg As %String) [ Private ]
{
    Do ##class(SemaphoreSample.Util).Logger($Horolog, ..Name(), Msg)
    Quit
}
/// Callback метод при создании нового объекта
Method %OnNew() As %Status
{
    Set msg = "Создание нового семафора"
    Do ..Log(msg)
    Quit $$$OK
}
/// Создание и инициализация семафора
Method Init(initvalue = 0) As %Status
{
    Try {
        If (..Create(..Name(), initvalue)) {
            Set msg = "Создан: """ _ ..Name() 
                    _ """; Начальное значение = " _ initvalue
            Do ..Log(msg)
            Return 1
        }
        Else {
        Set msg = "Возникла проблема при создании семафора с именем = """ _ ..Name() _ """"
        Do ..Log(msg)
        Return 0
        }
    } Catch errobj {
        Set msg = "Возникла ошибка при создании семафора: "_errobj.Data
        Do ..Log(msg)
        Return 0
    }
}
/// Callback метод при закрытии объекта
Method %OnClose() As %Status [ Private ]
{
    Set msg = "Закрываем семафор"
    Do ..Log(msg)
    Quit $$$OK
}
}

Note on naming semaphores
Semaphores are defined by the name that is passed to the system when the semaphore is created. And this name must meet the requirements for local / global variables. Naturally, the name of the semaphore must be unique. Typically, a semaphore is stored in the database instance in which it was created, and it is visible to all other processes of this instance. If the semaphore name complies with the rules for setting global variable names, then the semaphore becomes available to all running processes, including ECP.

And the last two classes imitate users entering and leaving the system. To simplify the example, suppose there are exactly 25 of them. Of course, it would be possible to start the process and create a new user until some key is pressed on the keyboard, but I decided to make it easier and use the final loop. In both classes, we first connect to the existing semaphore and try to decrease (log in) / increase (log out) the counter. We assume that the student will wait in his turn for an infinitely long time (well, he really needs to get access), so we use the Decrement function, which allows us to set an endless waiting period. Otherwise, we can set a specific period of time before the timeout in tenths of a second. To prevent all users from breaking into the system at the same time, we put some arbitrary pause before the next login.

SemaphoreSample.LogIn
Class SemaphoreSample.LogIn Extends %RegisteredObject [ ProcedureBlock ]
{
/// Моделирование входа пользователей в систему
ClassMethod Run() As %Status
{
    //открываем семафор, отвечающий за доступ к БД
    Set cell = ##class(SemaphoreSample.Counter).%New()
    Do cell.Open(##class(SemaphoreSample.Counter).Name())
    // начинаем "логиниться" в систему
    // для примера берем 25 разных студентов
    For deccnt = 1 : 1 : 25 {        
        // генерируем случайный логин
   	Set Name = ##class(%Library.PopulateUtils).LastName()
        try
        {
	       Set result =  cell.Decrement(1, -1)  
        } catch 
        {
	       Set msg = "Доступ прекращен"
	       Do ..Logger(##class(SemaphoreSample.Counter).Name(), msg)
	       Return   
	    }
        do ##class(SemaphoreSample.Util).AddUser(Name)      
        Set msg = Name _ " зашел в систему"
        Do ..Logger(Name, msg)
        Set waitsec = $RANDOM(10) + 7
        Hang waitsec
    }
    Set msg = "Желающие зайти в систему закончились"
    Do ..Logger(##class(SemaphoreSample.Counter).Name(), msg)
    Quit $$$OK
}
/// Вызов утилиты для записи лога
ClassMethod Logger(id As %String, msg As %String) [ Private ]
{
    Do ##class(SemaphoreSample.Util).Logger($Horolog, id, msg)
    Quit
}
}

When disconnecting from the server in our model, you need to check if there are any users there at all. Therefore, first we look at the contents of the global with users ( ^ LoggedUsers ) and if it is empty, then we wait for some arbitrary time and once again check if someone managed to log into the system.

SemaphoreSample.LogOut
Class SemaphoreSample.LogOut Extends %RegisteredObject [ ProcedureBlock ]
{
/// Моделирование выхода пользователей из системы
ClassMethod Run() As %Status
{
    Set cell = ##class(SemaphoreSample.Counter).%New()
    Do cell.Open(##class(SemaphoreSample.Counter).Name())
    // выходим из системы
    For addcnt = 1 : 1 : 25 {
        Set inx = ##class(SemaphoreSample.Util).ChooseUser(.Name)
        while inx = -1
        {
	        Set waitsec = $RANDOM(10) + 1
        	Hang waitsec
        	Set inx = ##class(SemaphoreSample.Util).ChooseUser(.Name)
        }
        try 
        {
        	Do cell.Increment(1)
        } catch 
        {
	        Set msg = "Доступ прекращен"
	        Do ..Logger(##class(SemaphoreSample.Counter).Name(), msg)
	        Return   
	    }
        Set waitsec = $RANDOM(15) + 2
        Hang waitsec
    }
    Set msg = "Все пользователи вышли из системы"
    Do ..Logger(##class(SemaphoreSample.Counter).Name(), msg)
    Quit $$$OK
}
/// Вызов утилиты для записи лога
ClassMethod Logger(id As %String, msg As %String) [ Private ]
{
    Do ##class(SemaphoreSample.Util).Logger($Horolog, id, msg)
    Quit
}
}

Now the project is ready. We compile it and you can run and watch what happened. We will launch in three different windows of the Terminal.

In the first window, if necessary, go to the desired namespace (I did a project in the USER namespace)
zn "USER"

and call the method to start our “server” from the Main class :
do ##class(SemaphoreSample.Main).Run()

In the second window, we call the Run method from the LogIn class , which will generate users who log into the system:
do ##class(SemaphoreSample.LogIn).Run()

And in the last window, we call the Run method from the LogOut class , which will generate users who log out of the system:
do ##class(SemaphoreSample.LogOut).Run()

After everyone went in and out, we have the following results in the windows:
The first window will be a log
(1) Start of the process at 21:50:44
(2) Creation of a new semaphore at 21:50:44
(3) Created: “Counter”; Initial value = 10 at 21:50:44
(4) Press any key to terminate access ... at 21:50:44
(61) The semaphore was deleted with status 1 at 22:00:16
(62) End of the process at 22:00: 16
Message log: number of entries = 62

# Time Sender Message
1) 21:50:44 Main: Start of the process
2) 21:50:44 Counter: Creating a new semaphore
3) 21:50:44 Counter: Created: “Counter”; Initial value = 10
4) 21:50:44 Main: Press any key to terminate access ...
5) 21:51:00 Counter: Create a new semaphore
6) 21:51:00 Zemaitis: Zemaitis logged in
7) 21:51:12 Goldman: Goldman logged
on 8) 21:51:24 Cooke: Cooke logged
on 9) 21:51:39 Kratzmann: Kratzmann logged
on 10) 21:51:47 Roentgen: Roentgen logged on in
11) 21:51:59 Xerxes: Xerxes entered into the system
12) 21:52:10 Houseman: Houseman entered into the system
13) 21:52:18 Wijnschenk: Wijnschenk entered into the system
14) 21:52:33 Orwell: Orwell came in
15) 21:52:49 Gomez: Gomez came in
16) 21:53:46 Counter: Creating a new semaphore
17) 21:53:46 Kratzmann: Kratzmann logged out
of 18) 21:53:46 Quilty : Quilty logged in
19) 21:54:00 Orwell: Orwell logged out
20) 21:54:00 Kelvin: Kelvin logged in
21) 21:54:11 Goldman: Goldman
logged off 22) 21:54:11 Nelson: Nelson logged
on 23) 21:54:23 Gomez: Gomez
logged off 24) 21:54:23 Ragon: Ragon logged on in
25) 21:54:30 Zemaitis: Zemaitis logged off
26) 21:54:31 Quilty: Quilty came in
27) 21:54:42 Nelson: Nelson was released from the system
28) 21:54:42 Williams: Williams entered into the system
29) 21:54:49 Houseman: Houseman released from the system
30) 21:54:52 Quilty: Quilty released from the system
31) 21:54:58 Macrakis: Macrakis entered into the system
32) 21:55:00 Xerxes: Xerxes
logged out 33) 21:55:02 Quilty: Quilty logged out
34) 21:55:04 Cooke: Cooke logged out
35) 21:55:08 Brown: Brown logged on
36) 21:55:14 Williams: Williams
logged off 37) 21:55:16 Yancik: Yancik logged on
38) 21:55:17 Kelvin: Kelvin logged off from the system
39) 21:55:26 Roentgen: Roentgen released from the system
40) 21:55:27 Jaynes: Jaynes entered into the system
41) 21:55:34 Jaynes: Jaynes released from the system
42) 21:55:34 Rogers: Rogers entered into the system
43) 21:55:47 Basile: Basile entered into the system
44) 21:55:50 Rogers: Rogers released from the system
45) 21:55:58 Yancik: Yancik released from the system
46) 21:56:02 Taylor: Taylor logged in
47) 21:56:09 Ahmed: Ahmed logged in
48) 21:56:11 Taylor: Taylor logged out
49) 21:56:15 Wijnschenk: Wijnschenk logged out
50) 21:56:23 Edwards: Edwards logged in
51) 21:56:29 Edwards: Edwards logged out
52) 21:56:32 Counter: Those who want to log in in run
53) 21:56:32 Counter: Closes semaphore
54) 21:56:42 Basile: Basile released from the system
55) 21:56:58 Macrakis: Macrakis released from the system
56) 21:57:11 Ahmed: Ahmed I came out of the system
57) 21:57:18 Ragon: Ragon logged off
58) 21:57:31 Brown: Brown came out of the system
59) 21:57:36 Counter: All users are logged out
of 60) 21:57:36 Counter: Close semaphore
61) 22:00:16 Main: Semaphore deleted with status 1
62) 22:00:16 Main: End of process
(63) Close the semaphore at 22:00:16

In the second window there will be a log
(5) Creating a new semaphore at 21:51:00
(6) Zemaitis logged on at 21:51:00
(7) Goldman logged on at 21:51:12
(8) Cooke logged on at 21:51: 24
(9) Kratzmann logged in at 21:51:39
(10) Roentgen logged in at 21:51:47
(11) Xerxes logged in at 21:51:59
(12) Houseman logged in at 21: 52:10
(13) Wijnschenk logged in at 21:52:18
(14) Orwell logged in at 21:52:33
(15) Gomez logged in at 21:52:49
(18) Quilty logged in 21:53:46
(20) Kelvin logged in at 21:54:00
(22) Nelson logged in at 21:54:11
(24) Ragon logged in at 21:54:23
(26) Quilty logged in system at 21:54:31
(28) Williams logged in at 21:54:42
(31) Macrakis logged in at 21:54:58
(35) Brown logged in at 21:55:08
(37) Yancik logged in at 21:55 : 16
(40) Jaynes logged in at 21:55:27
(42) Rogers logged in at 21:55:34
(43) Basile logged in at 21:55:47
(46) Taylor logged in at 21 : 56: 02
(47) Ahmed entered into the system at 21:56:09
(50) Edwards entered into the system at 21:56:23
(52) wishes to log into the system run in 21:56:32
(53) closes the semaphore 21:56:32

In the third window there will be a log
(16) Creating a new semaphore at 21:53:46
(17) Kratzmann logged off at 21:53:46
(19) Orwell logged off at 21:54:00
(21) Goldman logged off at 21:54: 11
(23) Gomez logged off at 21:54:23
(25) Zemaitis logged off at 21:54:30
(27) Nelson logged off at 21:54:42
(29) Houseman logged off at 21: 54:49
(30) Quilty logged off at 21:54:52
(32) Xerxes logged off at 21:55:00
(33) Quilty logged off at 21:55:02
(34) Cooke logged off 21:55:04
(36) Williams logged off at 21:55:14
(38) Kelvin logged off at 21:55:17
(39) Roentgen logged off at 21:55:26
(41) Jaynes logged off system at 21:55:34
(44) Rogers logged off at 21:55:50
(45) Yancik logged off at 21:55:58
(48) Taylor logged off at 21:56:11
(49) Wijnschenk logged off at 21:56 : 15
(51) Edwards logged off at 21:56:29
(54) Basile logged off at 21:56:42
(55) Macrakis logged off at 21:56:58
(56) Ahmed logged off at 21 : 57: 11
(57) Ragon logged out in 21:57:18
(58) Brown released from the system in 21:57:31
(59) All users are logged in 21:57:36
(60) closes the semaphore 21:57:36

Now take a closer look at what was happening. I deliberately waited until 10 allowed users “logged in” to show that the semaphore value cannot be less than 0. These are users above the red line in the figure. We see that there is a break almost a minute before the next user is allowed to log into the system. And then only after someone left. I specifically highlighted in bold users who log into the system, and those in italics that are crossed out in italics . Colors highlighted input / output pairs for each user.



As for me, an interesting picture came out.

Further methods used in Example Increment and Decrement To work with a semaphore, you can use the waiting list and methods of working with it:
  • AddToWaitMany - add semaphore operation to the list
  • RemoveFromWaitMany - remove an operation from the list
  • WaitMany - wait until all operations on the semaphore are completed

In this case, WaitMany in a loop fulfills all the tasks in the list and, after the operation is successful, calls the Callback WaitCompleted method , which the developer must implement independently. It is called when the semaphore allocated a nonzero value for the operation or the wait timed out. The number by which the counter has been reduced is returned to the argument of this method (0 in the case of a timeout). After this method has worked, the semaphore is deleted from the WaitMany task list and then the transition to the next task is carried out.

More information on semaphores in Caché can be found in the documentation (you can also see another example of working with a semaphore there) and in the class description.Since at the time of writing, Caché 2014.2 is available only on the field test portal for support users and participants of the InterSystems University academic program , links will be added as soon as the release is released.

The project is on GitHub .

If there are comments, comments or suggestions - you are welcome. Thank you for attention!

Also popular now: