Chủ Nhật, 28 tháng 2, 2010

Con quỷ Toán học làm thay đổi thế giới

Câu nói nổi tiếng của Isaac Newton, “Nếu tôi nhìn được xa hơn, ấy là vì tôi đứng trên vai những người khổng lồ”, đã tạo cảm hứng cho Melvyn Bragg viết cuốn “On Giants’ Shoulders” – một cuốn sách được tờ The Times ở Anh bình luận là đã “bỏ bùa mê … và mở toang kho báu khoa học của Aladin cho mọi độc giả”. Trong số 12 nhân vật “đứng trên vai những người khổng lồ” được Bragg liệt kê để viết tiểu sử, có 3 và chỉ 3 nhân vật vừa là nhà toán học vừa là nhà vật lý: Archimedes,  Isaac Newton, và Henri Poincaré.

Nói chính xác hơn, đó là ba “nhà đại quảng bác” (universalists), riêng Poincaré được gọi là “nhà đại quảng bác cuối cùng” (the last universalist). Đó là những nhà đại bác học có những khám phá phi thường bao trùm lên hết thẩy mọi lĩnh vực của toán học và vật lý đương thời, mở ra những chân trời mới cho khoa học để hậu thế tiếp tục khai phá.

Không thể kể hết những lời ngợi ca mà người đời đã dành cho họ.

Archimedes từng được nhà bác học trứ danh Galileo Galilei ca ngợi là “thần thánh” (divine), rồi thốt lên: “Không có Archimedes thì tôi sẽ chẳng làm nên trò trống gì!”.

Newton thì được nhà thơ Alexander Pope ngợi ca bằng hai câu thơ bất hủ, viết theo thể “Sáng thế ký” trong Kinh Thánh:

“Nature and Nature’s laws lay hid in night

God said “Let Newton be”, and all was light” 

Xin tạm dịch:

“Thiên nhiên và quy luật của Tự nhiên,

Lâu nay vẫn ẩn mình trong đêm tối,
Chúa phán “New-ton hãy ra đời”,
Và thế là khắp thế gian bừng sáng”. 

Còn Poincaré thì sao? Ông có được ngợi ca như “thần thánh” không? Thế kỷ 19 không sùng bái thần thánh nữa, vì thế Poincaré “bị” gọi là “con quỷ toán học”, nhưng … “con quỷ” ấy đã làm thay đổi thế giới!

1. “Con quỷ toán học” làm thay đổi thế giới:


Khiếp sợ trước khả năng phi thường của cậu học trò Poincaré, một thầy giáo dạy toán tại Trường trung học Nancy (Lycée de Nancy, nay là Lycée Henri Poincaré) là Carta de Elliot ở Liard đã gọi cậu là “con quỷ toán học”. Năm 1872, trong một thư gửi cho một người bạn, thầy Elliot viết: “Trong lớp của tôi ở Nancy, có một con quỷ toán học, đó là Henri Poincaré” (J’ai dans ma classe à Nancy, un monstre de mathématiques, c’est Henri Poincaré).

Và “cậu bé bị thầy của mình gọi là con quỷ toán học ấy đã chứng minh rằng cậu đúng là như thế: Cậu đã biến đổi nền toán học trong phần còn lại của thế kỷ 20”, Bragg đã viết về Poincaré như vậy.
Nhận định của Bragg hoàn toàn chính xác, nhưng chưa đầy đủ, bởi vì, cùng với những người khổng lồ khác như Max Planck, Albert Einstein, … Poincaré còn làm thay đổi cả vật lý trong phần còn lại của thế kỷ 20.

Có thể nhiều người đến nay vẫn chưa biết rằng Poincaré đã 51 lần được đề cử nhận Giải Nobel vật lý. Xin chú ý: Giải Nobel đầu tiên diễn ra vào năm 1901. Poincaré mất năm 1912. Vậy trong 12 năm, ông được đề cử 51 lần, trung bình mỗi năm có hơn 4 đề cử !

Nhưng tại sao ông chưa một lần đoạt giải Nobel?

Đơn giản vì trong số những đóng góp lớn nhất của Poincaré cho vật lý, có những tư tưởng vượt quá xa thời đại, đến nỗi Uỷ ban Nobel cũng chưa thể đánh giá hết được ý nghĩa của nó, hoặc vì họ thận trọng không muốn mắc sai lầm. Thí dụ điển hình là Thuyết tương đối hẹp (Special Theory of Relativity). Giả sử vì một lẽ gì đó, Uỷ ban Nobel nhận thấy “muộn còn hơn không bao giờ”, rồi quyết định trao Giải Nobel vật lý cho lý thuyết này thì sao nhỉ? Khi ấy, những người xứng đáng được nhận giải có lẽ sẽ không chỉ có một mình Einstein, mà còn phải bao gồm một số người khác, đặc biệt là Hendrik Lorentz và Henri Poincaré – hai trong số những người đi tiên phong trong tư tưởng về tương đối tính và đã “dọn đường” cho Einstein đi tới đích cuối cùng. Vấn đề này sẽ được trình bầy kỹ ở mục 4*.

Một bằng chứng khác là Lý thuyết hỗn độn (Theory of Chaos). Mặc dù phải đợi tới những năm 1960-1970, lý thuyết này mới xuất đầu lộ diện như một lý thuyết khoa học hoàn toàn mới, nhưng nguyên lý cơ bản của nó đã được Poincaré khám phá ra ngay từ tháng 11 năm 1890, khi ông công bố lời giải của “Bài toán ba vật thể” (Problème à Trois Corps)(1) trên tạp chí Acta Mathematica.

Và thiết tưởng, nếu không có Lý thuyết topo (Topology) thì không biết toán học và vật lý học ngày nay sẽ ra sao. Vậy mà Poincaré lại chính là cha đẻ của Topo đại số. Trong lĩnh vực này, Giả thuyết Poincaré (Poincaré Conjecture) đã đứng sừng sững trong suốt một thế kỷ qua như một trong những thách thức lớn nhất đối với các nhà toán học, để mãi đến năm 2006 mới được giải quyết trọn vẹn bởi nhà toán học Grigori Perelman, và sự kiện này đã trở thành đột phá của khoa học năm 2006. 

Không kể rất nhiều công trình nghiên cứu sâu sắc khác trong toán học và vật lý, chỉ riêng đóng góp của Poincaré đối với ba lý thuyết khổng lồ nói trên cũng đã quá đủ để nói lên tầm vóc khổng lồ của ông.

Nhưng sẽ là một thiếu sót lớn nếu nghĩ rằng “con quỷ toán học” chỉ nghiên cứu khoa học thuần tuý: Poincaré đồng thời còn là một nhà triết học thâm thuý, một nhà tư tưởng có tầm nhìn xa trông rộng.

2.  Poincaré, nhà tư tưởng nhìn xa trông rộng:

