Đồng bộ hóa

Các luồng chia sẻ với nhau cùng một không gian bộ nhớ, nghĩa là chúng có thể chia sè với nhau các tài nguyên. Khi có nhiều hon một luồng cùng muốn sir dụng một tài nguyên sẽ xuất hiện tình trạng câng thẳng, ở đó chi cho phép một luồng được quyền truy cập. Vi dụ, một luồng muốn truy cập vào một biến để đọc dữ liệu, trong khi một luồng khác lại muốn thay đổi biến dữ liệu ở cùng một thời điểm. Để cho các luồng chia sẻ với nhau được các tài nguyên và hoạt động hiệu quà, luôn đảm bão nhất quán dữ liệu thì phài có cơ chế đồng bộ chúng. Java cung cấp cơ chế đồng bộ ờ mức cao để điều khiển truy cập của các luồng vào nhũng tài nguyên dùng chung.

1. Các hàm đồng bộ

Như chúng ta đã biết, khái niệm semaphore (monitor được Tony Hoare đề xuất) thường được sử dụng để điều khiển đồng bộ các hoạt động truy cập vào những tài nguyên dùng chung. Một luồng muốn truy cập vào một tài nguyên dùng chung (như biến dữ liệu) thì trước tiên nó phải yêu cầu để có được monitor riêng. Khi có được monitor thì luồng như có được “chìa khóa” để “mờ cửa” vào miền “tranh chấp” (tài nguyên dùng chung) để sừ dụng những tài nguyên đó.

Cơ chế monitor thực hiện hai nguyên tắc đồng bộ chính:

• Không một luồng nào khác được phân monitor khi có một luồng đã yêu cầu và đang chiếm giữ nó. Những luồng khác yêu cầu monitor sẽ phải chờ cho đến khi monitor được giải phóng.
• Khi có một luồng giải phóng (ra khỏi) monitor, một trong số các luồng đang chờ monitor có thể truy cập vào tài nguyên dùng chung tương ứng với monitor đó.

Mọi đối tượng trong Java đều có monitor, mỗi đối tượng có thể được sử dụng như một khóa loại trừ nhau và cung cấp khả năng đồng bộ truy cập vào những tài nguyên chia sẻ.

Trong lập trinh có hai cách để thực hiện việc đồng bộ:

• Các hàm (phương thức) được đồng bộ
• Các khối được đồng bộ
• Các hàm đồng bộ

Hàm của một lớp chi cho phép một luồng được thực hiện ờ một thời điểm thì nó phài khai báo synchronized, được gọi là hàm đồng bộ. Một luồng muốn gọi để thực hiện một hàm đồng bộ thì nó phải chò để có được monitor của đối tượng có hàm đó. Trong khi một luồng đang thực hiện hàm đồng bộ thì tất cà các luồng khác muốn thực hiện hàm này của cùng một đối tượng, đều phải chò cho đến khi luồng đó thực hiện xong và được giải phóng. Bằng cách đó, những hàm được đồng bộ sẽ không bao giờ bị tắc nghẽn. Những hàm không được đồng bộ cùa đối tượng cỏ thể được gọi thực hiện mọi lúc bời bất kỳ đối tượng nào.

Ví dụ 1.4. Chương trình sau sử dụng Thread để tính tổng các phần tử của một màng.

public class Adder{ public int[] array; private                            int   sum = 0;

private                int   index = 0;

private                int   noOfThread = 10;

private                int   threadQuit;

public Adder(){ threadQuit = 0; array = new int[1000]; initializeArray() ;

startThread();

}

public synchronized int getNextlndex(){ if(index < 1000) return(index++); else return (-1);

}

public synchronized void addPartSum(int s){ sum += s;

if(++threadQuit == noOfThread)

System.out.println(The sum is: “+sum);

}

private void initializeArray(){ int i;

for(i=0; i < 1000; i++) array[i] = i;

}

public void startThread(){ int i;

for(i =0; i < 10; i++){

AdderThread at = new AdderThread(this, i); at.stat ();

}

}

public static void main(String args){

Adder a = new Adder();

}

}

