Process SynchronizationReferences:A

Process Synchronization

References:

Abraham Silberschatz, Greg Gagne, and Peter Baer Galvin, "Operating System Concepts, Eighth Edition ", Chapter 6
Warning: This chapter requires some heavy thought. As you read each of the algorithms below, you need to satisfy yourself that they do indeed work under all conditions. Think about it, and don't just accept them at face value.

6.1 Background

Recall that back in Chapter 3 we looked at cooperating processes ( those that can effect or be effected by other simultaneously running processes ), and as an example, we used the producer-consumer cooperating processes:
Producer code from chapter 3:

item nextProduced;

while( true ) {

/* Produce an item and store it in nextProduced */
nextProduced = makeNewItem( . . . );

/* Wait for space to become available */
while( ( ( in + 1 ) % BUFFER_SIZE ) == out )
; /* Do nothing */

/* And then store the item and repeat the loop. */
buffer[ in ] = nextProduced;
in = ( in + 1 ) % BUFFER_SIZE;

}

Consumer code from chapter 3:

item nextConsumed;

while( true ) {

/* Wait for an item to become available */
while( in == out )
; /* Do nothing */

/* Get the next available item */
nextConsumed = buffer[ out ];
out = ( out + 1 ) % BUFFER_SIZE;

/* Consume the item in nextConsumed
( Do something with it ) */

}

The only problem with the above code is that the maximum number of items which can be placed into the buffer is BUFFER_SIZE - 1. One slot is unavailable because there always has to be a gap between the producer and the consumer.
We could try to overcome this deficiency by introducing a counter variable, as shown in the following code segments:


Unfortunately we have now introduced a new problem, because both the producer and the consumer are adjusting the value of the variable counter, which can lead to a condition known as a race condition. In this condition a piece of code may or may not work correctly, depending on which of two simultaneous processes executes first, and more importantly if one of the processes gets interrupted such that the other process runs between important steps of the first process. ( Bank balance example discussed in class. )
The particular problem above comes from the producer executing "counter++" at the same time the consumer is executing "counter--". If one process gets part way through making the update and then the other process butts in, the value of counter can get left in an incorrect state.
But, you might say, "Each of those are single instructions - How can they get interrupted halfway through?" The answer is that although they are single instructions in C++, they are actually three steps each at the hardware level: (1) Fetch counter from memory into a register, (2) increment or decrement the register, and (3) Store the new value of counter back to memory. If the instructions from the two processes get interleaved, there could be serious problems, such as illustrated by the following:


Exercise: What would be the resulting value of counter if the order of statements T4 and T5 were reversed? ( What should the value of counter be after one producer and one consumer, assuming the original value was 5? )
Note that race conditions are notoriously difficult to identify and debug, because by their very nature they only occur on rare occasions, and only when the timing is just exactly right. ( or wrong! :-) ) Race conditions are also very difficult to reproduce. :-(
Obviously the solution is to only allow one process at a time to manipulate the value "counter". This is a very common occurrence among cooperating processes, so lets look at some ways in which this is done, as well as some classic problems in this area.
6.2 The Critical-Section Problem

The producer-consumer problem described above is a specific example of a more general situation known as the critical section problem. The general idea is that in a number of cooperating processes, each has a critical section of code, with the following conditions and terminologies:
Only one process in the group can be allowed to execute in their critical section at any one time. If one process is already executing their critical section and another process wishes to do so, then the second process must be made to wait until the first process has completed their critical section work.
The code preceding the critical section, and which controls access to the critical section, is termed the entry section. It acts like a carefully controlled locking door.
The code following the critical section is termed the exit section. It generally releases the lock on someone else's door, or at least lets the world know that they are no longer in their critical section.
The rest of the code not included in either the critical section or the entry or exit sections is termed the remainder section.


A solution to the critical section problem must satisfy the following three conditions:
Mutual Exclusion - Only one process at a time can be executing in their critical section.
Progress - If no process is currently executing in their critical section, and one or more processes want to execute their critical section, then only the processes not in their remainder sections can participate in the decision, and the decision cannot be postponed indefinitely. ( I.e. processes cannot be blocked forever waiting to get into their critical sections. )
Bounded Waiting - There exists a limit as to how many other processes can get into their critical sections after a process requests entry into their critical section and before that request is granted. ( I.e. a process requesting entry into their critical section will get a turn eventually, and there is a limit as to how many other processes get to go first. )
We assume that all processes proceed at a non-zero speed, but no assumptions can be made regarding the relative speed of one process versus another.
Kernel processes can also be subject to race conditions, which can be especially problematic when updating commonly shared kernel data structures such as open file tables or virtual memory management. Accordingly kernels can take on one of two forms:
Non-preemptive kernels do not allow processes to be interrupted while in kernel mode. This eliminates the possibility of kernel-mode race conditions, but requires kernel mode operations to complete very quickly, and can be problematic for real-time systems, because timing cannot be guaranteed.
Preemptive kernels allow for real-time operations, but must be carefully written to avoid race conditions. This can be especially tricky on SMP systems, in which multiple kernel processes may be running simultaneously on different processors.
Non-preemptive kernels include Windows XP, 2000, traditional UNIX, and Linux prior to 2.6; Preemptive kernels include Linux 2.6 and later, and some commercial UNIXes such as Solaris and IRIX.
6.3 Peterson's Solution

Peterson's Solution is a classic software-based solution to the critical section problem. It is unfortunately not guaranteed to work on modern hardware, due to vagaries of load and store operations, but it illustrates a number of important concepts.
Peterson's solution is based on two processes, P0 and P1, which alternate between their critical sections and remainder sections. For convenience of discussion, "this" process is Pi, and the "other" process is Pj. ( I.e. j = 1 - i )
Peterson's solution requires two shared data items:
int turn - Indicates whose turn it is to enter into the critical section. If turn = = i, then process i is allowed into their critical section.
boolean flag[ 2 ] - Indicates when a process wants to enter into their critical section. When process i wants to enter their critical section, it sets flag[ i ] to true.
In the following diagram, the entry and exit sections are enclosed in boxes.
In the entry section, process i first raises a flag indicating a desire to enter the critical section.
Then turn is set to j to allow the other process to enter their critical section if process j so desires.
The while loop is a busy loop ( notice the semicolon at the end ), which makes process i wait as long as process j has the turn and wants to enter the critical section.
Process i lowers the flag[ i ] in the exit section, allowing process j to continue if it has been waiting.


To prove that the solution is correct, we must examine the three conditions listed above:
Mutual exclusion - If one process is executing their critical section when the other wishes to do so, the second process will become blocked by the flag of the first process. If both processes attempt to enter at the same time, the last process to execute "turn = j" will be blocked.
Progress - Each process can only be blocked at the while if the other process wants to use the critical section ( flag[ j ] = = true ), AND it is the other process's turn to use the critical section ( turn = = j ). If both of those conditions are true, then the other process ( j ) will be allowed to enter the critical section, and upon exiting the critical section, will set flag[ j ] to false, releasing process i. The shared variable turn assures that only one process at a time can be blocked, and the flag variable allows one process to release the other when exiting their critical section.
Bounded Waiting - As each process enters their entry section, they set the turn variable to be the other processes turn. Since no process ever sets it back to their own turn, this ensures that each process will have to let the other process go first at most one time before it becomes their turn again.
Note that the instruction "turn = j" is atomic, that is it is a single machine instruction which cannot be interrupted.
6.4 Synchronization Hardware

To generalize the solution(s) expressed above, each process when entering their critical section must set some sort of lock, to prevent other processes from entering their critical sections simultaneously, and must release the lock when exi

ผลลัพธ์ (ไทย) 1:

กระบวนการซิงโครไนส์อ้างอิง:อับราฮัม Silberschatz กา Gagne และปีเตอร์รัซเซลเบเออร์ Galvin "ระบบปฏิบัติการแนวคิด 8", 6 บทคำเตือน: บทนี้ต้องคิดหนักบาง เมื่อคุณอ่านแต่ละอัลกอริทึมด้านล่าง คุณจำเป็นต้องตอบสนองตัวเองที่พวกเขาจริงทำงานภายใต้เงื่อนไขทั้งหมด คิดเกี่ยวกับมัน และไม่เพียงยอมรับพวกเขาที่หน้าค่า6.1 พื้นหลังนึกว่า กลับมาในบทที่ 3 เรามองที่กระบวนฟลอริ (ผู้ที่สามารถมีผล หรือมีผลอื่น ๆ โดยกระบวนการทำงานพร้อมกัน), และเป็นตัวอย่าง เราใช้กระบวนการฟลอริผู้ผลิตผู้บริโภค:รหัสโปรดิวเซอร์จากบทที่ 3:สินค้า nextProducedในขณะที่{(จริง)/ * ผลิตสินค้า และจัดเก็บใน nextProduced * /nextProduced = makeNewItem (...); / * รอเนื้อที่ได้มี * / ในขณะที่ (((ใน + 1) % BUFFER_SIZE) ==ออก) ; / * ไม่ * // * แล้วเก็บสินค้า และการวนทำซ้ำ */ บัฟเฟอร์ [ใน] = nextProducedใน = (ใน + 1) % BUFFER_SIZE}รหัสผู้บริโภคจากบทที่ 3:สินค้า nextConsumedในขณะที่{(จริง)/ * รอสินค้าได้มี * / ในขณะที่ (ใน==ออก) ; / * ไม่ * // * ได้รับสินค้าที่พร้อมใช้ถัดไป * / nextConsumed =บัฟเฟอร์ [ออก];ออก = (ออก + 1) % BUFFER_SIZE/ * บริโภคสินค้าใน nextConsumed (ทำอะไรกับมัน) * /}ปัญหาเดียวกับรหัสข้างต้นคือ ว่าจำนวนของสินค้าที่สามารถวางลงในบัฟเฟอร์ BUFFER_SIZE - 1 ช่องหนึ่งไม่พร้อมใช้งานเนื่องจากตลอดเวลาจะต้องมี ช่องว่างระหว่างผู้ผลิตและผู้บริโภคเราอาจพยายามเอาชนะขาดนี้ โดยการแนะนำตัวแปรนับ ตามที่แสดงในส่วนรหัสต่อไปนี้:แต่เราได้ตอนนี้แนะนำปัญหาใหม่ เนื่องจากทั้งผู้ผลิตและผู้บริโภคมีการปรับค่าของตัวนับตัวแปร ซึ่งสามารถนำไปสู่สภาพที่เรียกว่าเงื่อนไขการแข่งขัน ในสภาพนี้ชิ้นส่วนของรหัสอาจ หรืออาจไม่ทำงานถูกต้อง ตามที่สองพร้อมกระบวนดำเนินครั้งแรก และที่สำคัญถ้ากระบวนการหนึ่งจังหวะที่กระบวนการทำงานระหว่างขั้นตอนสำคัญของกระบวนการแรก (ธนาคารดุลตัวอย่างในชั้นเรียน)ปัญหาเฉพาะดังกล่าวมาจากผู้ผลิตดำเนิน "เคาน์เตอร์เก็บ ++" ขณะเดียวกันผู้บริโภคกำลังดำเนินการ "เคาน์เตอร์-" ถ้ากระบวนการหนึ่งได้รับส่วนวิธี โดยทำการปรับปรุงแล้ว กระบวนการ butts ใน ค่าของตัวนับสามารถรับเหลือในสถานะไม่ถูกต้องแต่ คุณอาจพูด ว่า "แต่ละคนมีคำแนะนำเดียว - วิธีสามารถพวกเขาได้รับการขัดจังหวะ halfway ผ่าน" คำตอบคือ ว่า แม้ว่าจะเป็นคำสั่งเดียวใน c ++, พวกเขาเป็นจริงสามขั้นตอนแต่ละระดับฮาร์ดแวร์: Fetch (1) เคาน์เตอร์จากหน่วยความจำลงทะเบียน, (2) เพิ่มขึ้น หรือลดลงทะเบียน และ (3) เก็บค่าของตัวนับกลับไปยังหน่วยความจำ ถ้าคำแนะนำจากกระบวนการทั้งสองได้รับแผนที่ อาจมีปัญหาร้ายแรง เช่น ตามต่อไปนี้:ออกกำลังกาย: อะไรจะนับค่าได้ถ้ามีการย้อนกลับลำดับของคำสั่ง T4 และ T5 (สิ่งควรค่าของตัวนับจะหลังจากโปรดิวเซอร์หนึ่ง และหนึ่งผู้บริโภค สมมติว่าค่าเดิมเป็น 5)โปรดสังเกตว่า เงื่อนไขการแข่งขันยากฉาวระบุ และตรวจแก้จุด บกพร่อง เนื่อง จาก โดยธรรมชาติของพวกเขามาก เท่านั้นเกิดขึ้นในโอกาสที่หายาก และเวลาถูกต้องเพียง (หรือไม่ถูกต้อง! :-)) เงื่อนไขการแข่งขันก็ยากที่จะสร้าง :-(แน่นอนโซลูชั่นมีให้เพียง หนึ่งครั้งเพื่อควบคุมค่า "นับ" นี้เป็นมากในกระบวนการฟลอริ ดังนั้น ให้ดูที่วิธีการบางอย่างในที่นี้จะทำ เป็นปัญหาคลาสสิกในพื้นที่นี้6.2 ส่วนสำคัญปัญหาปัญหาผู้ผลิตผู้บริโภคอธิบายไว้ข้างต้นเป็นตัวอย่างเฉพาะของสถานการณ์ทั่วไปที่เป็นปัญหาส่วนที่สำคัญ ความคิดทั่วไปเป็นที่จำนวนกระบวนฟลอริ มีส่วนที่สำคัญของรหัส เงื่อนไขและ terminologies ต่อไปนี้:กระบวนการหนึ่งในกลุ่มสามารถได้รับอนุญาตให้ดำเนินการในส่วนที่สำคัญของพวกเขาตลอดเวลาหนึ่ง ถ้าหนึ่งแล้วกำลังดำเนินการส่วนที่สำคัญ และกระบวนการอื่นต้องการ แล้วกระบวนการสองต้องทำการรอจนกว่ากระบวนการแรกแล้วเสร็จงานส่วนที่สำคัญรหัสก่อนหน้าส่วนสำคัญ และการควบคุมเข้าถึงส่วนที่สำคัญ เรียกว่าส่วนรายการ มันทำหน้าที่เหมือนประตูล็อกควบคุมอย่างระมัดระวังรหัสต่อไปนี้ส่วนที่สำคัญเรียกว่าส่วนออก โดยทั่วไปจะปลดล็อคคนอื่นเป็นประตู หรือน้อย ให้โลกรู้ว่า จะมีในส่วนที่สำคัญของพวกเขาส่วนเหลือของรหัสที่ไม่รวมอยู่ในส่วนสำคัญหรือส่วนรายการหรือออกเรียกว่าส่วนเหลือการแก้ไขปัญหาส่วนที่สำคัญต้องตรงกับเงื่อนไขสามต่อไปนี้:แยกออกซึ่งกันและกัน - สามารถเป็นการดำเนินกระบวนการเพียงหนึ่งครั้งในส่วนที่สำคัญของพวกเขาคืบหน้า - ถ้าไม่มีกระบวนการที่กำลังดำเนินอยู่ในส่วนที่สำคัญของพวกเขา และกระบวนการหนึ่ง หรือมากกว่าที่ต้องการดำเนินการส่วนที่สำคัญของพวกเขา แล้วกระบวนการในส่วนของส่วนที่เหลือไม่สามารถเข้าร่วมในการตัดสินใจ ตัดสินใจไม่เลื่อนไม่มีกำหนด (เช่นกระบวนไม่ถูกบล็อกตลอดไปคอยเป็นส่วนสำคัญของพวกเขา)ล้อมรอบรอ - มีขีดจำกัดกับกระบวนการอื่น ๆ ได้เป็นส่วนสำคัญของพวกเขาหลังจากที่กระบวนการร้องขอรายการ เป็นส่วนที่สำคัญของพวกเขา และ ก่อนได้รับการร้องขอ (เช่นกระบวนการร้องขอรายการเป็นส่วนที่สำคัญของพวกเขาจะได้รับกลับมาในที่สุด และมีขีดจำกัดกับกระบวนการอื่น ๆ ไปไปครั้งแรก)เราสมมติว่า กระบวนการทั้งหมดดำเนินการที่ความเร็วหนึ่ง แต่สมมติฐานไม่ได้เกี่ยวกับความเร็วสัมพัทธ์ของกระบวนหนึ่งเทียบกับอีกกระบวนการเคอร์เนลไม่สามารถขึ้นอยู่กับสภาพการแข่งขัน ซึ่งสามารถมีปัญหาโดยเฉพาะเมื่อปรับปรุงบ่อยร่วมเคอร์เนลโครงสร้างข้อมูลเช่นแฟ้มเปิดตารางหรือการจัดการหน่วยความจำเสมือน ตาม เมล็ดสามารถทำในสองรูปแบบอย่างใดอย่างหนึ่ง:เมล็ดที่ไม่ใช่ preemptive อนุญาตกระบวนการถูกขัดจังหวะขณะอยู่ในโหมดเคอร์เนล นี้กำจัดของโหมดเคอร์เนลแข่งขันเงื่อนไข แต่ต้องเคอร์เนลโหมดการดำเนินการให้เสร็จสมบูรณ์ได้อย่างรวดเร็ว และสามารถเป็นปัญหาสำหรับระบบเรียลไทม์ เพราะเวลาไม่สามารถรับประกันเมล็ด preemptive อนุญาตสำหรับการดำเนินงานแบบเรียลไทม์ แต่ต้องระมัดระวังเขียนเพื่อหลีกเลี่ยงเงื่อนไขการแข่งขัน นี้เป็นเรื่องยุ่งยากโดยเฉพาะอย่างยิ่งระบบ SMP ที่หลาย ๆ กระบวนการเคอร์เนลอาจเรียกใช้พร้อมกันบนตัวประมวลผลที่แตกต่างกันเมล็ดที่ไม่ใช่ preemptive รวม Windows XP, 2000, UNIX ดั้งเดิม และ Linux ก่อน 2.6 เมล็ด preemptive รวม Linux 2.6 และ UNIXes ในภายหลัง และบางธุรกิจเช่น IRIX และโซลาริส 6.3 Peterson โซลูชันโซลูชันของ Peterson เป็นคลาสสิกซอฟต์แวร์โซลูชันปัญหาส่วนที่สำคัญ มันเป็นแต่ไม่รับประกันว่า จะทำงานบนฮาร์ดแวร์ที่ทันสมัย เนื่องจากทุกข์ของโหลด และดำเนินการเก็บ แต่มันแสดงจำนวนแนวคิดที่สำคัญโซลูชันของ Peterson จะขึ้นอยู่กับ 2 กระบวน P0 และ P1 การสลับระหว่างส่วนสำคัญและส่วนที่เหลือของพวกเขา เพื่อความสะดวกของการสนทนา "นี้" กระบวนปี่ และกระบวนการ "อื่นๆ" พีเจ. (I.e. j = 1 - ฉัน)โซลูชันของ Peterson ต้องสองรายการข้อมูลที่ใช้ร่วมกัน:int เปิด - บ่งชี้ว่า เปิดจะป้อนเข้าไปในส่วนสำคัญ ถ้าเปิด==ฉัน แล้วได้เป็นส่วนสำคัญของกระบวนการค่าสถานะบูลี [2] - บ่งชี้เมื่อต้องเข้าสู่ส่วนสำคัญของกระบวนการ เมื่อประมวลผมอยากเข้าส่วนที่สำคัญของพวกเขา มันตั้งธง [i] เป็น trueในแผนภาพต่อไปนี้ ส่วนและออกจะอยู่ในกล่องในส่วนรายการ ประมวลผลฉันยกแรกธงแสดงความปรารถนาที่จะใส่ส่วนที่สำคัญแล้ว เปิดถูกกำหนดเป็นเจเพื่อให้กระบวนการอื่น ๆ เพื่อป้อนส่วนสำคัญของกระบวนการเจปรารถนาในขณะวนเป็นวนวุ่นวาย (สังเกตหมายอัฒภาคท้าย), ซึ่งทำให้กระบวนการรอตราบเท่าที่กระบวนการเจได้เปิด และอยากเข้าหัวข้อสำคัญกระบวนการฉันออกธง [i] ในส่วนออก ทำให้เจกระบวนการหาก ได้รับการรอคอยเราต้องตรวจสอบเงื่อนไขสามรายการข้างต้นเพื่อพิสูจน์ว่า การแก้ปัญหาถูกต้อง :ซึ่งกันและกันแยก - ถ้ากำลังดำเนินส่วนสำคัญของกระบวนการหนึ่งเมื่ออื่น ๆ ที่ประสงค์จะ กระบวนการสองจะกลายเป็นบล็อก โดยค่าสถานะของกระบวนการแรก ถ้ากระบวนการทั้งสองพยายามป้อนที่ตรง เวลา กระบวนการสุดท้ายดำเนินการ "เปิด =เจ" จะถูกบล็อกไว้ความคืบหน้า - แต่ละกระบวนการสามารถเท่านั้นถูกบล็อคในขณะถ้ากระบวนการต้องการใช้ส่วนสำคัญ (ธง [j] ==จริง), และเปิดของกระบวนการอื่น ๆ ไปใช้ส่วนสำคัญ (เปิด== j) ถ้าทั้งสองเงื่อนไขที่เป็นจริง แล้วอื่น ๆ กระบวนการ (เจ) จะได้รับอนุญาตให้ป้อนส่วนที่สำคัญ และเมื่อออกจากส่วนที่สำคัญ จะตั้งธง [j] เท็จ ปล่อยประมวลผลฉันนั้น เปิดตัวแปรร่วมกันมั่นใจว่า กระบวนการเดียวที่สามารถถูกบล็อค และแปรค่าสถานะช่วยให้กระบวนการหนึ่งไปปล่อยอีกเมื่อออกจากส่วนที่สำคัญของพวกเขาล้อมรอบรอ - ตามแต่ละกระบวนการป้อนส่วนรายการของพวกเขา พวกเขาตั้งตัวแปรเปิดจะ เปิดกระบวนการ เนื่องจากกระบวนการไม่เคยตั้งก็ เปิดกลับไปตน ให้แน่ใจว่า แต่ละกระบวนการจะต้องให้กระบวนการอื่น ๆ ไปก่อนมากที่สุดหนึ่งครั้งก่อนจะกลายเป็นการเปิดอีกครั้งหมายเหตุว่า คำสั่ง "เปิด = j " คืออะตอม เป็นคำสั่งเครื่องเดียวที่ไม่สามารถขัดจังหวะ6.4 ฮาร์ดแวร์ตรงเม solution(s) ที่แสดงด้านบน แต่ละกระบวนการเมื่อป้อนส่วนที่สำคัญของพวกเขาต้องตั้งค่าบางประเภทของล็อค เพื่อป้องกันไม่ให้ป้อนพร้อมกัน ส่วนสำคัญของกระบวนการอื่น ๆ และต้องปลดล็อกเมื่อ exi

ผลลัพธ์ (ไทย) 3:

กระบวนการการประสาน

อ้างอิง :

อับราฮัม silberschatz เกร็ก กาเย่ และ ปีเตอร์ แบร์ Galvin " แนวคิดของระบบปฏิบัติการรุ่นที่ 8 เตือน บทที่ 6
: บทนี้ต้องมีหนักคิด ในขณะที่คุณอ่านแต่ละอัลกอริทึมที่ด้านล่าง คุณต้องตอบตัวเองว่า พวกเขาจะแน่นอนทำงานภายใต้เงื่อนไขทั้งหมด คิดเกี่ยวกับมัน และไม่เพียงยอมรับพวกเขาที่มูลค่าพื้น



. .จำได้ว่ากลับมาในบทที่ 3 เราจะมองความร่วมมือกระบวนการ ( ผู้ที่ได้ผล หรือได้ผลโดยใช้กระบวนการอื่น ๆพร้อมกัน ) และเป็นตัวอย่าง เราใช้ของผู้บริโภคผู้ผลิตประสานงานกระบวนการผลิตรหัสจากบทที่ 3 :




สินค้า nextproduced ; ในขณะที่ ( จริง ) {

/ * ผลิตและรายการที่จัดเก็บไว้ใน nextproduced * /
nextproduced = makenewitem ( . . . . . . . . )

;/ * รอพื้นที่ที่จะกลายเป็นใช้ได้ * /
ในขณะที่ ( ( ( 1 ) buffer_size ) = = )
; / * ไม่ * /

/ * แล้วเก็บรายการและย้ำห่วง * /
บัฟเฟอร์ [ ] = nextproduced ;
ใน = ( 1 ) buffer_size ;

}

ของรหัสจากบทที่ 3 :

รายการ nextconsumed ;

ในขณะที่ ( จริง ) {

/ * รอสินค้าที่จะกลายเป็นใช้ได้ * /
ในขณะที่ ( = = )
; / * ไม่ * /

/ * รับต่อไปของสินค้า * /
nextconsumed = บัฟเฟอร์ [ ] ;
ออก = ( 1 ) buffer_size ;

/ * บริโภคสินค้าใน nextconsumed
( ทำ ) * /

}

ปัญหาอย่างเดียวกับข้างบนรหัสคือจำนวนสูงสุดของรายการ ซึ่งสามารถวางลงในบัฟเฟอร์ คือ buffer_size - 1 สล็อตหนึ่งไม่สามารถใช้งานได้ เพราะมันมักจะมีช่องว่างระหว่างผู้ผลิตและผู้บริโภค
เราได้พยายามที่จะเอาชนะข้อบกพร่องนี้โดยการแนะนำเคาน์เตอร์ตัวแปรตามที่แสดงในส่วนรหัสต่อไปนี้ :


แต่ตอนนี้เราได้นำปัญหาใหม่เพราะทั้งผู้ผลิตและผู้บริโภคมีการปรับค่าของตัวแปรที่เคาน์เตอร์ ซึ่งจะนำไปสู่ภาวะที่เรียกว่าสภาพการแข่งขัน . ในเงื่อนไขนี้เป็นชิ้นส่วนของรหัสที่อาจหรืออาจไม่ทำงานอย่างถูกต้องซึ่งขึ้นอยู่กับสองพร้อมกันกระบวนการดำเนินการก่อน และที่สำคัญ ถ้าหนึ่งในกระบวนการที่ถูกขัดจังหวะ ซึ่งกระบวนการอื่นที่วิ่งระหว่างขั้นตอนที่สำคัญของกระบวนการก่อน ( เช่น ยอดเงินธนาคารที่กล่าวถึงในชั้นเรียน )
โดยเฉพาะปัญหาดังกล่าวมาจากผู้ผลิต รัน " เคาน์เตอร์ " ในเวลาเดียวกันผู้บริโภคคือการ " ตอบโต้ " . . . .ถ้ากระบวนการที่ได้รับส่วนหนึ่งผ่านทางการ Update แล้วกระบวนการอื่นทุกทีเลย ค่าของตัวนับจะเหลืออยู่ในสถานะที่ไม่ถูกต้อง .
แต่คุณอาจพูดว่า " แต่ละคนเป็นคำสั่งเดียว -- วิธีการที่พวกเขาสามารถได้รับการขัดจังหวะกลางคันผ่าน ? คำตอบคือ แม้ว่าพวกเขาจะเดี่ยว คําแนะนําใน C , พวกเขาเป็นจริงสามขั้นตอนในแต่ละระดับฮาร์ดแวร์ :( 1 ) ดึงนับจากหน่วยความจำในการลงทะเบียน ( 2 ) เพิ่มหรือลดการลงทะเบียน และ ( 3 ) เก็บค่าใหม่ของเคาน์เตอร์คืนหน่วยความจำ ถ้าคําแนะนําจากสองกระบวนการรับอัด อาจมีปัญหาร้ายแรง เช่น ภาพประกอบ โดยต่อไปนี้ :


ออกกำลังกาย : อะไรจะส่งผลให้มูลค่าของเคาน์เตอร์ ถ้าลำดับของงบ T4 T5 และถูกย้อนกลับ ?( สิ่งที่ควรคุณค่า นับเป็นหนึ่งในผู้ผลิตและผู้บริโภคหลังหนึ่ง สมมติว่าค่าเดิมคือ 5 ? )
ประกาศเงื่อนไขการแข่งขันเป็นอย่างฉาวโฉ่ยากที่จะระบุและแก้ปัญหา เพราะโดยธรรมชาติของพวกเขามากพวกเขาเกิดขึ้นเฉพาะในโอกาสที่หายาก และเมื่อถึงเวลาก็ถูกต้อง ( หรือผิด : - ) ) เงื่อนไขการแข่งขันยังยากที่จะทำซ้ำ : - (
เห็นได้ชัดว่าวิธีที่จะเพียง แต่ช่วยให้กระบวนการหนึ่งที่เวลาในการจัดการค่า " เคาน์เตอร์ " นี้เป็นปกติมากที่เกิดขึ้นระหว่างการประสานงานกระบวนการ ดังนั้นให้ดูที่บางวิธีที่ทำ ตลอดจนบางคลาสสิกปัญหาในพื้นที่นี้ .
6.2 มีปัญหา

ส่วนผู้ผลิต ผู้บริโภค ปัญหาที่อธิบายข้างต้นเป็นตัวอย่างที่เฉพาะเจาะจงของสถานการณ์ทั่วไปที่รู้จักกันเป็นปัญหาส่วนวิกฤติ ความคิดทั่วไปคือ ในจํานวนประสานงานกระบวนการ แต่ละส่วนที่สำคัญของรหัสต่อไปนี้ด้วยเงื่อนไขและศัพท์เฉพาะ :
เพียงกระบวนการหนึ่งในกลุ่มจะได้รับอนุญาตให้ดำเนินการในส่วนที่สำคัญของพวกเขาในเวลาใดเวลาหนึ่งถ้ากระบวนการหนึ่งอยู่แล้ว ส่วนการวิจารณ์ของพวกเขาและกระบวนการอื่นที่ประสงค์ที่จะทำเช่นนั้น , แล้วขั้นตอนที่สอง จะต้องให้รอจนกว่าขั้นตอนแรกได้เสร็จสิ้นการทำงานในส่วนของวิกฤติ
รหัสที่มีส่วนสําคัญ ซึ่งการควบคุมการเข้าถึงส่วนที่สำคัญคือ termed ส่วนรายการ มันทำหน้าที่เหมือนประตูล็อค
ควบคุมอย่างระมัดระวัง .รหัสต่อไปนี้ในส่วนที่สำคัญคือส่วนที่เรียกว่า ออกจาก โดยทั่วไปออกล็อคประตูคนอื่น หรืออย่างน้อยก็ช่วยให้โลกรู้ว่า พวกเขาไม่ได้อยู่ในส่วนวิกฤติของ .
ส่วนที่เหลือของรหัสที่ไม่รวมอยู่ในส่วนวิกฤติหรือรายการหรือส่วนทางออกคือ termed

ส่วนเหลือ .การแก้ไขปัญหาส่วนที่สำคัญต้องตอบสนองต่อไปนี้สามเงื่อนไข :
ร่วมกันยกเว้น - เพียงหนึ่งขั้นตอนในเวลาที่สามารถดำเนินการในส่วนที่สำคัญของพวกเขา ถ้าไม่มีกระบวนการ
ความคืบหน้าขณะนี้ดำเนินการในส่วนที่สำคัญของพวกเขาและกระบวนการหนึ่งหรือมากกว่าหนึ่งต้องการที่จะรันส่วนที่สำคัญของพวกเขาจากนั้นเพียงกระบวนการในส่วนที่เหลือของพวกเขาสามารถมีส่วนร่วมในการตัดสินใจและการตัดสินใจจะถูกเลื่อนออกไปอย่างไม่มีกำหนด ( เช่นกระบวนการไม่สามารถถูกบล็อกตลอดกาลรอรับที่เป็นส่วน สำคัญของพวกเขา )
จำกัดรอ - มีอยู่จำกัด เป็นวิธีการหลายขั้นตอนอื่นๆ สามารถเข้าไปในส่วนที่สำคัญของพวกเขาหลังจากกระบวนการบันทึกคำขอในส่วนที่สำคัญของพวกเขาและก่อนที่จะขอ อนุญาต ( เช่น กระบวนการร้องขอเข้าเป็นส่วนสําคัญของพวกเขาจะได้รับการเปิดในที่สุด และมีขีดจำกัดในกระบวนการอื่น ๆ กี่ ออกไปก่อน )
เราคิดว่ากระบวนการทั้งหมดดำเนินการที่ความเร็วที่ไม่ใช่ศูนย์ แต่ไม่สามารถทำให้สมมติฐานเกี่ยวกับความเร็วสัมพัทธ์ของกระบวนการหนึ่งกับอีก กระบวนการ
เมล็ดยังสามารถอยู่ภายใต้สภาวะการแข่งขัน ซึ่งจะเป็นปัญหาอย่างมากเมื่อปรับปรุงเคอร์เนลโครงสร้างข้อมูลที่ใช้ร่วมกันโดยทั่วไป เช่น โต๊ะเปิดแฟ้มหรือการจัดการหน่วยความจำเสมือน ตามเมล็ด สามารถใช้ในหนึ่งในสองรูปแบบ :
ไม่เกิดเมล็ดไม่อนุญาตให้กระบวนการขัดจังหวะ ในขณะที่ในโหมดเคอร์เนล นี้จะช่วยลดความเป็นไปได้ของเคอร์เนลโหมดการแข่งขัน เงื่อนไข แต่ต้องใช้งานโหมดเคอร์เนลที่จะเสร็จสมบูรณ์ได้อย่างรวดเร็วมาก และสามารถเป็นปัญหาสำหรับระบบเรียลไทม์ เพราะไม่สามารถกำหนดเวลาได้ รับประกัน ให้งานเกิดเมล็ด
แบบเรียลไทม์แต่ต้องเขียนอย่างระมัดระวังเพื่อหลีกเลี่ยงเงื่อนไขการแข่งขัน นี้สามารถหากินโดยเฉพาะอย่างยิ่งในระบบ SMP ซึ่งในกระบวนการหลายโปรแกรมอาจจะทำงานพร้อมกันบนโปรเซสเซอร์ที่แตกต่างกัน .
ไม่เกิดเมล็ด รวมถึง Windows XP , 2000 , UNIX และ Linux 2.6 แบบดั้งเดิมก่อนการเกิดเมล็ด ; รวมถึง Linux 2.6 และในภายหลังและการค้าบาง unixes เช่น Solaris และ ไอริกซ์ .
63 Peterson โซลูชั่น

ปีเตอร์สันโซลูชั่นแบบคลาสสิกที่ใช้ซอฟต์แวร์โซลูชั่นเพื่อวิจารณ์ ส่วนปัญหา มันเป็นโชคร้ายที่ไม่ได้รับประกันว่าจะทำงานบนฮาร์ดแวร์ที่ทันสมัย เนื่องจากความไม่แน่นอนของการโหลดและเก็บ แต่มันแสดงให้เห็นถึงจำนวนของแนวคิดที่สำคัญ .
Peterson แก้ปัญหาตามกระบวนการและ 2 P0 P1 ,ซึ่งสลับกันระหว่างส่วนที่สำคัญของตนเอง และส่วนที่เหลือ . เพื่อความสะดวกของการสนทนา , " กระบวนการนี้ " คือ ปี่ และกระบวนการ " อื่น ๆ " คือ เกต ( เช่น J = 1 - I )
Peterson โซลูชั่นต้องใช้สองที่แบ่งปันข้อมูล :
1 เปิดแสดงที่เปลี่ยนมันเข้าไปในส่วนวิกฤติ ถ้าเปิด = = ผม แล้วผมจะอนุญาติให้เข้ากระบวนการส่วนที่สำคัญของพวกเขา .
บูลีนธง [ 2 ] - แสดงเมื่อกระบวนการอยากเข้าไปในส่วนที่สำคัญของพวกเขา เมื่อขั้นตอนที่ฉันต้องการเข้าส่วนที่สำคัญของพวกเขา มันตั้งธง [ i ] จริง .
ในแผนภาพต่อไปนี้ รายการและส่วนทางออกจะอยู่ในกล่อง
ในส่วนของรายการ กระบวนการแรกยกธงแสดงความปรารถนาที่จะระบุส่วนที่สำคัญ .
แล้วเปลี่ยนเป็นชุดเจ เพื่อให้กระบวนการอื่น ๆเพื่อระบุส่วนที่สำคัญของกระบวนการ เจ ถ้าปรารถนา .
ในขณะที่วงเป็นวงๆ ( สังเกตเครื่องหมายอัฒภาคที่สิ้นสุด ) ซึ่งทำให้กระบวนการฉันรอได้นานเท่าที่กระบวนการเจได้เปิดและต้องการระบุส่วนที่สำคัญ .
ผมลดกระบวนการ ธง [ i ] ในส่วนของทางออกที่ช่วยให้กระบวนการเจต่อไปหากได้รับ

รอเพื่อพิสูจน์ว่าวิธีการแก้ปัญหาที่ถูกต้อง เราต้องตรวจสอบเงื่อนไขสามข้างต้น :
ร่วมกันยกเว้นถ้าหนึ่งในกระบวนการดำเนินมาตราการอื่น ๆของพวกเขาเมื่อต้องการทำเช่นนั้น ขั้นตอนที่สองจะกลายเป็นบล็อกโดยธงของกระบวนการก่อน ถ้ากระบวนการทั้งสองพยายามที่จะใส่ในเวลาเดียวกัน ขั้นตอนสุดท้ายที่จะรัน " เปิด =
J " จะถูกปิดกั้นความคืบหน้า - แต่ละขั้นตอนสามารถบล็อก ในขณะถ้ากระบวนการอื่น ๆต้องการใช้ส่วนที่สำคัญ ( ธง [ j ] = = จริง ) และมันอื่น ๆกระบวนการเปิดใช้งานที่สำคัญ ( เปิด = = ; ) ถ้าเงื่อนไขนั้นเป็นจริงแล้วกระบวนการอื่น ( J ) จะได้รับอนุญาตให้เข้าไปในส่วนที่สำคัญ และเมื่อออก ส่วนการจะตั้งธง [ J ] เพื่อเท็จการใช้กระบวนการแปรเปลี่ยนผมมั่นใจว่าเพียงหนึ่งขั้นตอนที่เวลาสามารถบล็อก และธงตัวแปรช่วยให้กระบวนการหนึ่งที่จะปล่อยอื่น ๆ เมื่อออกจากส่วนที่สําคัญของพวกเขา .
จำกัดรอ - แต่ละกระบวนการเข้าสู่ส่วนรายการของพวกเขา พวกเขาตั้งเปลี่ยนแปรเป็น กระบวนการอื่น ๆ เปิด เนื่องจากไม่มีกระบวนการเดิม ชุดมันกลับเปิดของตัวเองนี้ช่วยให้มั่นใจว่า แต่ละขั้นตอนจะต้องให้กระบวนการอื่นไปก่อนมากที่สุดหนึ่งครั้ง ก่อนที่จะเปิดอีกครั้ง .
ทราบว่าการเรียนการสอน " เปิด = J " อะตอม คือว่ามันเป็นเครื่องเดียว การสอนซึ่งไม่สามารถขัดจังหวะ .
4 ประสานฮาร์ดแวร์

generalize ( s ) โซลูชั่น ที่แสดงข้างต้นแต่ละกระบวนการ เมื่อเข้าสู่ส่วนวิกฤตต้องตั้งค่าบางประเภทของล็อคเพื่อป้องกันไม่ให้กระบวนการอื่น ๆ เข้าไป ส่วนวิกฤติของพร้อมกัน และจะปลดล็อคเมื่อ exi