Một sinh viên của Poincaré viết về thầy của mình: “Poincaré luôn kết thúc buổi giảng bằng những công thức đơn giản, được diễn giải bằng một thứ ngôn ngữ đầy hình ảnh đến nỗi buộc chúng tôi phải hiểu”. Nhận xét ngắn ngủi này phản ánh chính xác tư tưởng và tính cách của Poincaré: Đối với ông, toán học phải sinh động, giầu hình ảnh, đầy cảm nhận trực giác, mặc dù bề ngoài của nó là những ký hiệu và các phương trình. Ký hiệu hay phương trình chỉ là công cụ để thể hiện một tư tưởng, không được phép biến thành một thứ ngôn ngữ chết, một chuỗi suy diễn logic máy móc, vô hồn vô cảm. Điều này giải thích vì sao Poincaré quyết liệt chống đối chủ nghĩa toán học hình thức ngay từ buổi trứng nước của nó.
Thật vậy, đầu thế kỷ 20, bất chấp đa số các nhà toán học lao theo con đường do David Hilbert vạch ra, dồn mọi nỗ lực vào việc tìm kiếm Chiếc Chén Thánh Toán Học (The Holy Grail of Mathematics)(2), hòng biến toán học thành một hệ thống logic hình thức thuần tuý, hoàn toàn tách rời khỏi hiện thực, không đếm xỉa tới trực giác, Poincaré vẫn ung dung đi trên con đường riêng của mình và không ngừng cảnh báo chủ nghĩa hình thức về sai lầm của họ: “Nhà toán học xa rời thực tiễn giống như một hoạ sĩ bị tước đi vật mẫu”. Lời cảnh báo bất hủ ấy đã nhanh chóng được kiểm chứng:

Năm 1902, Bertrand Russell, một nhà tiên phong trong cuộc hành trình tìm kiếm Chiếc Chén Thánh, trớ trêu thay, lại khám phá ra một nghịch lý của chính logic hình thức, Nghịch lý Russell(3), cho thấy chủ nghĩa logic hình thức giống như con rắn tự nuốt đuôi của mình. Không giấu được vẻ giễu cợt, Poincaré nói: “Cuối cùng thì chủ nghĩa logic cũng đã chứng minh được rằng nó không hoàn toàn vô ích. Rốt cuộc nó cũng sinh đẻ được, nhưng lại đẻ ra một nghịch lý”. Bất chấp sự khác biệt về lý tưởng toán học, Russell vẫn khảng khái nhận định: “Poincaré là người có tài trí khoa học vĩ đại nhất đang còn sống” (Poincaré was the greatest scientific mind then living).

Năm 1931, Định lý Godel ra đời, xác nhận chủ nghĩa hình thức quả thật là một ảo tưởng, do đó Poincaré quả thật là người nhìn xa trông rộng!



Tuy nhiên không phải mọi điều đã được hiểu đúng ngay từ những năm 1930. Bằng chứng là chủ nghĩa hình thức vẫn còn giương cao ngọn cờ “toán học mới” để tấn công ồ ạt vào hệ thống giáo dục phổ thông ở tây phương những năm 1960. Phải đợi tới những thập kỷ cuối thế kỷ 20 mọi điều mới tỏ rõ. Giống như sau một cơn bão, khi bình yên trở lại trên đống hoang tàn, người ta mới nghiệm ra rằng quả thật Poincaré sâu sắc, và thế là dấy lên một trào lưu “đọc lại” những tác phẩm của ông:

· “Science et hypothèse” (Khoa học và giả thuyết, ra mắt năm 1902),

· “La valeur de la science” (Giá trị của khoa học, 1905),

· “Science et méthode” (Khoa học và phương pháp, 1908),

· “Savants et écrivains” (Nhà bác học và nhà văn, 1910),

Đó là những tác phẩm triết luận sâu sắc, hùng hồn, hấp dẫn, đến nỗi Poincaré được đánh giá như một nhà triết luận tài ba, và đã trở thành nhà khoa học đầu tiên được bầu vào Viện hàn lâm văn chương Pháp (Académie Francaise). Đáng tiếc là chưa có một tác phẩm nào nói trên được dịch ra tiếng Việt. Điều này cũng dễ hiểu: Sự chậm trễ của người Việt chúng ta chỉ là tấm gương phản chiếu sự chậm trễ trên toàn cầu.

Nhưng thế giới đã thức tỉnh, và khi tỉnh dậy, người ta ngạc nhiên chứng kiến một Poincaré luôn luôn có mặt trên tuyến đầu của tất cả các cuộc cách mạng lớn nhất về nhận thức trong thế kỷ 20, từ “cuộc cách mạng về tương đối tính” đến cuộc cách mạng về bất định, ngẫu nhiên và hỗn độn: Lời giải “Bài toán ba vật thể” của Poincaré chính là ánh chớp đầu tiên báo hiệu cuộc cách mạng tư tưởng sâu sắc nhất sắp xẩy ra trong thế kỷ 20:

Cuộc chuyển dịch của nhận thức từ xác định sang bất định.

3. Từ xác định tới bất định:

Trước thế kỷ 20, tư tưởng thống trị trong khoa học là chủ nghĩa tất định (determinism) – chủ nghĩa cho rằng vũ trụ vận hành theo những quy luật xác định và tất yếu như một chiếc đồng hồ. Từ thế kỷ 17 trở về sau, chiếc đồng hồ ấy được mệnh danh là “chiếc đồng hồ Newton” (Newtonian clock), bởi vì với cơ học Newton, người ta có thể xác định được tương lai hoặc quá khứ của vũ trụ nếu biết rõ trạng thái của nó tại một thời điểm cho trước. Nhà toán học Pierre Simon Laplace giải thích: “Chúng ta có thể coi trạng thái hiện tại của vũ trụ như hậu quả của quá khứ và là nguyên nhân của tương lai … và trước con mắt của một người trí thức, chẳng có gì là bất định cả, tương lai cũng như quá khứ sẽ chỉ là hiện tại mà thôi”. Đó là “Tất định luận Laplace” (Laplace’s determinism). Tất định luận này ăn sâu vào tâm trí các nhà khoa học đến nỗi Louis Lagrange, nhà toán học lỗi lạc cuối thế kỷ 18 đầu thế kỷ 19, phải buồn rầu than thở: “Newton đã tìm ra hết mọi bí mật rồi, chẳng còn gì cho chúng ta làm nữa”. Dù cho vật lý thế kỷ 19 được bổ sung bởi Lý thuyết điện từ của James Clerk Maxwell, nhưng lý thuyết này hoàn toàn nhất quán với cơ học Newton để tạo nên một hệ thống lý thuyết hoàn toàn xác định và chắc chắn, làm nền tảng cho mọi hiểu biết về vũ trụ, đến nỗi nhiều người nghĩ rằng khoa học đã tiệm cận tới những trang cuối cùng. Nhưng …..

Lạ thay, cuối thế kỷ 19 đầu thế kỷ 20, những tư tưởng hoàn toàn mới đã nẩy mầm trên mọi lĩnh vực của nhận thức: Tư tưởng về cái bất định, bất toàn, ngẫu nhiên, hỗn độn – những cái không chắc chắn và không thể dự đoán trước (unpredictable)(4). Tư tưởng ấy bộc lộ trong hội hoạ của Paul Cézanne và Pablo Picasso, … trong bộ tiểu thuyết vĩ đại “À la recherche du temps perdu” (Đi tìm thời đã mất) của Marcel Proust, … và trong một loạt lý thuyết khoa học hoàn toàn “đảo lộn” sau đây:


· Nguyên lý bất định của Heisenberg trong cơ học lượng tử, ra đời năm 1921. Lý thuyết này đã dẫn tới cuộc xung đột “xác định vs bất định” giữa hai biểu tượng vĩ đại của vật lý thế kỷ 20: Albert Einstein, “nhà vật lý cổ điển cuối cùng”, và Niels Bohr, nhà phát ngôn và lãnh tụ triết học của cơ học lượng tử. Nếu hiểu hết mọi nhẽ mà Bohr đã nêu lên để bác bỏ quan điểm xác định cổ điển cuả Einstein thì khi đó người ta sẽ hiểu rõ bất định lượng tử là gì, và tại sao Bohr được coi là “vị trưởng lão quyết đoán” tương ứng với vị trí (-1) trên trục số, trong khi Einstein tương ứng vị trí zero(5).

