Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Linux atomic operations and synchronization mechanisms     - To install JDK1.7 and compiler Hadoop-2.7.1 under CentOS7 (Server)

- Wildcards and special symbols usage comments under Linux (Linux)

- Mount and unloading disks under Linux (Linux)

- Python MySQL database connection (Database)

- Android imitation UC browser scroll up and down functions (Programming)

- Asynchronous communication mechanism between the Android source code analysis thread (Programming)

- Python function arguments * args and ** kwargs usage (Programming)

- CentOS 6.5 / 6.6 modify the default SSH port number (Linux)

- CentOS 6.4 installation environment to build Scrapy 0.22 (Linux)

- How to install Laravel PHP framework on CentOS 7 / Ubuntu 15.04 (Server)

- RM Environment Database RMAN Backup Strategy Formulation (Database)

- Oracle bug Ora-04043 (Database)

- Use scripts easily install the latest Linux kernel in Ubuntu (Linux)

- 20 Linux commands interview questions and answers (Linux)

- Ubuntu 14.04 VirtualBox can not start solution (Linux)

- Configuring the PXE server in Ubuntu 14.04 (Server)

- Slice MyCAT common fragmentation rules of enumeration (Database)

- CentOS cross compiler core Raspberry Pi 2 (Linux)

- Use chattr and lsattr command to manage linux files and directory attributes (Linux)

- Use virt-manager to create and manage virtual machines (Linux)

 
         
  Linux atomic operations and synchronization mechanisms
     
  Add Date : 2018-11-21      
         
         
         
  Concurrency issues

Modern operating systems support multiple concurrent tasks, concurrent computing while improving resource utilization has also brought the resource competition. For example, C language statement "count ++;" assembly code generated when the compiler optimization is not.



When the operating system memory execute the code in multiple processes at the same time, it is possible to bring concurrency issues.



Suppose count variable is initialized to zero. A process executing the "mov eax, [count]", the eax register holds the count value of 0. In this case, the process 2 is scheduled for execution, to seize control of the CPU 1 of the process. Process 2 Run "count ++;" assembly code, the count value accumulated after 1 is written back to memory. Then, the process 1 is again scheduled for execution, CPU control back to process 1. 1 process is then performed to calculate the cumulative value of the count is still 1, written back to memory. Although the processes 1 and 2 performed twice "count ++;" operation, but the actual count memory is 1, not 2!
Uniprocessor atomic operations

Solve this problem is to "count ++;" statement is translated to a single instruction.



Intel x86 instruction set supports inc operation memory operand, and "count ++;" the operation can be completed in one instruction. Because the context of the process of switching is always after an instruction is executed, it does not occur concurrency issues. For single processors, a processor instruction is an atomic operation.

Multiprocessor atomic operations

However, in a multi-processor environment, such as SMP architecture, this conclusion is no longer valid. We know that during the execution of "inc [count]" instruction is divided into three steps:

1) read from memory count data to the cpu.

2) the cumulative value read.

3) modify the value of the writeback count memory.

This goes back to the previous concurrency issues similar situation, only this time the theme is no longer a concurrent process, but the processor.

Intel x86 instruction set provides instructions prefix lock for locking the front end serial bus (FSB), to ensure that the other processors will not be disturbed when the instruction is executed.



Use lock instruction prefix, the inter-processor count concurrent access to memory (read / write) is prohibited, thus ensuring the atomic instruction.



x86 implement atomic operations

Linux source code is defined in the file structure of the atom for x86 operating system.

linux2.6 / include / asm-i386 / atomic.h

Document defines the atomic type atomic_t, it is only a field counter, for storing 32-bit data.

typedef struct {volatile int counter;} atomic_t;

Wherein the atomic manipulation functions atomic_inc complete self-imposed atomic operation.

/ **

 * Atomic_inc - increment atomic variable

 * @v: Pointer of type atomic_t

 *

 * Atomically increments @v by 1.

 * /

static __inline__ void atomic_inc (atomic_t * v)

{

    __asm__ __volatile __ (

      LOCK "incl% 0"

      : "= M" (v-> counter)

      : "M" (v-> counter));

}

Which is defined as a macro LOCK.

#ifdef CONFIG_SMP

    #define LOCK "lock;"

#else

    #define LOCK ""

#endif

Seen in the case of a symmetric multi-processor architecture, LOCK is interpreted as a command prefix lock. For single-processor architecture, LOCK does not contain any content.

