Các quá trình trong hệ thống có thể thực thi đồng hành và chúng phải được tạo và xóa tự động. Do đó, hệ điều hành phải cung cấp một cơ chế (hay phương tiện) cho việc tạo quá trình và kết thúc quá trình.
Quá trình có thể tạo nhiều quá trình mới, bằng một lời gọi hệ thống create-process, trong khi thực thi. Quá trình tạo gọi là quá trình cha, ngược lại các quá trình mới được gọi là quá trình con của quá trình đó. Mỗi quá trình mới này sau đó có thể tạo các quá trình khác, hình thành một cây quá trình (hình III-7).  Hình III‑7-Cây quá trình trên một hệ thống UNIX điển hình Thông thường, một quá trình sẽ cần các tài nguyên xác định (như thời gian CPU, bộ nhớ, tập tin, thiết bị nhập/xuất ) để hoàn thành tác vụ của nó. Khi một quá trình tạo một quá trình con, quá trình con có thể nhận tài nguyên của nó trực tiếp từ hệ điều hành hay nó có thể bị ràng buộc tới một tập con các tài nguyên của quá trình cha. Quá trình cha có thể phải phân chia các tài nguyên giữa các quá trình con hay có thể chia sẻ một số tài nguyên (như bộ nhớ và tập tin) giữa nhiều quá trình con. Giới hạn một quá trình con tới một tập con tài nguyên của quá trình cha ngăn chặn bất cứ quá trình từ nạp chồng hệ thống bằng cách tạo quá nhiều quá trình con. Ngoài ra, khi một quá trình được tạo nó lấy tài nguyên vật lý và luận lý khác nhau, dữ liệu khởi tạo (hay nhập) có thể được truyền từ quá trình cha tới quá trình con. Thí dụ, xét một quá trình với toàn bộ chức năng là hiển thị trạng thái của một tập tin F1 trên màn hình. Khi nó được tạo, nó sẽ lấy dữ liệu vào từ quá trình cha, tên của tập tin F1 và nó sẽ thực thi dùng dữ liệu đó để lấy thông tin mong muốn. Nó có thể cũng lấy tên của thiết bị xuất. Một số hệ điều hành chuyển tài nguyên tới quá trình con. Trên hệ thống như thế, quá trình mới có thể lấy hai tập tin đang mở, F1 và thiết bị cuối, và có thể chỉ cần chuyển dữ liệu giữa hai tập tin. Khi một quá trình tạo một quá trình mới, hai khả năng có thể tồn tại trong thuật ngữ của việc thực thi:
Cũng có hai khả năng trong thuật ngữ không gian địa chỉ của quá trình mới:
Để hiển thị việc cài đặt khác nhau này, chúng ta xem xét hệ điều hành UNIX. Trong UNIX, mỗi quá trình được xác định bởi danh biểu quá trình (process identifier), là số nguyên duy nhất. Một quá trình mới được tạo bởi lời gọi hệ thống fork. Quá trình mới chứa bản sao của không gian địa chỉ của quá trình gốc. Cơ chế này cho phép quá trình cha giao tiếp dễ dàng với quá trình con. Cả hai quá trình (cha và con) tiếp tục thực thi tại chỉ thị sau khi lời gọi hệ thống fork, với một sự khác biệt: mã trả về cho lời gọi hệ thống fork là không cho quá trình mới (con), ngược lại danh biểu quá trình (khác không) của quá trình con được trả về tới quá trình cha. Điển hình lời gọi hệ thống execlp được dùng sau lời gọi hệ thống fork bởi một trong hai quá trình để thay thế không gian bộ nhớ với quá trình mới. Lời gọi hệ thống execlp nạp tập tin nhị phân vào trong bộ nhớ-xóa hình ảnh bộ nhớ của chương trình chứa lời gọi hệ thống execlp - và bắt đầu việc thực thi của nó. Trong cách thức này, hai quá trình có thể giao tiếp và sau đó thực hiện cách riêng của nó. Sau đó, quá trình cha có thể tạo nhiều hơn quá trình con, hay nếu nó không làm gì trong thời gian quá trình con chạy thì nó sẽ phát ra lời gọi hệ thống wait để di chuyển nó vào hàng đợi sẳn sàng cho tới khi quá trình con kết thúc. Chương trình C (hình III-8 dưới đây) hiển thị lời gọi hệ thống UNIX được mô tả trước đó. Quá trình cha tạo một quá trình con sử dụng lời gọi hệ thống fork. Bây giờ chúng ta có hai quá trình khác nhau chạy một bản sao của cùng chương trình. Giá trị pid cho quá trình con là 0; cho quá trình cha là một số nguyên lớn hơn 0. Quá trình con phủ lắp không gian địa chỉ của nó với lệnh của UNIX là /bin/ls (được dùng để liệt kê thư mục) dùng lời gọi hệ thống execlp. Quá trình cha chờ cho quá trình con hoàn thành với lời gọi hệ thống wait. Khi quá trình con hoàn thành, quá trình cha bắt đầu lại từ lời gọi hệ thống wait nơi nó hoàn thành việc sử dụng lời gọi hệ thống exit. Ngược lại, hệ điều hành DEC VMS tạo một quá trình mới, nạp chương trình xác định trong quá trình đó và bắt đầu thực thi nó. Hệ điều hành Microsoft Windows NT hỗ trợ cả hai mô hình: không gian địa chỉ của quá trình cha có thể được sao lại hay quá trình cha có thể xác định tên của một chương trình cho hệ điều hành nạp vào không gian địa chỉ của quá trình mới. #include<stdio.h> main(int argc, char* argv[]) { intpid; /*fork another process*/ pid=fork(); if(pid<0){/*error occurred */ fprintf(stderr, “Fork Failed”); exit(-1); } else if (pid==0){/*child process*/ execlp(“/bin/ls”,”ls”,NULL); } else {/*parent process*/ /*parent will wait for the child to complete*/ wait(NULL); printf(“Child Complete”); exit(0); } } Hình III‑8-Chương trình C tạo một quá trình riêng rẻ
Một quá trình kết thúc khi nó hoàn thành việc thực thi câu lệnh cuối cùng và yêu cầu hệ điều hành xóa nó bằng cách sử dụng lời gọi hệ thống exit. Tại thời điểm đó, quá trình có thể trả về dữ liệu (đầu ra) tới quá trình cha (bằng lời gọi hệ thống wait). Tất cả tài nguyên của quá trình –gồm bộ nhớ vật lý và luận lý, các tập tin đang mở, vùng đệm nhập/xuất-được thu hồi bởi hệ điều hành. Việc kết thúc xảy ra trong các trường hợp khác. Một quá trình có thể gây kết thúc một quá trình khác bằng một lời gọi hệ thống hợp lý (thí dụ, abort). Thường chỉ có quá trình cha bị kết thúc có thể gọi lời gọi hệ thống như thế. Ngược lại, người dùng có thể tùy ý giết (kill) mỗi công việc của quá trình còn lại. Do đó, quá trình cha cần biết các định danh của các quá trình con. Vì thế khi một quá trình tạo một quá trình mới, định danh của mỗi quá trình mới được tạo được truyền tới cho quá trình cha. Một quá trình cha có thể kết thúc việc thực thi của một trong những quá trình con với nhiều lý do khác nhau:
Để hiển thị việc thực thi và kết thúc quá trình, xem xét hệ điều hành UNIX chúng ta có thể kết thúc một quá trình dùng lời gọi hệ thống exit; nếu quá trình cha có thể chờ cho đến khi quá trình con kết thúc bằng lời gọi hệ thống wait. Lời gọi hệ thống wait trả về định danh của quá trình con bị kết thúc để quá trình cha có thể xác định những quá trình con nào có thể kết thúc. Tuy nhiên, nếu quá trình cha kết thúc thì tất cả quá trình con của nó được gán như quá trình cha mới của chúng, quá trình khởi tạo (init process). Do đó, các quá trình con chỉ có một quá trình cha để tập hợp trạng thái và thống kê việc thực thi.
Các quá trình đồng hành thực thi trong hệ điều hành có thể là những quá trình độc lập hay những quá trình hợp tác. Một quá trình là độc lập (independent) nếu nó không thể ảnh hưởng hay bị ảnh hưởng bởi các quá trình khác thực thi trong hệ thống. Rõ ràng, bất kỳ một quá trình không chia sẻ bất cứ dữ liệu (tạm thời hay cố định) với quá trình khác là độc lập. Ngược lại, một quá trình là hợp tác (cooperating) nếu nó có thể ảnh hưởng hay bị ảnh hưởng bởi các quá trình khác trong hệ thống. Hay nói cách khác, bất cứ quá trình chia sẻ dữ liệu với quá trình khác là quá trình hợp tác. Chúng ta có thể cung cấp một môi trường cho phép hợp tác quá trình với nhiều lý do:
Thực thi đồng hành của các quá trình hợp tác yêu cầu các cơ chế cho phép các quá trình giao tiếp với các quá trình khác và đồng bộ hóa các hoạt động của chúng. Để minh họa khái niệm của các quá trình cộng tác, chúng ta xem xét bài toán người sản xuất-người tiêu thụ, là mô hình chung cho các quá trình hợp tác. Quá trình người sản xuất cung cấp thông tin được tiêu thụ bởi quá trình người tiêu thụ. Thí dụ, một chương trình in sản xuất các ký tự được tiêu thụ bởi trình điều khiển máy in. Một trình biên dịch có thể sản xuất mã hợp ngữ được tiêu thụ bởi trình hợp ngữ. Sau đó, trình hợp ngữ có sản xuất module đối tượng, được tiêu thụ bởi bộ nạp. Để cho phép người sản xuất và người tiêu thụ chạy đồng hành, chúng ta phải có sẳn một vùng đệm chứa các sản phẩm có thể được điền vào bởi người sản xuất và được lấy đi bởi người tiêu thụ. Người sản xuất có thể sản xuất một sản phẩm trong khi người tiêu thụ đang tiêu thụ một sản phẩm khác. Người sản xuất và người tiêu thụ phải được đồng bộ để mà người tiêu thụ không cố gắng tiêu thụ một sản phẩm mà chưa được sản xuất. Trong trường hợp này, người tiêu thụ phải chờ cho tới khi các sản phẩm mới được tạo ra. Bài toán người sản xuất-người tiêu thụ với vùng đệm không bị giới hạn (unbounded-buffer) thiết lập không giới hạn kích thước của vùng đệm. Người tiêu thụ có thể phải chờ các sản phẩm mới nhưng người sản xuất có thể luôn tạo ra sản phẩm mới. Vấn đề người sản xuất-người tiêu thụ với vùng đệm có kích thước giới hạn (bounded-buffer) đảm bảo một kích thước cố định cho vùng đệm. Trong trường hợp này, người tiêu thụ phải chờ nếu vùng đệm rỗng, và người sản xuất phải chờ nếu vùng đệm đầy. Vùng đệm có thể được cung cấp bởi hệ điều hành thông qua việc sử dụng phương tiện giao tiếp liên quá trình (interprocess-communication-IPC), hay được mã hóa cụ thể bởi người lập trình ứng dụng với việc sử dụng bộ nhớ được chia sẻ. Để chúng ta hiển thị một giải pháp chia sẻ bộ nhớ đối với vấn đề vùng đệm bị giới hạn (bounded-buffer). Quá trình người sản xuất và người tiêu thụ chia sẻ các biến sau: #define BUFFER_SIZE10 typedefstruct{ … } item; item buffer[BUFFER_SIZE]; intin=0; intout=0; Vùng đệm được chia sẻ được cài đặt như một mảng vòng với hai con trỏ luận lý: in và out. Biến in chỉ tới vị trí trống kế tiếp trong vùng đệm; out chỉ tới vị trí đầy đầu tiên trong vùng đệm. Vùng đệm là rỗng khi in==out; vùng đệm là đầy khi ((in + 1)%BUFFER_SIZE) ==out. Mã cho quá trình người sản xuất và người tiêu thụ được trình bày dưới đây. Quá trình người sản xuất có một biến nextProduced trong đó sản phẩm mới được tạo ra và được lưu trữ: while (1) { /*produce an item in nextProduced*/ while (((in + 1)%BUFFER_SIZE) ==out) ; /*do nothing*/ buffer[in]=nextProduced; in=(in + 1) % BUFFER_SIZE; } Quá trình người tiêu thụ có biến cục bộ nextConsumed trong đó sản phẩm được tiêu thụ và được lưu trữ: while (1){ while (in==out) ; //nothing nextConsumed=buffer[out]; out=(out+1)% BUFFER_SIZE; /*consume the item in nextConsumed*/ } Cơ chế này cho phép nhiều nhất BUFFER_SIZE –1 trong vùng đệm tại cùng một thời điểm. Page 2Giải pháp hai quá trình (two-Process Solution) Trong phần này, chúng ta giới hạn việc quan tâm tới những giải thuật có thể áp dụng chỉ hai quá trình cùng một lúc. Những quá trình này được đánh số P0 và P1. Để thuận lợi, khi trình bày Pi, chúng ta dùng Pj để chỉ quá trình còn lại, nghĩa là j = 1 – i
Tiếp cận đầu tiên của chúng ta là để hai quá trình chia sẻ một biến số nguyên chung turn được khởi tạo bằng 0 (hay 1). Nếu turn == 0 thì quá trình Pi được phép thực thi trong vùng tương trục của nó. Cấu trúc của quá trình Pi được hiển thị trong Hình V.-2. Giải pháp này đảm bảo rằng chỉ một quá trình tại một thời điểm có thể ở trong vùng tương trục của nó. Tuy nhiên, nó không thoả mãn yêu cầu tiến trình vì nó yêu cầu sự thay đổi nghiêm khắc của các quá trình trong việc thực thi của vùng tương trục. Thí dụ, nếu turn == 0 và P1 sẳn sàng đi vào vùng tương trục của nó thì P1 không thể đi vào vùng tương trục thậm chí khi P0 đang ở trong phần còn lại của nó.
Vấn đề với giải thuật 1 là nó không giữ lại đủ thông tin về trạng thái của mỗi quá trình; nó nhớ chỉ quá trình nào được phép đi vào miền tương trục. Để giải quyết vấn đề này, chúng ta có thể thay thế biến turn với mảng sau: Boolean flag[2]; Các phần tử của mảng được khởi tạo tới flase. Nếu flag[i] là true, giá trị này hiển thị rằng Pi sẳn sàng đi vào vùng tương trục. Cấu trúc của quá trình Pi được hiển thị trong hình V.-3 dưới đây: flag[i] = true;while (flag[j]);do{critical sectionflag[i] = false;remainder section} while(1); Hình V‑3 –Cấu trúc của quá trình Pi trong giải thuật 2 Trong giải thuật này, quá trình Pi trước tiên thiết lập flag[i] tới true, hiển thị rằng nó sẳn sàng đi vào miền tương trục. Sau đó, Pi kiểm tra rằng quá trình quá trình Pj cũng không sẳn sàng đi vào miền tương trục của nó. Nếu Pj sẳn sàng thì Pi sẽ chờ cho tới khi Pj hiển thị rằng nó không còn cần ở trong vùng tương trục nữa (nghĩa là cho tới khi flag[j] là false). Tại thời điểm này, Pi sẽ đi vào miền tương trục. Thoát ra khỏi miền tương trục, Pi sẽ đặt flag[i] là false, cho phép quá trình khác (nếu nó đang chờ) đi vào miền tương trục của nó. Trong giải pháp này, yêu cầu loại trừ hỗ tương sẽ được thoả mãn. Tuy nhiên, yêu cầu tiến trình không được thoả mãn. Để minh hoạ vấn đề này, chúng ta xem xét thứ tự thực thi sau: T0: P0 thiết lập flag[0] = true; T1: P1 thiết lập flag[1] = true; Bây giờ P0 và P1 được lập mãi mãi trong câu lệnh while tương ứng của chúng. Giải thuật này phụ thuộc chủ yếu vào thời gian chính xác của hai quá trình. Thứ tự này được phát sinh trong môi trường nơi có nhiều bộ xử lý thực thi đồng hành hay nơi một ngắt (chẳng hạn như một ngắt định thời) xảy ra lập tức sau khi bước T0 được thực thi và CPU được chuyển từ một quá trình này tới một quá trình khác. Chú ý rằng chuyển đổi thứ tự của các chỉ thị lệnh để thiết lập flag[i] và kiểm tra giá trị của flag[j] sẽ không giải quyết vấn đề của chúng ta. Hơn nữa chúng ta sẽ có một trường hợp đó là hai quá trình ở trong vùng tương trục cùng một lúc, vi phạm yêu cầu loại trừ hỗ tương.
Giải thuật 3 còn gọi là giải pháp Peterson. Bằng cách kết hợp hai ý tưởng quan trọng trong giải thuật 1 và 2, chúng ta đạt được một giải pháp đúng tới với vấn đề vùng tương trục, ở đó hai yêu cầu được thoả. Các quá trình chia sẻ hai biến: Boolean flag[2] Int turn; Khởi tạo flag[0] = flag[1] = false và giá trị của turn là không xác định (hoặc là 0 hay 1). Cấu trúc của quá trình Pi được hiển thị trong hình sau: do{flag[i] = true;turn = j;while (flag[j] &&turn ==j);critical sectionflag[i] = false;remainder section} while (1); Hình V‑4 Cấu trúc của quá trình Pi trong giải thuật 3 Để đi vào miền tương trục, quá trình Pi trước tiên đặt flag[i] là true sau đó đặt turn tới giá trị j, do đó xác định rằng nếu quá trình khác muốn đi vào miền tương trục nó. Nếu cả hai quá trình đi vào miền tương trục cùng một lúc turn sẽ đặt cả hai i và j tại xấp xỉ cùng một thời điểm. Chỉ một trong hai phép gán này là kết quả cuối cùng. Giá trị cuối cùng của turn quyết định quá trình nào trong hai quá trình được cho phép đi vào miền tương trục trước. Bây giờ chúng ta chứng minh rằng giải pháp này là đúng. Chúng ta cần hiển thị rằng:
Chứng minh thuộc tính 1, chúng ta chú ý rằng mỗi Pi đi vào miền tương trục của nó chỉ nếu flag[j] ==false hay turn ==i. Cũng chú ý rằng, nếu cả hai quá trình có thể đang thực thi trong vùng tương trục của chúng tại cùng thời điểm thì flag[0] == flag[1] ==true. Hai nhận xét này ngụ ý rằng P0 và P1 không thể thực thi thành công trong vòng lặp while của chúng tại cùng một thời điểm vì giá trị turn có thể là 0 hay 1. Do đó, một trong các quá trình-Pj phải được thực thi thành công câu lệnh while, ngược lại Pi phải thực thi ít nhất câu lệnh bổ sung (“turn==j”). Tuy nhiên, vì tại thời điểm đó, flag[j] ==true và turn ==j, và điều kiện này sẽ không đổi với điều kiện là Pj ở trong vùng miền tương trục của nó, kết quả sau việc loại trừ hỗ tương được bảo vệ
Để chứng minh thuộc tính 2 và 3, chúng ta chú ý rằng một quá trình Pi có thể được ngăn chặn từ việc đi vào miền tương truc chỉ nếu nó bị kẹt trong vòng lặp while với điều kiện flag[j] == true và turn == j. Nếu Pj không sẳn sàng đi vào miền tương trục thì flag[j] == false và Pi có thể đi vào miền tương trục của nó. Nếu Pj đặt flag[j] là true và nó cũng đang thực thi trong câu lệnh while của nó thì turn == i hay turn == j. Nếu turn == i thì Pi sẽ đi vào miền tương trục. Nếu turn ==j thì Pj sẽ đi vào miền tương trục. Tuy nhiên, một khi Pj ở trong vùng tương trục của nó thì nó sẽ đặt lại flag[j] tới false, cho phép Pi đi vào miền tương trục của nó. Nếu Pj đặt lại flag[j] tới true, nó cũng phải đặt turn tới i. Do đó, vì Pi không thay đổi giá trị của biến turn trong khi thực thi câu lệnh while, nên Pi sẽ đi vào miền tương trục (tiến trình) sau khi nhiều nhất chỉ Pj đi vào (chờ có giới hạn). Giải pháp nhiều quá trình Giải thuật 3 giải quyết vấn đề miền tương trục cho hai quá trình. Bây giờ chúng ta phát triển một giải thuật để giải quyết vấn đề miền tương trục cho n quá trình. Giải thuật này được gọi là giải thuật Bakery và nó dựa trên cơ sở của giải thuật định thời thường được dùng trong cửa hiệu bánh mì, cửa hàng kem,..nơi mà thứ tự rất hỗn độn. Giải thuật này được phát triển cho môi trường phân tán, nhưng tại thời điểm này chúng ta tập trung chỉ những khía cạnh của giải thuật liên quan tới môi trường tập trung. Đi vào một cửa hàng, mỗi khách hàng nhận một số. Khách hàng với số thấp nhất được phục vụ tiếp theo. Tuy nhiên, giải thuật Bakery không thể đảm bảo hai quá trình (khách hàng) không nhận cùng số. Trong trường hợp ràng buộc, một quá trình với tên thấp được phục vụ trước. Nghĩa là, nếu Pi và Pj nhận cùng một số và nếu (i < j) thì Pi được phục vụ trước. Vì tên quá trình là duy nhất và được xếp thứ tự nên giải thuật là hoàn toàn mang tính “may rủi” (deterministic). Cấu trúc dữ liệu chung là booleanchoosing[n]; intnumber[n]; Đầu tiên, các cấu trúc dữ liệu này được khởi tạo tới false và 0 tương ứng. Để tiện dụng, chúng ta định nghĩa các ký hiệu sau:
Cấu trúc của quá trình Pi được dùng trong giải thuật Bakery, được hiển thị trong hình dưới đây.
Hình V‑6 Cấu trúc của giải thuật Pi trong giải thuật Bakery Kết quả được cho này thể hiện rằng loại trừ hỗ tương được tuân theo. Thật vậy, xét Pi trong vùng tương trục của nó và Pk cố gắng đi vào vùng tương trục Pk. Khi quá trình Pk thực thi câu lệnh while thứ hai cho j==i, nhận thấy rằng
Do đó, nó tiếp tục vòng lặp trong câu lệnh while cho đến khi Pi rời khỏi vùng tương trục Pi. Giải thuật trên đảm bảo rằng yêu cầu về tiến trình, chờ đợi có giới hạn và đảm bảo sự công bằng, vì các quá trình đi vào miền tương trục dựa trên cơ sở tới trước được phục vụ trước. Phần cứng đồng bộ hoá Như các khía cạnh khác của phần mềm, các đặc điểm phần cứng có thể làm các tác vụ lập trình dễ hơn và cải tiến tính hiệu quả của hệ thống. Trong phần này, chúng ta trình bày một số chỉ thị phần cứng đơn giản sẳn dùng trên nhiều hệ thống và trình bày cách chúng được dùng hiệu quả trong việc giải quyết vấn đề miền tương trục. boolean TestAndSet( boolean &target){boolean rv = target;target = true;returnrv;} Hình V‑7 Định nghĩa của chỉ thị TestAndSet Vấn đề miền tương trục có thể được giải quyết đơn giản trong môi trường chỉ có một bộ xử lý nếu chúng ta cấm các ngắt xảy ra khi một biến chia sẻ đang được thay đổi. Trong cách này, chúng ta đảm bảo rằng chuỗi chỉ thị hiện hành có thể được cho phép thực thi trong thứ tự không trưng dụng. Không có chỉ thị nào khác có thể chạy vì thế không có bất cứ sự thay đổi nào có thể được thực hiện trên các biến được chia sẻ. Tuy nhiên, giải pháp này là không khả thi trong một môi trường có nhiều bộ xử lý. Vô hiệu hoá các ngắt trên đa bộ xử lý có thể mất nhiều thời gian khi một thông điệp muốn truyền qua tất cả bộ xử lý. Việc truyền thông điệp này bị trì hoãn khi đi vào miền tương trục và tính hiệu quả của hệ thống bị giảm. Do đó nhiều máy cung cấp các chỉ thị phần cứng cho phép chúng ta kiểm tra hay thay đổi nội dung của một từ (word) hay để thay đổi nội dung của hai từ tuân theo tính nguyên tử (atomically)-như là một đơn vị không thể ngắt. Chúng ta có thể sử dụng các chỉ thị đặc biệt này để giải quyết vấn đề miền tương trục trong một cách tương đối đơn giản. Chỉ thị TestAndSet có thể được định nghĩa như trong hình V.-7. Đặc điểm quan trọng của chỉ thị này là việc thực thi có tính nguyên tử. Do đó, nếu hai chỉ thị TestAndSet được thực thi cùng một lúc (mỗi chỉ thị trên một CPU khác nhau), thì chúng sẽ được thực thi tuần tự trong thứ tự bất kỳ.
Hình V‑8: Cài đặt loại trừ hỗ tương với TestAndSet Nếu một máy hỗ trợ chỉ thị TestAndSet thì chúng ta có thể loại trừ hỗ tương bằng cách khai báo một biến khoá kiểu luận lý và được khởi tạo tới false. Cấu trúc của quá trình Pi được hiển thị trong hình V.-9 ở trên. Chỉ thị Swap được định như hình V.-9 dưới đây, thao tác trên nội dung của hai từ; như chỉ thị TestAndSet, nó được thực thi theo tính nguyên tử. void Swap(boolean &a, boolean &b){ boolean temp = a; a = b; b = temp; } Hình V‑9: Định nghĩa chỉ thị Swap Nếu một máy hỗ trợ chỉ thị Swap, thì việc loại trừ hỗ tương có thể được cung cấp như sau. Một biến luận lý toàn cục lock được khai báo và được khởi tạo tới false. Ngoài ra, mỗi quá trình cũng có một biến luận lý cục bộ key. Cấu trúc của quá trình Pi được hiển thị trong hình V.-10 dưới đây.
Hình V‑10: Cài đặt loại trừ hỗ tương với chỉ thị Swap Các giải thuật này không thoả mãn yêu cầu chờ đợi có giới hạn. Chúng ta hiển thị giải thuật sử dụng chỉ thị TestAndSet trong hình V.-11 dưới đây. Giải thuật này thoả mãn tất cả các yêu cầu miền tương trục.
Hình V‑11 Loại trừ hỗ tương chờ đợi có giới hạn với TestAndSet Cấu trúc dữ liệu thông thường là: boolean waiting[n]; booleanlock; Cấu trúc dữ liệu này được khởi tạo tới false. Để chứng minh rằng loại trừ hỗ tương được thoả, chúng ta chú ý rằng quá trình Pi có thể đưa vào miền tương trục chỉ nếu hoặc waiting[i] ==false hay key == false. Giá trị của key có thể trở thành false chỉ nếu TestAndSet được thực thi. Đối với quá trình đầu tiên, để thực thi TestAndSet sẽ tìm key == false; tất cả quá trình khác phải chờ. Biến waiting[i] có thể trở thành false chỉ nếu quá trình khác rời khởi miền tương trục của nó; chỉ một waiting[i] được đặt false, duy trì yêu cầu loại trừ hỗ tương. Để chứng minh yêu cầu tiến trình được thoả, chúng ta chú ý rằng các đối số được hiện diện cho việc loại trừ hỗ tương cũng áp dụng được ở đây, vì thế một quá trình thoát khỏi miền tương trục hoặc đặt lock bằng false hay đặt waiting[j] bằng false. Cả hai trường hợp đều cho phép một quá trình đang chờ để đi vào miền tương trục được xử lý. Để chứng minh yêu cầu chờ đợi được giới hạn được thoả, chúng ta chú ý rằng khi một quá trình rời miền tương trục của nó, nó duyệt qua mảng waiting trong thứ tự tuần hoàn (i + 1, i + 2, …, n – 1, 0, …, i - 1). Nó định rõ quá trình đầu tiên trong thứ tự này mà thứ tự đó ở trong phần đi vào (waiting[j] == true) khi quá trình tiếp theo đi vào miền tương trục. Bất cứ quá trình nào đang chờ để đi vào miền tương trục sẽ thực hiện n – 1 lần. Tuy nhiên, đối với người thiết kế phần cứng, cài đặt các chỉ thị nguyên tử TestAndSet trên bộ đa xử lý không là tác vụ thử nghiệm. Những giải pháp trên đều phải thực hiện một vòng lặp để kiểm tra liệu nó có được phép vào miền tương trục hay không. Nếu điều kiện chưa thoả, quá trình phải chờ tiếp tục trong vòng lặp kiểm tra này. Các giải pháp buộc quá trình phải liên tục kiểm tra điều kiện để phát hiện thời điểm thích hợp được vào miền tương trục như thế được gọi là các giải pháp chờ đợi bận “busy waiting”. Lưu ý, việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy quá trình đang chờ vẫn chiếm dụng CPU. Xu hướng giải quyết vấn đề đồng bộ hoá là nên tránh các giải pháp chờ đợi bận. |