· Định lý bất toàn của Kurt Godel. Khi định lý này mới ra đời năm 1931, trừ một vài người thấy giật mình đến mức phải thay đổi định hướng nghiên cứu toán học, điển hình là John von Newman(6), đa số vẫn “phớt lờ” để tiếp tục tôn thờ chủ nghĩa hình thức. Nhưng càng ngày người ta càng nhận thấy ý nghĩa vĩ đại của định lý này: Trong toán học tồn tại những mệnh đề không quyết định được (undecidable) – những mệnh đề không thể chứng minh và không thể bác bỏ. Hoá ra toán học cũng không tuyệt đối chắc chắn như người ta tưởng. Greg Chaitin sau này còn đi xa hơn khi chứng minh rằng yếu tố ngẫu nhiên và bất định nằm ngay trong nền tảng của số học(7).

· Lý thuyết hỗn độn mà Henri Poincaré là người đặt nền móng. So với Nguyên lý bất định của Heisenberg và Định lý bất toàn của Godel, tư tưởng về cái hỗn độn ra đời sớm hơn rất nhiều – ngay từ năm 1890 khi Poincaré công bố lời giải “Bài toán ba vật thể”, trong đó ông mô tả:

“Khi tôi cố gắng mô tả hình ảnh được tạo ra bởi hai đường cong này và vô số giao điểm của chúng, … những giao điểm này tạo nên một mạng lưới, một mớ lằng nhằng hoặc một cạm bẫy vô cùng rắc rối. Tôi hết sức kinh hoàng vì tính phức tạp của hình ảnh này đến nỗi tôi không cố sức để vẽ nó ra nữa”.


Năm 1908 ông giải thích vấn đề này rõ hơn:

“Một nguyên nhân rất nhỏ mà chúng ta không nhận thấy có thể dẫn tới một hậu quả lớn đến mức không thể đoán trước, và vì thế chúng ta bảo rằng hậu quả này xẩy ra do ngẫu nhiên … Có thể xẩy ra trường hợp những khác biệt vô cùng nhỏ trong dữ kiện ban đầu dẫn tới những hậu quả vô cùng lớn trong hiện tượng sau cùng. Một sai lệch nhỏ ban đầu có thể gây ra một sai lệch khổng lồ trong kết quả. Dự đoán trở nên bất khả, và chúng ta có một hiện tượng ngẫu nhiên” (trích Science et méthode).

Đó chính là tuyên ngôn mở đầu về những hiện tượng không thể dự đoán trước. Lần đầu tiên trong khoa học, bản chất ngẫu nhiên đã được đề cập. Lần đầu tiên tư tưởng tất định từng ngự trị trong hàng trăm năm trước, ít nhất kể từ thời Newton, đã bị nghi vấn. Lần đầu tiên lời than vãn của Lagrange đã bị chứng minh là sai. Đó là cuộc cách mạng đầu tiên về cái ngẫu nhiên, bất định, và hỗn độn trong thế kỷ 20!

Melvyn Bragg viết: Poincaré là “người tình cờ khám phá ra tính hỗn độn”, nhưng đó là sự tình cờ vĩ đại chỉ xẩy ra ở những bộ óc vĩ đại!

4. Giả thuyết Poincaré :

Năm 2000, Viện toán học Clay ở Mỹ nêu lên danh sách 7 bài toán khó nhất của thiên niên kỷ thứ hai (từ năm 1001-2000) và treo giải thưởng 1 triệu USD cho mỗi bài toán. Giả thuyết Poincaré (GP) do Poincaré nêu lên từ năm 1904 là một trong số 7 bài toán đó.

Thông thường, bài toán tổng quát trong không gian n chiều là bài toán khó nhất, nhưng kỳ lạ thay, lịch sử giải quyết GP lại rất “ngược đời”:

· Năm 1966, Stephen Smale đoạt Giải Fields (giải thưởng danh giá nhất trong toán học, được xem như Giải Nobel toán học) vì đã chứng minh được GP trong trường hợp n = 5 và n > 5.

· Trong những năm 1970, William Thurston đoạt Giải Fields vì chứng minh được một tính chất đặc biệt của các đa tạp 3 chiều và chứng minh này được coi là một đóng góp lớn vào việc chứng minh GP.

· Năm 1982, Michel Friedman đoạt Giải Fields vì chứng minh được GP đúng với n = 4.

· Tháng 11-2002, Grigori Perelman, tiến sĩ thuộc Viện toán học Steklov ở St Petersburg, Nga, bắt đầu công bố các chứng minh của ông trên internet, gây nên một cuộc xáo động chưa từng có trong thế giới toán học, kể từ sau cuộc xáo động do Andrew Wiles gây ra khi công bố chứng minh Định lý cuối cùng của Fermat. Tháng 04-2003, Perelman tới thăm Viện công nghệ Massachusetts (MIT), Đại học Princeton, Đại học tiểu bang New York ở Stony Brook, Đại học Columbia, và Đại học New York, để trao đổi với các đồng nghiệp và thực hiện các cuộc thuyết trình chuyên môn. Ba nhóm học giả độc lập đã được thành lập để nhận định công trình của Perelman. Trong khi chờ đợi sự đánh giá, Perelman từ chối trả lời mọi câu hỏi của báo chí, làm cho cả thế giới phải nín thở để theo dõi. Không khí căng thẳng này làm người ta nhớ đến khung cảnh năm 1993, khi Andrew Wiles lần đầu tiên trình bầy chứng minh Định lý cuối cùng của Fermat tại Đại học Princeton. Lần ấy, chính Wiles đã phát hiện ra sai lầm của mình, và phải mất hơn một năm trời để sửa chữa chứng minh rồi mới đi đến thắng lợi. Có vẻ như Perelman đã học được bài học đó. Điều lý thú là cả Wiles lẫn Perelman đều đơn thương độc mã đương đầu với một thách thức thuộc tầm cỡ ghê gớm nhất đối với bộ não của con người: Wiles mất 7 năm cho bài toán Fermat, Perelman mất 8 năm cho bài toán Poincaré. Cuối cùng, tháng 05-2006, Liên đoàn toán học quốc tế thừa nhận chứng minh của Perelman là đúng và quyết định trao tặng Perelman Giải Fields. Đồng thời, Perelman cũng đoạt Giải Thiên Niên Kỷ (Millennium Prize) của Viện Clay. Nhưng ông từ chối mọi giải thưởng. Đó là chuyện lạ chưa từng có! Phải chăng Perelman muốn thể hiện sự khinh rẻ đối với bả vinh hoa + danh vọng + tiền tài? Phải chăng ông muốn đề cao CÁI ĐẸP như chính Poincaré đã từng đề cao:

“Nhà khoa học không nghiên cứu tự nhiên vì việc đó có ích; Anh ta nghiên cứu nó vì anh ta thấy thích thú và anh ta thấy thích thú vì nó đẹp. Nếu tự nhiên không đẹp thì nó không đáng để biết, và cuộc sống không đáng để sống”.