class AdderThread extends Thread{ int s=0;

Adder parent; int num;

Khi chạy, chương trình sẽ thi hành tuần tự các lệnh cho đển khi kết thúc chương trình.

Trong Java, hàm đồng bô có thể khai báo static Các lóp cũng có thể có các monitor tương tự như đối VỚI các đối tượng. Một luồng yêu cầu monitor của lớp trước khi nó có thể thực hiện với một hàm được đồng bộ tĩnh (static) nào đó trong lóp, đồng thời các luồng khác muốn thực hiện những hàm như thế của cùng một lóp thì bị chặn lai

(ii) Các khối đồng bộ

Như trên đã nêu, các hàm đồng bộ của một lóp được đồng bộ dựa vào monitor của đối tượng trong lớp đó. Mặt khác, đồng bộ khối lại cho phép một khối chương trình (một đoan mă lênh) được dồng bộ dựa vào monitor cúa một đối tượng bất kỳ. Đồng bộ khối có dạng như sau:

synchronized (<Tham chiếu đối tượng>) (<khối mã lênh>)}

Khi một luồng muốn vào khối mã lệnh đồng bộ để thực hiện thì nó phải ycu cầu dề có được monitor ờ đối tương tham chiếu, nhũng luồng khác sẽ phái chờ cho đến khi monitor được giải phóng. Ví dụ,

class Client!

BankAccount account;

//…

public void updateTransaction(){

synchronized (account) {                              // (1) Khối đồng bộ

account. update 0 ;                          //(2)

}

}

}

Câu lệnh (2) được đồng bộ trong khối đồng bộ (1) theo đối tượng account của lóp BankAccount. Khi có một số luồng đồng thời muốn thực hiện updateTransaction () dối VỚI một dối tượng của lóp Client thi ờ mồi thời điểm, câu lệnh (2) chì thực hiện được ở một luồng.

2. Sự trao đổi giữa các luồng không đống bộ

Để loại bỏ được sự truy cập đồng thời cùa nhiều luồng vào những đối tượng dùng chung, chúng ta phải biết cách để đồng bộ chúng.

Ví dụ 1.5. Chúng ta hãy xây dựng hệ thống ngân hàng có 10 tài khoản, trong đó có các giao dịch chuyển tiền giữa các tài khoản với nhau môt cách ngẫu nhiên. Chương trình tạo ra 10 luồng cho 10 tài khoản. Mỗi giao dịch được một luồng phục vụ sẽ chuyển một lượng tiền ngẫu nhiên từ một tài khoản sang tài khoản khác.

Chúng ta xây dựng lóp Bank có hàm transfer () để chuyển tiền từ một tài khoản sang tài khoản khác nếu số tiền ở tài khoản gốc còn nhiều tiền hơn số tiền cần chuyển.

startThread();

}

public synchronized int getNextlndex(){ i f ( index < 1000) return(index++) ; else return (-1);

}

public synchronized void addPartSum(int s){ sum += s;

if ( + + threadQuit == noOfThread)

System.out.println(The sum is: “+sum);

}

private void initializeArray(){ int i;

for(i=0; i < 1000; i + +) array[i] = i;

}

public void startThread(){ int i;

for(i = 0; i < 10; Ì++){

AdderThread at = new AdderThread(this, i); at.stat ();

}

}

public static void main(String args){

Adder a = new Adder 0;

}

}

class AdderThread extends Thread{ int s=0;

Adder parent; i nt num;

public AdderThread(Adder parent, int num) { this.parent = parent; this.num = num;

}

public void run(){ int index = 0; while(index != -1){

s += parent.array[index]; index = parent.getNextlndex();

}

System.out.println(“Tồng bộ phận tinh theo luồng

số: ” + num + ” là: ” + s);

}

Khi chạy, chương trình sẽ thi hành tuần tụ các lệnh cho đến khi kểt thúc chương trình.

public void transfer(ìnt from, int to, int amount){ if(accounts[from] < amount) return; accounts[from] -= amount; accounts[to] += amount; numTransacts++;

if(numTransacts % NTEST == 0) test();

}

Sau đó xây dựng lớp Transf erThread, kế thừa lớp Thread và nạp chồng hàm run () để thực hiện Việc chuyển một lượng tiền ngẫu nhiên sang một tài khoản khác cũng ngẫu nhiên.

class TransferThread extends Thread{

// Các thuộc tính public void run(){ try {

while(!interrupted()){

int toAcc = (int) (bank.sizeO * Math.random0 ) ; int amount = (int) (maxAmount * Math.random()); bank.transfer{fromAcc, toAcc, amount); sleep (1);

}

}catch(InterruptedException e){

)

)

)

