Signal and synchronous mutual exclusion

The process of mutual exclusion and P, V operation 1. Critical resources What is critical resources: only the resources used by one process are critical resources. What is a critical area: The code segment that visits critical resources is the critical area. For example: code segment 1 a = count; A-; count = a; code segment 2 b = count; b ; count = b; is critical area, count is critical resources. Access to critical resources must meet the following conditions: Only one process can enter, other processes waiting. The entrant must exit in a limited time. Waitingers should have the opportunity to enter. Second, the structure model of the semaphore: (s, q) In the 2.4.x core, the semaphore data structure is defined as (include / asm / semaphore.h): struct semaphore {atomic_t count; int Sleepers; Wait_Queue_head_t Wait; #if waitqueue_debug long __magic; #ENDIF}; Semicone operation: 1) Initialization 2) P operation a) S - b) IF (S <0) Sleep ELSE in Q Q queue ELSE 3) V operation a) S b) IF (s <= 0) Wake a sleep process (waiting for progress in the queue in sleep) ELSE Continued P operations can be understood as application resources, V operations can be understood as release resources, in the 2.4.x kernel Semaphore structure, count is the resource Count, for positive or 0, the number of available resources, -1 indicates no idle resources and waiting for the process, as for waiting for the number of processes, relying on Sleepers, complicated, but the benefits are UP operation is very simple Just assemble atomically add count, if less than or equal to 0, the process is waiting, call __up_wakeup () -> __UP (), otherwise returns. The implementation in Linux can be seen in Arch / I386 / Kernel / Semaphore.c, __ down () and __UP (). Signal Implementation: A simple implementation of iTron as an example. I watched the code, regarding the Semaphore's P / V operation, with counter control and waiting queue. Semcb (Semaphore Control Block) has members such as ID, queues, counters. Os_acquiresemaphoretimeOut () {... Lock () Semcb-> Semcnt - // Counter - IF (Semcb-> Semcnt <0) {Make_Wait () // Make Current Task in Wait State Queue_INSERT_TPRI () // Insert by Priority To the semaphore's // Wait Queue, Which is a circular queue} unlock () ...} os_freesemaphore () {... lock () ife (semcp-> semcnt <0) {wait_release_ok () | -> Wait_Release () // Release a Task from Wait State} Semcb-> Semcnt // Counter unlock () ...} Note: V operation S 先 plus 1 to determine if it is less than or equal to 0 and first judge whether it is less than 0 and add 1 is equivalent.

Note: In this implementation, the SEMCNT value is not only the resource idle or has a process, and its absolute value is also meaningful. The number of processes waiting for the negative time value represents the number of resources that are idle resources. . Third, synchronous mutex model s = 1 AP (s) critical area V (s) BP (s) critical area V (s) producer consumer problem (producer calculation generation), consumer printing.) 1 production 1 consumers, buffer BUF is 1 2 semaphore: PUT = 1 get = 0 A calculates X P (PUT) BUF = X V (GET) BP (GET) Y = BUF V (PUT) print Y 1 producer 2 consumers, buffer BUF is 1 (2 consumers a print odd number of printed numbers) 3 semaphors implementation model: PUT = 1 getj = 0 getO = 0 A calculates X P (PUT) buf = X if (x 奇) V (Getj) Else V (GETO) BP (Getj) Y = BUF V (PUT) Print Y CP (GETO) Y = BUF V (PUT) Print Y This model is more intuitive, but used 3 semaphors. Different signals from "V" is determined after the X is calculated. If only 2 semons are implemented, the producer calculates a signal of "V" after X, and the two consumers will be taken out and determine whether the print is still in the case. 2 semaphores: PUT = 1 get = 0 A calculates X P (PUT) BUF = X V (GET) BP (GET) Y = BUF} if (y is 奇) {v (PUT) print y} else V (GET) CP (GET) Y = BUF IF (Y) {V (PUT) Print Y} ELSE V (GET) 1 consumer, buffer BUF is M 2 semaphore implementation model: PUT = M get = 0 A calculates X P (PUT) BUF [T] = xt = ( T)% M v (Get) BP (GET) Y = BUF [K] K = ( K)% M V (PUT) prints Y N producers M consumers, buffer BUF is M 4 semaphore implementation model: PUT = M get = 0 t = 1 k = 1 A calculates X P (PUT) P (T) BUF [T] = = xt = ( T)% M V (T) V (GET) BP (GET) p (k) y = BUF [K] K = ( K)% M V (K) V ( PUT) Print Y 4. Delete a semaphore deletes a semaphore, the system should release some resources. If there is no process waiting for this quantity, the process is relatively simple. If there is a process waiting for this signal, how to handle these processes, some people say kill, but the implementation I see is awake. In addition to the process, this waiting queue also needs to be released, otherwise the memory leak will cause memory. Not only deletes a semaphore, not only a certain resource is deleted, and all Task waiting for the queue will be released. OS_DELFLAG - | OS_DELMESSAGEBUFFER - | -> Call wait_delete (queue *) -> os_delsemaphore - | While () {wait_release (); ...} // Release All tasks blocked on specified wait Queue 5, why Tap so much. Because there is a self-realization-based ITron-based OS requires test.