Nhưng dù Perelman nghĩ gì thì người đời cũng vẫn phải nghiêng mình bái phục ông. Nhà toán học lỗi lạc Đào Triết Hiên (Terence Tao), người hiện nay được mệnh danh là “Mozart của toán học” (danh hiệu trước đây dành cho Poincaré), đã không tiếc lời ca tụng:

“Những bài toán thiên niên kỷ giống như những vách đá thẳng đứng bên bờ biển, không có chỗ bám víu. Tôi không biết làm thế nào mà có thể leo lên tới đỉnh. Theo ý kiến của tôi, đối với tất cả chúng ta có mặt ở đây, chứng minh Giả thuyết Poincaré của Perelman là một thành tựu kỳ vĩ, xứng đáng nhất để trao giải thưởng … chứng minh của Perelman thật sự là một loạt các đột phá…”.

Với 4 Giải Fields đã đoạt được, lời giải của Giả thuyết Poincaré đã chiếm kỷ lục về số giải thưởng cao quý nhất mà một bài toán có thể đạt được. Nói cách khác, nó cũng chiếm kỷ lục về sự tiêu hao năng lượng của những bộ óc vĩ đại nhất thế kỷ 20. Điều đó thiết tưởng đã quá đủ để nói lên tầm vóc của tác giả giả thuyết đó.

5. Poincaré và Thuyết tương đối hẹp:

Vốn ngưỡng mộ Einstein, năm 2005 tôi thật sự bị choáng khi đọc bài báo “Anhxtanh, thiên tài đạo văn?” trên tạp chí Khoa học & công nghệ số 1-2005. Thoạt nhìn đầu đề bài báo, tôi có cảm giác khó chịu, nhưng ngay sau khi đọc xong, tôi thấy cần tìm hiểu sự thật một cách kỹ lưỡng, vì bài báo được viết theo những nguồn thông tin nghiêm túc.

Điều kỳ lạ là xung quanh hai khám phá lớn nhất của Einstein đều xẩy ra những chuyện rắc rối liên quan đến quyền tác giả.

Chẳng hạn, theo cuốn “Phương trình của Chúa” (God’s Equation) của Amir Aczel, đã có một cuộc tranh chấp giữa Einstein và David Hilbert, một nhà toán học lớn cùng thời, về quyền tác giả đối với Phương trình trường trong Thuyết tương đối tổng quát(9). Một uỷ ban đã được thành lập để giải quyết cuộc tranh chấp này, nhưng phải đợi mãi đến cuối năm 1997, sau khi nhiều văn khố lưu trữ chưa từng biết về Einstein được công bố, thì mới có kết luận chung quyết: Quyền tác giả Phương trình trường thuộc về Einstein.

Đối với Thuyết tương đối hẹp thì sao?
 

Không có vấn đề tranh quyền tác giả ở đây, nhưng trớ trêu thay, “Năm vật lý Einstein 2005”, năm kỷ niệm Thuyết tương đối hẹp tròn 100 tuổi, đã trở thành dịp phơi bầy ra nhiều sự thật trước đây ít được biết, gây nên tranh cãi lớn xung quanh câu hỏi ai là tác giả thật sự của Thuyết tương đối hẹp.

Thực ra sự chia rẽ quan điểm đã có từ lâu, nhưng nhờ internet, việc tự do ngôn luận đã bùng nổ thành một cuộc tranh cãi lớn trên toàn cầu, trong đó nổi lên ba nhóm ý kiến:

· Nhóm 1 gồm những người đề cao đóng góp của những người đi trước Einstein về tương đối tính. Điển hình là Edmund Whittaker, tác giả cuốn “Một lịch sử về lý thuyết ê-te và điện” (A History of the Theories of Aether and Electricity), trong đó nói rằng Thuyết tương đối hẹp là đóng góp chủ yếu của Lorentz và Poincaré, còn Einstein chỉ là người mở rộng thêm vấn đề(10).

· Nhóm 2 gồm những người mắc bệnh sùng bái Einstein, coi Einstein như “ông thánh khoa học” và do đó cho rằng Thuyết tương đối hẹp chỉ có thể là sản phẩm của một bộ óc phi thường duy nhất – bộ óc Einstein. Điển hình cho nhóm này là Amir Aczel, tác giả cuốn “Phương trình của Chúa” đã nói ở trên.


· Nhóm 3 gồm những người có thái độ khách quan tôn trọng sự thật. Đó là thái độ khoa học chân chính. Một trong những nhân vật điển hình của nhóm này là Max Born, nhà vật lý đoạt Giải Nobel năm 1954, một người bạn của Einstein, và cũng là người nổi tiếng chính trực.


Theo một bài báo trên tạp chí NEXUS tập 11, số 1, thì trong cuốn “Physics in My Generation” (Vật lý trong thế hệ của tôi) của Max Born, do Pergamon Press xuất bản tại London năm 1956, trang 193, Born viết:

“Thêm một nét đặc biệt khác thường nữa của công trình hiện nay đang nổi tiếng, công trình của Einstein năm 1905, là sự vắng mặt của bất kỳ một tham khảo nào về Poincaré hoặc về bất kỳ ai khác. Điều đó gây cho bạn ấn tượng rằng đây là một cuộc mạo hiểm hoàn toàn mới. Nhưng tất nhiên, như tôi đã cố gắng giải thích, điều đó không đúng sự thật”.

Có lẽ đây chính là nguyên nhân làm cho nhiều người nghĩ rằng Thuyết tương đối hẹp chỉ có thể là sản phẩm của một bộ óc thiên tài duy nhất. Nhưng may thay, chính Einstein đã sửa chữa sự hiểu lầm đó: Hai năm trước khi mất, tức năm 1953, ông gửi thư cho ban tổ chức kỷ niệm lần thứ 50 ngày ra đời Thuyết tương đối hẹp sẽ tổ chức vào năm 1955, trong đó viết:

“Tôi hy vọng chúng ta cũng sẽ quan tâm tới việc vinh danh thích đáng công lao của Lorentz và Poincaré vào dịp đó”.

Đó là đảm bảo bằng vàng đối với công lao của Lorentz và Poincaré!

Công lao ấy đã được làm sáng tỏ trong bài báo “Ai phát minh ra Thuyết tương đối?” (Who Invented Relativity?) của Hermann Weyl, một trong những nhà toán học và vật lý xuất sắc nhất thế kỷ 20. Weyl mở đầu:

“Mọi sự khởi đầu đều không rõ ràng”, rồi ông viết tiếp:

“Một trong những khía cạnh lịch sử thú vị của thuyết tương đối hiện đại là ở chỗ, mặc dù nó thường được xem như một đóng góp cực kỳ độc đáo và cách mạng của một cá nhân duy nhất, nhưng hầu hết mọi tư tưởng và sự trình bầy của lý thuyết này đã được những người khác nói từ trước. Chẳng hạn, cả phương trình hiệp biến Lorentz (Lorentz covariance) lẫn quán tính của năng lượng đều đã ngầm chứa trong các phương trình Maxwell. Cũng vậy, năm 1887 Voigt đã rút ra những phép biến đổi Lorentz một cách hình thức dựa trên những khảo sát tổng quát đối với phương trình sóng. Vào những năm 1890, trong phạm vi điện-động-lực-học, Fitzgerald, Larmor, và Lorentz, tất cả đều đã đi tới những phép biến đổi Lorentz, bao gồm tất cả những hiệu ứng khác thường gắn liền với Thuyết tương đối hẹp của Einstein như hiện tượng dãn thời gian và co độ dài. Năm 1905, Poincaré đã phát biểu rõ ràng nguyên lý tương đối và nhiều hệ quả của nó, đã chỉ ra sự thiếu cơ sở thực tiễn của tính đồng thời tuyệt đối (absolute simultaneity), đã thách thức ý nghĩa bản chất của ê-te, và đã chứng minh rằng những phép biến đổi Lorentz chứa một nhóm biến đổi có ý nghĩa giống như các phép biến đổi Galileo”.