Chương trình thực hiện 10000 giao dịch, mỗi giao dịch transfer () sẽ gọi hàm test () để tính lại tổng số tiền và in ra màn hình.

Chương trình sẽ chạy liên tục và không dừng. Muốn dừng, bạn hãy nhẩn CTRL + c đề kết thúc chương trình.

// AsynBankTransfer.java

public class AsynBankTransfer{

public static void main(String argil){

Bank b – new Bank(NACCOUNTS, INI_BALANCE); for(int i = 0; 1 < NACCOUNTS; i + +){

TransferThread t = new TransferThread(b, i, INI BALANCE);

t.setPriorityfThread.NORM^PRIORITY + i % 2); t.start ();

}

}

public static final int NACCOUNTS = 10; public static final int INITBALANCE = 10000;

}

class Bank{

public static final int NTEST = 1000; private int[] accounts; private long numTransacts = 0; public Bank(int n, int initBalance){ accounts = new int[n];

for (int i = 0; i < accounts.length; i + +) accounts[i] = initBalance; numTransacts = 0;

public void transfer(int from, int to, int amount)( if(accounts[from] < amount) return; accounts(from] -= amount; accounts[to] += amount; numTransacts++;

if(numTransacts % NTEST == 0) test () ;

}

void test(){

int sum = 0;

for (int i = 0; i < accounts.length; i + +) sum += accounts[i];

System.out.println(“Giao dich: ” + numTransacts

+ ” tong so:           ” + sum);

)

public int size(){

return accounts.length;

}

}

class TransferThread extends Thread{ private Bank bank; private int fromAcc; pr.i va t.e int max Amount;

public TransferThread(Bank b, int from, int max){ bank ■= b; fromAcc = from; maxMount = max ;

}

publi c void run () { try (

whi1e(!interrupted()){

int toAcc = (int) (bank, size 0 * Math. random()) ; int amount – (int) (maxAmount * Math. random () ); bank.transfer(fromAcc, toAcc, amount); sleep(1);

}

}catch(InterruptedException e){

}

}

}

3. Đồng bộ việc truy cập vào các tài nguyên chia sẻ

Chương trình trên thực hiện với 10 luồng hoạt động không đồng bộ để chuyển tiền giữa các tài khoản trong một ngân hàng, vấn đề sẽ nảy sinh khi có hai luồng đồng thời muốn chuyển tiền vào cùng một tài khoản. Giả sử hai luồng cùng thực hiện:

accounts[to] += amount;

Đây không phải là thao tác nguyên tố. Câu lệnh này được thục hiện như sau:

1. Nạp accounts [ to ] vào thanh ghi
2. Cộng số tiền trong tài khoản accounts với amount
3. Lưu lại kết quả cho accounts [to].

Giả sứ có hai tài khoản cùng chuyển tiền vào cùng một tài khoản. Chúng ta có thể giả thiết luồng thứ nhất thực hiện bước 1 và 2 với amount = 500, sau đó nó bị ngắt. Luồng ửiứ hai có thểtiụrc hiện trọn ven cả ba bước trên với amount = ] 000, và luồng thứ nhai kết thúc việc cạp nhật bằng cách thực hiện nốt bước 3. Quá trình này được mô tả như ở hình 1.3.

Kết thúc luồng thứ nhất, accounts (to] có 6000, nhưng ngay sau đó luồng thứ hai kết thúc thì cũng chính tài khoản đó chưa chuyển tiền đi đâu cà, nhưng lại chỉ còn 5500. Trong trường hợp này, ờ tài khoản nhận tiền chuyển đến phải có là 6500 đơn vị tiền mới là chinh xác.