arm atomic operations to achieve

In the arm instruction set, there is no instruction prefix lock, how to complete the atomic operation that it?

Linux source code is defined in the file system of the operating arm structure of the atom is.

linux2.6 / include / asm-arm / atomic.h

Wherein the self-imposed by the atomic function atomic_add_return implementation.

static inline int atomic_add_return (int i, atomic_t * v)

{

    unsigned long tmp;

    int result;

    __asm__ __volatile __ ( "@ atomic_add_return n"

      "1: ldrex% 0, [% 2] n"

      "Add% 0,% 0,% 3 n"

      "Strex% 1,% 0, [% 2] n"

      "Teq% 1, # 0 n"

      "Bne 1b"

      : "= & R" (result), "= & r" (tmp)

      : "R" (& v-> counter), "Ir" (i)

      : "Cc");

    return result;

}

The actual form of the above is embedded assembly.

1:

ldrex [result], [v-> counter]

add [result], [result], [i]

strex [temp], [result], [v-> counter]

teq [temp], # 0

bne 1b

ldrex instruction v-> counter value transferred to the result, and set the global mark "Exclusive".

add instruction completion "result + i" of the operation and saves the addition result to result.

strex instruction detected first global tag "Exclusive" exists, if present, the value will result writeback counter-> v, and the temp is set to 0, clear the "Exclusive" tag, or directly to end temp is set to 1.

teq directive test temp value is 0.

bne instruction is not equal to zero temp jump to label 1, wherein the character b represents a jump backwards.

Overall, the above-described assembly code has been trying to complete "v-> counter + = i" operation until the end of temp is 0:00.

Use ldrex and strex instructions can guarantee whether atomic add command it? Suppose two processes concurrently executing "ldrex + add + strex" operation, when the process execution ldrex 1 set global tag "Exclusive". At this point the process of switching to 2, before performing ldrex global tag "Exclusive" has been set, after ldrex repetitive set the mark. Then add execute instructions and strex complete accumulate operations. Switch back to process 1 again, and then execute add instructions that, when executed strex instruction, since the "Exclusive" flag is cleared Process 2, and therefore does not perform the transfer operation, the temp is set to 1. Teq measured temp successor instruction is not equal to 0, then jump to the beginning of re-execute the eventual accumulation operation! Visible ldrex and strex instructions can ensure the synchronization between processes. Multiprocessor with this same, because the operating arm of the atomic concerned only "Exclusive" tag, but not with the front end of the serial bus is locked.

Prior to ARMv6, swp instruction bus is accomplished by locking the data exchange atoms, but the impact on system performance. After ARMv6, and general use ldrex strex instruction instead of swp instruction function.

Spinlock atomic operations

Linux source code in the x86 architecture spinlock definition file.

linux2.6 / include / asm-i386 / spinlock.h

Wherein __raw_spin_lock complete the spin-lock lock function

#define __raw_spin_lock_string

    " N1: t"

    "Lock; decb% 0 n t"

    "Jns 3f n"

    "2: t"

    "Rep; nop n t"

    "Cmpb $ 0,% 0 n t"

    "Jle 2b n t"

    "Jmp 1b n"

    "3: n t"

static inline void __raw_spin_lock (raw_spinlock_t * lock)

{

    __asm__ __volatile __ (

      __raw_spin_lock_string

      : "= M" (lock-> slock):: "memory");

}

The actual form of the above code is compiled.

1:

lock decb [lock-> slock]

jns 3

2:

rep nop

cmpb $ 0, [lock-> slock]

jle 2

jmp 1

3:

Wherein the lock-> slock field an initial value of 1, after performing an atomic operation decb zero. The sign bit is 0, execution jumps to 3 jns instruction to complete the spin lock lock.

When applying spin lock again, after performing an atomic operation decb lock-> slock -1. The sign bit is 1, the instruction is not executed jns. Access to the label 2, Comparative lock- after performing a set of instructions nop> if slock less than or equal to 0, if less than or equal to 0 back label 2 cycle (spin). Otherwise, jump to label 1 reapply spin lock until the application is successful.

When the spin-lock release will lock-> slock set to 1, thus ensuring that other processes can acquire spin lock.

Semaphore atomic operations

Linux source code in the x86 architecture spinlock definition file.

linux2.6 / include / asm-i386 / semaphore.h