Sau khi đề cập đến việc so sánh Einstein với Copernicus, Weyl cho rằng việc so sánh đó là đúng, rồi ông phân tích tiếp:

“Chỉ những người kế tiếp như Kepler, Galileo, và Newton, nhờ đào xới những hiểu biết của Copernicus đến mức sâu sắc hơn chính Copernicus đã làm thì mới thực sự tạo ra được một lý thuyết vật lý mới lạ về chất. Rõ ràng là Copernicus chỉ là một trong số nhiều người tập hợp lại để cùng tạo nên cuộc cách mạng Copernicus trong khoa học, và chúng ta có thể lập luận tương tự rằng Einstein cũng chỉ là một trong số những cá nhân bao gồm cả Maxwell, Lorentz, Poincaré, Planck và Minkowski cùng có trọng trách đối với cuộc cách mạng về tương đối tính”.

“Trong những năm cuối đời Einstein nhận xét rằng không nghi ngờ gì nữa Thuyết tương đối hẹp, nếu đánh giá sự phát triển của nó trong sự hồi tưởng quá khứ, là đã chín muồi để được khám phá ra trong năm 1905. Cùng với Lorentz, người tiến gần nhất tới việc khám phá ra thuyết tương đối hẹp trước Einstein chắc chắn là Poincaré, người đã đề xuất trong năm 1900 một định nghĩa rõ ràng thích hợp về tính đồng bộ hoá của đồng hồ và năm 1904 đã gợi ý rằng ê-te về nguyên tắc là không thể phát hiện được … Hai đề xuất đó và những hệ quả của chúng về cơ bản đã là hiện thân của toàn bộ Thuyết tương đối hẹp”.


Trong thời đại thông tin ngày nay, quan điểm của Weyl đã đến với mọi người, và được nhiều học giả thể hiện sự đồng thuận.

Chẳng hạn bài báo “Poincaré contemplates Copernicus”(11) (Poincaré suy ngẫm về Copernicus) viết: “Hai công trình của Poincaré năm 1905 cùng với những công trình của ông trước đó đã mô tả một cách rõ ràng một lý thuyết về tương đối tính, ngay cả khi nó không giống với lý thuyết của Einstein trong mọi khía cạnh triết học”.

Sau đó bài báo trích dẫn lời của chính Poincaré viết năm 1905 (trước khi Einstein công bố công trình của ông về tương đối hẹp), rằng:

“Dường như việc không thể phát hiện được chuyển động tuyệt đối trên trái đất bằng thí nghiệm có thể là một định luật tổng quát của tự nhiên; Một cách tự nhiên chúng ta có khuynh hướng thừa nhận định luật này, mà chúng ta gọi là Tiên đề về tính tương đối và thừa nhận vô giới hạn. Tiên đề này đến nay vẫn phù hợp với thực nghiệm, nhưng dù cho sau này nó có thể được xác nhận thêm hoặc bị bác bỏ bởi những thí nghiệm chính xác hơn, thì trong mọi trường hợp, việc tìm hiểu những hệ quả của nó vẫn rất thú vị”.

Một bài báo khác nhan đề “Relativity” (Thuyết tương đối) trên trang mạng “How it works”(12) viết: “Thuyết tương đối hẹp được phát triển một cách độc lập bởi Henri Poincaré tại Paris và Albert Einstein tại Zürich … Henri Poincaré là người khởi đầu thật sự của thuyết tương đối”. Theo bài báo này thì chính Poincaré chứ không phải ai khác đã là người đầu tiên gieo thuật ngữ “relativité” (tương đối tính) vào thế giới khoa học, và cũng chính Poincaré chứ không phải ai khác đã là người đầu tiên nêu lên hệ quả của tính tương đối, rằng không có cái gì có thể chuyển động nhanh hơn ánh sáng. Đó chính là một tiên đề cơ bản của Thuyết tương đối hẹp. Nhưng cũng chính Einstein chứ không phải ai khác đã có công giải đáp những nghịch lý về ê-te do Lorentz và Poincaré khám phá ra. Nói cách khác, Einstein đã đẩy tư tưởng của Lorentz và Poincaré tới bước quyết định mang tính cách mạng.

6. Lời kết:

Trở về chủ đề “đứng trên vai những người khổng lồ”, xin thưa, thực ra đó là một lối nói ẩn dụ đã lưu truyền trong nền văn hoá Tây phương từ xa xưa, nguyên văn tiếng La-tinh là “Nanos gigantum humeris insidentes”, tức “Những chú lùn đứng trên vai những người khổng lồ”.

Tuy nhiên, những người như Newton, Einstein, Poincaré không phải là “những chú lùn”, mà là những người khổng lồ đứng trên vai những người khổng lồ. Vì thế tầm nhìn của họ quá xa, quá rộng, đến nỗi không dễ gì có thể hiểu hết những điều họ nghĩ trong một thời gian ngắn.

Nhưng dường như chưa bao giờ bức chân dung Poincaré hiện ra rõ rệt như hiện nay, khi những dịp kỷ niệm lớn về ông đang tới:

· Năm 2010 là dịp kỷ niệm 120 năm ngày ra đời của tư tưởng về cái hỗn độn – ngày công bố lời giải của Poincaré đối với “Bài toán Ba Vật Thể”.

· Năm 2012 sẽ là dịp kỷ niệm tròn 100 năm ngày mất của Poincaré. Điều này gợi nhớ tới ý kiến của nhà toán học Jean Mawhin tại Viện quốc tế Solvay về vật lý và hoá học ở Brussels, Bỉ, viết năm 2004, nhân kỷ niệm 150 năm ngày sinh của Poincaré:

“Năm 1954, cộng đồng khoa học kỷ niệm 100 năm ngày sinh của Poincaré. Tại thời điểm đó, danh tiếng của Poincaré không nằm ở vị trí cao nhất trong số các nhà toán học, (vì) tinh thần Hilbert đang thống trị trong phần lớn tư duy toán học. Đó cũng không phải là điểm cao nhất của Poincaré trong vật lý, vì vật lý đang quan tâm chủ yếu đến lý thuyết lượng tử. (Nhưng) bất chấp điều đó, lễ kỷ niệm vẫn rất quan trọng trong những lĩnh vực mà sự hiện diện hoặc tên tuổi của Poincaré có ý nghĩa, và nội dung của những lĩnh vực đó đã được công bố trong một Cuốn Sách Vàng (Golden Book), được tái bản trong tập cuối của bộ sách Công trình khoa học của Poincaré. Năm nay chúng ta kỷ niệm tròn 150 năm ngày sinh của Poincaré, sự nổi tiếng của Poincaré đã đạt tới những đỉnh cao mới trong thế giới khoa học, thậm chí đối với cả những người không làm khoa học. Lý thuyết hỗn độn và nguồn gốc của Thuyết tương đối đã đưa tên tuổi và chân dung của Poincaré lên các tạp chí khoa học nổi tiếng nhất”.

(Vnmath.com & Vietsciences)

Thứ Sáu, 26 tháng 2, 2010

BÀI 5 : CÁC GIẢI PHÁP ĐỒNG BỘ HOÁ