Như vậy, hoạt động giao dịch giữa các tài khoản trong ngân hàng sẽ không còn chính xác, nghĩa là xuất hiện sự sai lệch về dữ liệu, không đảm bảo tính toàn vẹn của dữ liệu. Nhưng, nếu tất cả các luồng cùng thực hiện với cùng một mức ưu tiên thi sẽ rất chậm, bởi vì mỗi luồng sau khi thực hiện “một chút” công việc lại phải đi “ngủ” để các luồng khác thực hiện, rồi lại tiếp tục, v.v.

Các vấn đề trên sẽ được giải quyết khí chúng ta sử dụng cơ chế điều khiển hoạt động của các luồng theo mức ưu tiên và đồng bộ hoá để đảm báo rằng một luồng thực hiện xong việc cập nhật rồi mới trao quyền cho luồng tiếp theo.

Như trên đã nêu, Java sừ dụng cơ chế đồng bộ khá hiệu quả là monitor. Một hàm sẽ không bị ngất nếu bạn khai báo nó là synchronized, như

public synchronized void transfer(int from, int to, int amount) { if(accounts[from] < amount) return; accounts[from] -= amount; accounts[to] += amount; numTransacts++;

if (numTransactS 1 NTEST == 0) test 0;//NTEST-một hằng số

}

public synchronized void test ( ) { int sum = 0;

for(int i = 0; i < accounts.length; i + + ) sum += accounts[i];

System.out.println(“Giao dich: ” + numTransacts

+ ” tong so: ” + sum);

}

Khi có một luồng gọi hàm được đồng bộ thì nó được đảm bảo rằng, hàm này phải thực hiện xong thì luồng khác mới được sứ dụng đối với cùng những tài nguyCn dùng chung dò.

Hoạt động cúa các luồng không đồng bộ và đồng bộ cùa hai luồng thực hiện gọi hàm transfer () được mô tà như hình 1.4.

 

Viết lại chương trinh trên với hai hàm transfer 0, test 0 được khai báo đồng bộ synchronized như trên và chạy thử, chúng ta thấy sẽ không còn xuất hiện sự sai lệch dữ liệu nữa.

Các khóa đối tượng

Khi một luồng gọi một hàm được đồng bộ thì đoi tượng cũa nó bị “khóa”. Chủng ta hình dung như mỗi đối tượng có mọt “chìa khóa” đế mờ của vào “nhà”. Ban đầu chia khóa để ỏ ngoài bậc cửa. Khi một luồng muốn sử dụng một hàm đồng bộ, nó dùng chìa khóa đoi tượng “mớ cừa” đế vào bên trong, đặt chia khóa phía trong “cánh cửa” và thực hiện một số công việc cùa mình. Như vậy, khi một luồng khác muốn gọi hàm đồng bộ cùa cùng đối tượng đó thì sẽ không mở được cừa để vào vùng chung đó vi không có chìa khóa. Sau khi thực hiện xong, luồng ở bên trong giải phóng hàm đồng bộ vừa sữ dụng, ra khỏi đối tượng và đưa chìa khóa ra ngoài bậc cửa để những luồng khác có thể tiếp tục công việc của minh.

Một luồng có thể giữ nhiều khóạ đối tượng ờ cùng một thời điểm, như trong khi đang thực hiện một lòi gọi hàm đồng bộ của một đối tượng, nó lại gọi tiếp hàm đồng bộ cùa đối ‘tượng khác. Nhưng, tại mỗi thời điểm, mỗi khóa đối tượng chi được một luồng sở hữu.

Chúng ta hãy phân tích chi tiết horn hoạt động cùa hệ thống ngân hàng. Một giao dịch chuyển tiền sẽ không thực hiện được nếu không còn đù tiền. Nó phải chờ cho đến khi các tài khoản khác chuyển tiền đến và khi có đù thì mới thực hiện được giao dịch đó.

public synchronized void transfer (int f rem, int to, int amount)! while(accounts[from] < amount) wait ();

// Chuyển tiền

}