Requesting a semaphore implemented by the function down.

/ *

 * This is ugly, but we want the default case to fall through.

 * "__down_failed" Is a special asm handler that calls the C

 * Routine that actually waits. See arch / i386 / kernel / semaphore.c

 * /

static inline void down (struct semaphore * sem)

{

    might_sleep ();

    __asm__ __volatile __ (

      "# Atomic down operation n t"

      LOCK "decl% 0 n t" / * --sem-> count * /

      "Js 2f n"

      "1: n"

      LOCK_SECTION_START ( "")

      "2: tlea% 0, %% eax n t"

      "Call __down_failed n t"

      "Jmp 1b n"

      LOCK_SECTION_END

      : "= M" (sem-> count)

      :

      : "Memory", "ax");

}

The actual assembly code form.

lock decl [sem-> count]

js 2

1:

<========== Another section ==========>

2:

lea [sem-> count], eax

call __down_failed

jmp 1

Semaphore sem-> count Usually initialized to a positive integer, an atomic semaphore operation decl when applying the sem-> count minus one. If the value is reduced to negative (sign bit is 1) jump to another label segment 2, or the application semaphore success.

2 tag is compiled into another section, enter the label 2, the Executive lea instruction fetch sem-> count address into the eax register as an argument, and then calls the function __down_failed signal representing the amount of the application fails, the process added to the waiting queue. Finally, jump back to the end of the tag 1 semaphore applications.

Semaphore release operation is realized by the function up.

/ *

 * Note! This is subtle. We jump to wake people up only if

 * The semaphore was negative (== somebody was waiting on it).

 * The default case (no contention) will result in NO

 * Jumps for both down () and up ().

 * /

static inline void up (struct semaphore * sem)

{

    __asm__ __volatile __ (

      "# Atomic up operation n t"

      LOCK "incl% 0 n t" / * ++ sem-> count * /

      "Jle 2f n"

      "1: n"

      LOCK_SECTION_START ( "")

      "2: tlea% 0, %% eax n t"

      "Call __up_wakeup n t"

      "Jmp 1b n"

      LOCK_SECTION_END

      ".subsection 0 n"

      : "= M" (sem-> count)

      :

      : "Memory", "ax");

}

The actual assembly code form.

lock incl sem-> count

jle 2

1:

<========== Another section ==========>

2:

lea [sem-> count], eax

call __up_wakeup

jmp 1

Perform atomic operations incl releasing the semaphore will sem-> count plus 1, if the value is less than or equal to 0, then the wait queue has blocked processes need to wake up, jump to label 2, otherwise the success of the release of the semaphore.

2 tag is compiled into another section, enter the label 2, the Executive lea instruction fetch sem-> count address into the eax register as an argument, and then calls the function __up_wakeup wakeup waiting process queue. Finally, jump back to the end of a label to release the semaphore.

 

To sum up

Through the realization of the principle of the operating system concurrency issues discussed Research within the operating system atomic operations, and discusses the implementation of different architectures Linux atomic operations, and finally describes the Linux operating system how to use atomic operations to achieve a common process synchronization mechanism, I hope for your help.
     
         
         
         
  More:      
 
- In-depth summary of the PHP core of object-oriented (Programming)
- Installation and deployment of MariaDB under CentOS (Database)
- Modifying the system registry protection server security (Linux)
- How to fix the Ubuntu Error script returned error exit status 1 (Linux)
- Three methods easy data encryption on Linux (Linux)
- Distributed File System using MogileFS (Linux)
- Linux and Unix systems really do network more secure (Linux)
- ORA-12547: TNS: lost contact error Solution (Database)
- PHP interview questions of design patterns (Programming)
- To deploy MySQL database with separate read and write OneProxy (Database)
- Computer security perimeter recommendations (Linux)
- Getting Started with Linux system to learn: how to check memory usage of Linux (Linux)
- Generated characters using Java Videos (Programming)
- Android first line of code study notes (Programming)
- Linux Firewall IPCop Profile (Linux)
- CentOS 7 source code to compile and install PHP5.6 Nginx1.7.9 and MySQL (LNMP build environment) (Server)
- To batch create users under Linux (Linux)
- Linux compression and decompression command (Linux)
- Linux dmidecode command detail (Linux)
- HBase cluster installation and deployment (Server)
     
           
     
  CopyRight 2002-2020 newfreesoft.com, All Rights Reserved.