Bài học này sẽ giới thiệu các giải pháp cụ thể để xử lý bài toán đồng bộ hoá. Có nhiều giải pháp để thực hiện việc truy xuất miền găng, các giải pháp này được phân biệt thành hai lớp tùy theo cách tiếp cận trong xử lý của tiến trình bị khóa :các giải pháp « busy waiting » và các giải pháp « sleep and wakeup ».

   I.1. Các giải pháp phần mềm
I.1.1. Sử dụng các biến cờ hiệu:
Tiếp cân : các tiến trình chia sẻ một biến chung đóng vai trò « chốt cửa » (lock) , biến này được khởi động là 0. Một tiến trình muốn vào miền găng trước tiên phải kiểm tra giá trị của biến lock. Nếu lock = 0, tiến trình đặt lại giá trị cho lock = 1 và đi vào miền găng. Nếu lock đang nhận giá trị 1, tiến trình phải chờ bên ngoài miền găng cho đến khi lock có giá trị 0. Như vậy giá trị 0 của lock mang ý nghĩa là không có tiến trình nào đang ở trong miền găng, và lock=1 khi có một tiến trình đang ở trong miền găng.
while (TRUE) {
while (lock == 1); // wait
lock = 1;
critical-section ();
lock = 0;
Noncritical-section ();
}
Hình 3.5 Cấu trúc một chương trình sử dụng biến khóa để đồng bộ
Thảo luận : Giải pháp này có thể vi phạm điều kiện thứ nhất: hai tiến trình có thể cùng ở trong miền găng tại một thời điểm. Giả sử một tiến trình nhận thấy lock = 0 và chuẩn bị vào miền găng, nhưng trước khi nó có thể đặt lại giá trị cho lock là 1, nó bị tạm dừng để một tiến trình khác hoạt động. Tiến trình thứ hai này thấy lock vẫn là 0 thì vào miền găng và đặt lại lock = 1. Sau đó tiến trình thứ nhất được tái kích hoạt, nó gán lock = 1 lần nữa rồi vaò miền găng. Như vậy tại thời điểm đó cả hai tiến trình đều ở trong miền găng.
I.1.2. Sử dụng việc kiểm tra luân phiên :
Tiếp cận : Đây là một giải pháp đề nghị cho hai tiến trình. Hai tiến trình này sử dụng chung biến turn (phản ánh phiên tiến trình nào được vào miền găng), được khởi động với giá trị 0. Nếu turn = 0, tiến trình A được vào miền găng. Nếu turn = 1, tiến trình A đi vào một vòng lặp chờ đến khi turn nhận giá trị 0. Khi tiến trình A rời khỏi miền găng, nó đặt giá trị turn về 1 để cho phép tiến trình B đi vào miền găng.
while (TRUE) {
while (turn != 0); // wait
critical-section ();
turn = 1;
Noncritical-section ();
}
(a) Cấu trúc tiến trình A
while (TRUE) {
while (turn != 1); // wait
critical-section ();
turn = 0;
Noncritical-section ();
}
(b) Cấu trúc tiến trình B
Hình 3.6 Cấu trúc các tiến trình trong giải pháp kiểm tra luân phiên
Thảo luận: Giải pháp này dựa trên việc thực hiện sự kiểm tra nghiêm nhặt đến lượt tiến trình nào được vào miền găng. Do đó nó có thể ngăn chặn được tình trạng hai tiến trình cùng vào miền găng, nhưng lại có thể vi phạm điều kiện thứ ba: một tiến trình có thể bị ngăn chặn vào miền găng bởi một tiến trình khác không ở trong miền găng. Giả sử tiến trình B ra khỏi miền găng rất nhanh chóng. Cả hai tiến trình đều ở ngoài miền găng, và turn = 0. Tiến trình A vào miền găng và ra khỏi nhanh chóng, đặt lại giá trị của turn là1, rồi lại xử lý đoạn lệnh ngoài miền găng lần nữa. Sau đó, tiến trình A lại kết thúc nhanh chóng đoạn lệnh ngoài miền găng của nó và muốn vào miền găng một lần nữa. Tuy nhiên lúc này B vẫn còn mãi xử lý đoạn lệnh ngoài miền găng của mình, và turn lại mang giá trị 1 ! Như vậy, giải pháp này không có giá trị khi có sự khác biệt lớn về tốc độ thực hiện của hai tiến trình, nó vi phạm cả điều kiện thứ hai.
I.1.3. Giải pháp của Peterson
Tiếp cận : Petson đưa ra một giải pháp kết hợp ý tưởng của cả hai giải pháp kể trên. Các tiến trình chia sẻ hai biến chung :
int turn; // đến phiên ai
int interesse[2]; // khởi động là FALSE
Nếu interesse[i] = TRUE có nghĩa là tiến trình Pi muốn vào miền găng. Khởi đầu, interesse[0]=interesse[1]=FALSE và giá trị của est được khởi động là 0 hay 1. Để có thể vào được miền găng, trước tiên tiến trình Pi đặt giá trị interesse[i]=TRUE ( xác định rằng tiến trình muốn vào miền găng), sau đó đặt turn=j (đề nghị thử tiến trình khác vào miền găng). Nếu tiến trình Pj không quan tâm đến việc vào miền găng (interesse[j]=FALSE), thì Pi có thể vào miền găng, nếu không, Pi phải chờ đến khi interesse[j]=FALSE. Khi tiến trình Pi rời khỏi miền găng, nó đặt lại giá trị cho interesse[i]= FALSE.
while (TRUE) {
int j = 1-i; // j là tiến trình còn lại
interesse[i]= TRUE;
turn = j;
while (turn == j && interesse[j]==TRUE);
critical-section ();
interesse[i] = FALSE;
Noncritical-section ();
}
Hình 3.7 Cấu trúc tiến trình Pi trong giải pháp Peterson
Thảo luận: giải pháp này ngăn chặn được tình trạng mâu thuẫn truy xuất : mỗi tiến trình Pi chỉ có thể vào miền găng khi interesse[j]=FALSE hoặc turn = i. Nếu cả hai tiến trình đều muốn vào miền găng thì interesse[i] = interesse[j] =TRUE nhưng giá trị của turn chỉ có thể hoặc là 0 hoặc là 1, do vậy chỉ có một tiến trình được vào miền găng.