Chúng ta sẽ làm gì khi trong tài khoản không co đù tiền? Tất nhiên là phải chờ cho đến khi có đủ tiền trong tài khoản. Nhưng transfer () là hàm được đồng bộ. Do đó, khi một luồng đã chiếm dụng khóa đối tượng thì các luồng khác sẽ không có cơ hội sờ hữu khóa đó, cho đến khi nó được giải phóng.

Khi wait () được gọi ở trong hàm được đồng bộ (như ờ transfer ()), luồng hiện thời sẽ bị chặn lại và trao lại khóa đối tượng cho luồng khác.

Có sự khác nhau thực sự giữa luồng đang chờ để sử dụng hàm đồng bộ với hàm bị chặn lại bới hàm wait (). Khi một luồng gọi wait 0 thì nó được đưa vào danh sách hàng đọi Cho đển khi các luồng chưa được đưa ra khòi danh sách hàng đợi thì bộ lập lịch sẽ bò qua và do vậy chúng không thể tiếp tục được. Để đưa một luồng ra khỏi danh sách hàng đợi thì phải có một luồng khác gọi notify () hoặc notifyAll () trên cùng mật đối tượng.

• notify () đưa một luồng bẩt kỳ ra khỏi danh sách hàng đợi.
• no ti fyAl 1 () đưa tất cả các luồng ra khỏi danh sách hàng đợi.

Những luồng đưa ra khỏi danh sách hàng đợi sê được bộ lập lịch kích hoạt chúng. Ngay tức khắc, luồng nào chiếm được khóa đối tượng thi sẽ bắt đầu thực hiện. Như vậy, trong hàm transfer () chúng ta gọi notifyAll 0 khi kểt thúc việc chuyển tiền để một trong các luồng có thể được tiếp tục thực hiện và tránh bế tắc. Cuối cùng chương trình sừ dụng cơ chế đồng bộ được viết lại như sau.

// SynBankTransfer.java

public class SynBankTransfer{

public static void main(String arg[]){

Bank b = new Bank(NACCOUNTS, INI_BALANCE); forfint i = 0; i < NACCOUNTS; i++){

TransferThread t = new TransferThread (b, i, INI_BAIANCE); t.setPriority(Thread.NORM_PRIORITY + i % 2);

t.start ();

}

}

public static final int NACCOUNTS = 10; public static final int INI_BALANCE = 10000;

} ,

class Bank{

public static final int NTEST = 1000; private int [ ] accounts; private long numTransacts = 0; public Bank(int n, int initBalance){ accounts = new int[n];

for{int i = 0; i < accounts.length; i++) accountsti] = initBalance; numTransacts = 0;

}

public void transfer(int from, int to, int amount) {

while(accounts[from] < amount) wait ();

accounts[from] -= amount;

accounts[to] += amount;

numTransacts++;

notifyAll();

if(numTransacts % NTEST == 0) test();

}

public synchronized void test(){ int sum =0;

for(int i — 0; i < accounts.length; i++) sum += accounts[i];

System.out.printIn(“Giao dich: ” + numTransacts

+ ” tong so: ” + sum);

}

public int size(){

return accounts.length;

}

}

class TransferThread extends Thread{ private Bank bank; private int fromAcc; private int maxAmount;

public TransferThread(Bank b, int from, int max){ bank = b; fromAcc = from; maxAmount = max;

}

public void run(){ try {

while{!interrupted()){

int toAcc = (int) (bank.size 0 * Math.random()); int amount = (int) (maxAmount * Math. random 0) ; bank.transfer(fromAcc, toAcc, amount); sleep (1);

}

}catch (InterruptedException e){

1

}

}

Nếu bạn chạy chương trình với các hàm transfer 0, test () được đồng bộ thi mọi việc sẽ thực hiện chính xác đúng theo yêu cầu. Tuy nhiên, bạn cũng có thể nhận thấy chương trình sẽ chạy chậm hơn chút ít bời vỉ phải ưả giá cho cơ chế đồng bộ nhằm đảm bảo cho hệ thống hoạt động chính xác, đảm bảo nhất quán dữ liệu, hoặc tránh gây ra tắc nghẽn.