I.2.1. Cấm ngắt:
Tiếp cân: cho phép tiến trình cấm tất cả các ngắt trước khi vào miền găng, và phục hồi ngắt khi ra khỏi miền găng. Khi đó, ngắt đồng hồ cũng không xảy ra, do vậy hệ thống không thể tạm dừng hoạt động của tiến trình đang xử lý để cấp phát CPU cho tiến trình khác, nhờ đó tiến trình hiện hành yên tâm thao tác trên miền găng mà không sợ bị tiến trình nào khác tranh chấp.
Thảo luận: giải pháp này không được ưa chuộng vì rất thiếu thận trọng khi cho phép tiến trình người dùng được phép thực hiện lệnh cấm ngắt. Hơn nữa, nếu hệ thống có nhiều bộ xử lý, lệnh cấm ngắt chỉ có tác dụng trên bộ xử lý đang xử lý tiến trình, còn các tiến trình hoạt động trên các bộ xử lý khác vẫn có thể truy xuất đến miền găng !
I.2.2. Chỉ thị TSL (Test-and-Set):
Tiếp cận: đây là một giải pháp đòi hỏi sự trợ giúp của cơ chế phần cứng. Nhiều máy tính cung cấp một chỉ thị đặc biệt cho phép kiểm tra và cập nhật nội dung một vùng nhớ trong một thao tác không thể phân chia, gọi là chỉ thị Test-and-Set Lock (TSL) và được định nghĩa như sau:
Test-and-Setlock(boolean target)
{
Test-and-Setlock = target;
target = TRUE;
}
Nếu có hai chỉ thị TSL xử lý đồng thời (trên hai bộ xử lý khác nhau), chúng sẽ được xử lý tuần tự . Có thể cài đặt giải pháp truy xuất độc quyền với TSL bằng cách sử dụng thêm một biến lock, được khởi gán là FALSE. Tiến trình phải kiểm tra giá trị của biến lock trước khi vào miền găng, nếu lock = FALSE, tiến trình có thể vào miền găng.
while (TRUE) {
while (Test-and-Setlock(lock));
critical-section ();
lock = FALSE;
Noncritical-section ();
}
Hình 3.8 Cấu trúc một chương trình trong giải pháp TSL
Thảo luận : cũng giống như các giải pháp phần cứng khác, chỉ thị TSL giảm nhẹ công việc lập trình để giải quyết vấn để, nhưng lại không dễ dàng để cài đặt chỉ thị TSL sao cho được xử lý một cách không thể phân chia, nhất là trên máy với cấu hình nhiều bộ xử lý.
    Tất cả các giải pháp trên đây đề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 găng, nếu điều kiện chưa cho phép, tiến 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 tiến 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 găng như thế được gọi các giải pháp « busy waiting ». Lưu ý rằng việc kiểm tra như thế tiêu thụ rất nhiều thời gian sử dụng CPU, do vậy tiến 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 « busy waiting ».

Để loại bỏ các bất tiện của giải pháp « busy waiting », chúng ta có thể tiếp cận theo hướng cho một tiến trình chưa đủ điều kiện vào miền găng chuyển sang trạng thái blocked, từ bỏ quyền sử dụng CPU. Để thực hiện điều này, cần phải sử dụng các thủ tục do hệ điều hành cung cấp để thay đổi trạng thái tiến trình. Hai thủ tục cơ bản SLEEPWAKEUP thường được sử dụng để phục vụ mục đích này.
SLEEP là một lời gọi hệ thống có tác dụng tạm dừng hoạt động của tiến trình (blocked) gọi nó và chờ đến khi được một tiến trình khác « đánh thức ». Lời gọi hệ thống WAKEUP nhận một tham số duy nhất : tiến trình sẽ được tái kích hoạt (đặt về trạng thái ready).
Ý tưởng sử dụng SLEEP và WAKEUP như sau : khi một tiến trình chưa đủ điều kiện vào miền găng, nó gọi SLEEP để tự khóa đến khi có một tiến trình khác gọi WAKEUP để giải phóng cho nó. Một tiến trình gọi WAKEUP khi ra khỏi miền găng để đánh thức một tiến trình đang chờ, tạo cơ hội cho tiến trình này vào miền găng :
int busy;   // 1 nếu miền găng đang bị chiếm, nếu không là 0 int blocked;   // đếm số lượng tiến trình đang bị khóa

while (TRUE) {
if (busy){
    blocked = blocked + 1;
    sleep();
}
else busy = 1;

critical-section ();

busy = 0;
if(blocked){
    wakeup(process);
    blocked = blocked - 1;
}

Noncritical-section ();
}
Hình 3.9 Cấu trúc chương trình trong giải pháp SLEEP and WAKEUP
Khi sử dụng SLEEP và WAKEUP cần hết sức cẩn thận, nếu không muốn xảy ra tình trạng mâu thuẫn truy xuất trong một vài tình huống đặc biệt như sau : giả sử tiến trình A vào miền găng, và trước khi nó rời khỏi miền găng thì tiến trình B được kích hoạt. Tiến trình B thử vào miền găng nhưng nó nhận thấy A đang ở trong đó, do vậy B tăng giá trị biến blocked và chuẩn bị gọi SLEEP để tự khoá. Tuy nhiên trước khi B có thể thực hiện SLEEP, tiến trình A lại được tái kích hoạt và ra khỏi miền găng. Khi ra khỏi miền găng A nhận thấy có một tiến trình đang chờ (blocked=1) nên gọi WAKEUP và giảm giá trị của blocked. Khi đó tín hiệu WAKEUP sẽ lạc mất do tiến trình B chưa thật sự « ngủ » để nhận tín hiệu đánh thức !Khi tiến trình B được tiếp tục xử lý, nó mới goi SLEEP và tự khó vĩnh viễn !
Vấn đề ghi nhận được là tình trạng lỗi này xảy ra do việc kiểm tra tư cách vào miền găng và việc gọi SLEEP hay WAKEUP là những hành động tách biệ, có thể bị ngắt nửa chừng trong quá trình xử lý, do đó có khi tín hiệu WAKEUP gởi đến một tiến trình chưa bị khóa sẽ lạc mất.
Để tránh những tình huống tương tự, hệ điều hành cung cấp những cơ chế đồng bộ hóa dựa trên ý tưởng của chiến lược « SLEEP and WAKEUP » nhưng được xây dựng bao hàm cả phương tiện kiểm tra điều kiện vào miền găng giúp sử dụng an toàn.
Tiếp cận: Được Dijkstra đề xuất vào 1965, một semaphore s là một biến có các thuộc tính sau:
Một giá trị nguyên dương e(s)
Một hàng đợi f(s) lưu danh sách các tiến trình đang bị khóa (chờ) trên semaphore s
Chỉ có hai thao tác được định nghĩa trên semaphore
Down(s): giảm giá trị của semaphore s đi 1 đơn vị nếu semaphore có trị e(s) > 0, và tiếp tục xử lý. Ngược lại, nếu e(s) £ 0, tiến trình phải chờ đến khi e(s) >0.
Up(s): tăng giá trị của semaphore s lên 1 đơn vị. Nếu có một hoặc nhiều tiến trình đang chờ trên semaphore s, bị khóa bởi thao tác Down, thì hệ thống sẽ chọn một trong các tiến trình này để kết thúc thao tác Down và cho tiếp tục xử lý.

Hình 3.10 Semaphore s
Cài đặt: Gọi p là tiến trình thực hiện thao tác Down(s) hay Up(s).
Down(s):
e(s) = e(s) - 1;
if e(s) < 0 {
status(P)= blocked;
enter(P,f(s));
}
Up(s):
e(s) = e(s) + 1;
if s £ 0 {
exit(Q,f(s)); //Q là tiến trình đang chờ trên s
status (Q) = ready;
enter(Q,ready-list);
}
Lưu ý cài đặt này có thể đưa đến một giá trị âm cho semaphore, khi đó trị tuyệt đối của semaphore cho biết số tiến trình đang chờ trên semaphore.
Điều quan trọng là các thao tác này cần thực hiện một cách không bị phân chia, không bị ngắt nữa chừng, có nghĩa là không một tiến trình nào được phép truy xuất đến semaphore nếu tiến trình đang thao tác trên semaphore này chưa kết thúc xử lý hay chuyển sang trạng thái blocked.
Sử dụng: có thể dùng semaphore để giải quyết vấn đề truy xuất độc quyền hay tổ chức phối hợp giữa các tiến trình.
Tổ chức truy xuất độc quyền với Semaphores: khái niệm semaphore cho phép bảo đảm nhiều tiến trình cùng truy xuất đến miền găng mà không có sự mâu thuẫn truy xuất. n tiến trình cùng sử dụng một semaphore s, e(s) được khởi gán là 1. Để thực hiện đồng bộ hóa, tất cả các tiến trình cần phải áp dụng cùng cấu trúc chương trình sau đây:
while (TRUE) {
Down(s)
critical-section ();
Up(s)
Noncritical-section ();
}
Hình 3.11 Cấu trúc một chương trình trong giải pháp semaphore
Tổ chức đồng bộ hóa với Semaphores: với semaphore có thể đồng bộ hóa hoạt động của hai tiến trình trong tình huống một tiến trình phải đợi một tiến trình khác hoàn tất thao tác nào đó mới có thể bắt đầu hay tiếp tục xử lý. Hai tiến trình chia sẻ một semaphore s, khởi gán e(s) là 0. Cả hai tiến trình có cấu trúc như sau:
P1:
while (TRUE) {
job1();
Up(s); //đánh thức P2
}
P2:
while (TRUE) {
Down(s); // chờ P1
job2();
}
Hình 3.12 Cấu trúc chương trình trong giải pháp semaphore

Thảo luận : Nhờ có thực hiện một các không thể phân chia, semaphore đã giải quyết được vấn đề tín hiệu "đánh thức" bị thất lạc. Tuy nhiên, nếu lập trình viên vô tình đặt các primitive Down Up sai vị trí, thứ tự trong chương trình, thì tiến trình có thể bị khóa vĩnh viễn.
Ví dụ : while (TRUE) {
Down(s)
critical-section ();
Noncritical-section ();

}
tiến trình trên đây quên gọi Up(s), và kết quả là khi ra khỏi miền găng nó sẽ không cho tiến trình khác vào miền găng !
Vì thế việc sử dụng đúng cách semaphore để đồng bộ hóa phụ thuộc hoàn toàn vào lập trình viên và đòi hỏi lập trình viên phải hết sức thận trọng.
Tiếp cận: Để có thể dễ viết đúng các chương trình đồng bộ hóa hơn, Hoare(1974) và Brinch & Hansen (1975) đã đề nghị một cơ chế cao hơn được cung cấp bởi ngôn ngữ lập trình , là monitor. Monitor là một cấu trúc đặc biệt bao gồm các thủ tục, các biến và cấu trúc dữ liệu có các thuộc tính sau :
Các biến và cấu trúc dữ liệu bên trong monitor chỉ có thể được thao tác bởi các thủ tục định nghĩa bên trong monitor đó. (encapsulation).
Tại một thời điểm, chỉ có một tiến trình duy nhất được hoạt động bên trong một monitor (mutual exclusive).
Trong một monitor, có thể định nghĩa các biến điều kiện và hai thao tác kèm theo là Wait Signal như sau : gọi c là biến điều kiện được định nghĩa trong monitor:
Wait(c): chuyển trạng thái tiến trình gọi sang blocked , và đặt tiến trình này vào hàng đợi trên biến điều kiện c.
Signal(c): nếu có một tiến trình đang bị khóa trong hàng đợi của c, tái kích hoạt tiến trình đó, và tiến trình gọi sẽ rời khỏi monitor.
Hình 3.13 Monitor và các biến điều kiện
Cài đặt : trình biên dịch chịu trách nhiệm thực hiện việc truy xuất độc quyền đến dữ liệu trong monitor. Để thực hiện điều này, một semaphore nhị phân thường được sử dụng. Mỗi monitor có một hàng đợi toàn cục lưu các tiến trình đang chờ được vào monitor, ngoài ra, mỗi biến điều kiện c cũng gắn với một hàng đợi f(c) và hai thao tác trên đó được định nghĩa như sau:
Wait(c) : 
status(P)= blocked;
enter(P,f(c));

Signal(c)
if (f(c) != NULL){
exit(Q,f(c)); //Q là tiến trình chờ trên c
statusQ) = ready;

enter(Q,ready-list);

}
Sử dụng: Với mỗi nhóm tài nguyên cần chia sẻ, có thể định nghĩa một monitor trong đó đặc tả tất cả các thao tác trên tài nguyên này với một số điều kiện nào đó.:
monitor 
condition điều kiện>;
;

procedure Action1();
{

}

....

procedure Actionn();
{

}
end monitor;
Hình 3.14 Cấu trúc một monitor
Các tiến trình muốn sử dụng tài nguyên chung này chỉ có thể thao tác thông qua các thủ tục bên trong monitor được gắn kết với tài nguyên:
while (TRUE) {
Noncritical-section ();
.Actioni;
//critical-section();
Noncritical-section ();
}
Hình 3.15 Cấu trúc tiến trình Pi trong giải pháp monitor
Thảo luận: Với monitor, việc truy xuất độc quyền được bảo đảm bởi trình biên dịch mà không do lập trình viên, do vậy nguy cơ thực hiện đồng bộ hóa sai giảm rất nhiều. Tuy nhiên giải pháp monitor đòi hỏi phải có một ngôn ngữ lập trình định nghĩa khái niệm monitor, và các ngôn ngữ như thế chưa có nhiều.
Tiếp cận: giải pháp này dựa trên cơ sở trao đổi thông điệp với hai primitive Send và Receive để thực hiện sự đồng bộ hóa:
Send(destination, message): gởi một thông điệp đến một tiến trình hay gởi vào hộp thư.
Receive(source,message): nhận một thông điệp thừ một tiến trình hay từ bất kỳ một tiến trình nào, tiến trình gọi sẽ chờ nếu không có thông điệp nào để nhận.
Sử dụng: Có nhiều cách thức để thực hiện việc truy xuất độc quyền bằng cơ chế trao đổi thông điệp. Đây là một mô hình đơn giản: một tiến trình kiểm soát việc sử dụng tài nguyên và nhiều tiến trình khác yêu cầu tài nguyên này. Tiến trình có yêu cầu tài nguyên sẽ gởi một thông điệp đến tiến trình kiểm soát và sau đó chuyển sang trạng thái blocked cho đến khi nhận được một thông điệp chấp nhận cho truy xuất từ tiến trình kiểm soát tài nguyên.Khi sử dụng xong tài nguyên , tiến trình gởi một thông điệp khác đến tiến trình kiểm soát để báo kết thúc truy xuất. Về phần tiến trình kiểm soát , khi nhận được thông điệp yêu cầu tài nguyên, nó sẽ chờ đến khi tài nguyên sẵn sàng để cấp phát thì gởi một thông điệp đến tiến trình đang bị khóa trên tài nguyên đó để đánh thức tiến trình này.
while (TRUE) {
Send(process controler, request message);
Receive(process controler, accept message);
critical-section ();
Send(process controler, end message);
Noncritical-section ();

}
Hình 3.16 Cấu trúc tiến trình yêu cầu tài nguyên trong giải pháp message
Thảo luận: Các primitive semaphore và monitor có thể giải quyết được vấn đề truy xuất độc quyền trên các máy tính có một hoặc nhiều bộ xử lý chia sẻ một vùng nhớ chung. Nhưng các primitive không hữu dụng trong các hệ thống phân tán, khi mà mỗi bộ xử lý sỡ hữu một bộ nhớ riêng biệt và liên lạc thông qua mạng. Trong những hệ thống phân tán như thế, cơ chế trao đổi thông điệp tỏ ra hữu hiệu và được dùng để giải quyết bài toán đồng bộ hóa.

Bài đăng phổ biến