- 作為羅徹斯特大學電腦科學教授，並在他的家鄉威斯康辛大學麥迪遜分校擔任院長五年。他研究並向學生講授並行和分散式程式設計以及語言設計。
全世界都從教科書中認識了邁克爾 , 工作呢 榮獲 Dijkstra 獎，是分散式運算領域最著名的獎項之一。您可能也知道他是該演算法的作者 .
他與 Doug Lee 一起開發了為 Java 庫提供支援的非阻塞演算法和同步隊列。執行 在 JavaSE 6 中效能提高了 10 倍 ThreadPoolExecutor.
內容：
- 早期職業生涯，羅徹斯特大學。夏洛特計劃，山貓語言；
- IEEE可擴充相干接口，MCS鎖定；
- 在不斷變化的世界中生存；
- 學生變笨了嗎？全球趨勢、國際化；
- 與學生進行有效的合作；
- 如何跟上新課程和書籍的準備；
- 商業界和學術界之間的聯繫；
- 想法的實際實施。 MCS、MS、CLH、JSR 166，與 Doug Lee 等人合作；
- 事務內存；
- 新架構。事務記憶體的勝利已近在眼前；
- 非揮發性記憶體、Optane DIMM、超高速設備；
- 下一個大趨勢。雙資料結構。九頭蛇。
面試由以下人員進行：
維塔利·阿克謝諾夫 — 目前是奧地利 IST 的博士後研究員和 ITMO 大學電腦技術系的成員。在競爭資料結構的理論和實務領域進行研究。在加入 IST 之前，他在 Peter Kuznetsov 教授的指導下獲得了巴黎狄德羅大學和 ITMO 大學的博士學位。
阿列克謝·費多羅夫 是 JUG Ru Group 的製作人，這是一家為開發者組織會議的俄羅斯公司。 Alexey 參與了 50 多個會議的籌備工作，從 Oracle（JCK，Java Platform Group）的開發工程師職位到 Odnoklassniki 的開發人員職位，他的簡歷應有盡有。
弗拉基米爾·西特尼科夫 是 Netcracker 的一名工程師。 十年來，他一直致力於 NetCracker OS 的性能和可擴展性，NetCracker OS 是電信運營商用來自動化網絡和網絡設備管理流程的軟件。 對 Java 和 Oracle 數據庫性能問題感興趣。 官方 PostgreSQL JDBC 驅動程序中十多項性能改進的作者。
早期職業生涯，羅徹斯特大學。夏洛特項目，Lynx 語言。
阿列克謝：首先，我想告訴您，在俄羅斯，我們都非常熱愛電腦科學、資料科學和演算法。這實在是太淫穢了。我們已經閱讀了所有內容 。因此，即將到來的會議、學校和這次採訪本身應該會很受歡迎。我們收到了來自學生、程式設計師和社區成員的許多關於這次採訪的問題，因此我們非常感謝有這個機會。電腦科學在美國也受到同樣的喜愛嗎？
邁克爾：我們的領域是如此多樣化，它有如此多的方向，它以如此多不同的方式影響社會，我很難給你一個明確的答案。但事實是，在過去的30年裡，它為商業、工業、藝術和整個社會帶來了巨大的改變。
維塔利: 讓我們從遙遠的事情開始。在許多大學中，都存在著某個特定領域的專業化。對於卡內基美隆大學來說，這是平行計算，對於麻省理工學院來說，這是密碼學、機器人和多線程。羅徹斯特大學有這樣的專業嗎？
邁克爾：說實話，我想說 CMU 和 MIT 各個領域都很專業。我們部門一直最關注人工智慧。在我們工作的人中有一半從事人工智慧或人機互動——這個比例高於其他部門，而且一直都是如此。但我在大學的時候，沒有任何人工智慧的課程，也從來沒有從事過這個領域的工作。所以我的部門專門研究一個與我無關的問題。值得安慰的是，我們部門的第二個最重要的問題是並行和多執行緒編程，也就是我的專業。
維塔利：當多執行緒程式設計領域剛興起時，您開始從事電腦科學工作。您的出版品清單顯示您的第一個作品涉及相當廣泛的問題：多執行緒系統中的記憶體管理、分散式檔案系統、作業系統。為什麼有這麼多才多藝？您是否一直在努力在研究界找到自己的位置？
邁克爾: 作為一名學生，我參加過 在威斯康辛大學，第一個分散式作業系統就是在那裡開發的。在那裡我與拉斐爾·芬克爾（Rafael Finkel）一起工作（）和馬文·所羅門（）。我的論文致力於開發一種用於分散式系統的系統軟體語言——現在每個人都忘記了它，感謝上帝。我創建了 Lynx 程式語言，其目的是讓為鬆散耦合的分散式作業系統建立伺服器變得更容易。由於當時我主要從事作業系統方面的工作，所以我認為我的職業生涯主要與作業系統相關。但羅徹斯特是一所很小的大學，因此，那裡的不同群體之間的互動非常密切。那裡沒有十幾個其他作業系統人員可供我交談，所以我所有的聯絡人都是在完全不同領域工作的人。我真的很喜歡它，成為全能選手對我來說是一個很大的優勢。如果我們具體談論多執行緒資料結構和同步演算法，那麼我開始研究它們完全是偶然的。
IEEE 可擴充相干接口，MCS 鎖定。
維塔利: 能詳細介紹一下嗎？
邁克爾：這是一個有趣的故事，我樂此不疲地告訴大家。事情發生在一次會議上 在波士頓——那是在 80 年代末或 90 年代初。約翰·梅勒-克拉米（），我們學院的畢業生。我認識他，但我們之前沒有進行過聯合研究。瑪麗·弗農（來自威斯康辛州的 ) 發表了有關他們在威斯康辛州開發的多處理器系統的演講： 。這個Multicube在硬體層面有一個同步機制，叫做Q on Sync Bit，後來改名為Q on Lock Bit，因為聽起來像Colby Cheese，這是一個雙關語。如果您對多執行緒機制感興趣，您可能知道 Colby 最終成為 IEEE 可擴展一致性介面標準的同步引擎。這是一種鎖定機制，它在硬體層級創建從一個快取到另一個快取的指針，以便每個鎖持有者知道輪到誰了。當約翰和我聽到這個消息時，我們面面相覷：為什麼要在硬體層面這樣做？使用比較和交換不能實現同樣的事情嗎？我們拿起教室裡的一本筆記本，在上面亂畫。 ，而瑪麗繼續她的報告。隨後，我們實施了它，進行了實驗，結果證明這個想法是成功的，我們發表了文章。當時，對我來說，這個主題似乎只是一個有趣的消遣，之後我打算回到作業系統。但隨後出現了另一個同樣的問題，最後同步、多執行緒和資料結構成為了我的專長。正如你所看到的，這一切都是偶然發生的。
維塔利：我很早就熟悉MCS屏蔽，但直到現在我還不知道這是你的作品，也不明白這是你姓氏的縮寫。
如何在瞬息萬變的世界中生存？
阿列克謝：我有一個相關主題的問題。 30或40年前，不同專業有較多自由。如果您想開始多執行緒或分散式系統的職業生涯，那麼歡迎您，如果您想進入作業系統，沒問題。每個領域都有很多懸而未決的問題，但專家卻很少。現在已經出現了狹隘的專業化：不僅有一般作業系統的專家，還有個別系統的專家。多執行緒和分散式系統也是如此。但問題是，我們的生命並不是無限的，每個人只能投入幾十年的時間來研究。如何在這個新世界生存？
邁克爾：我們在這方面並不特別；同樣的事情在其他地區也發生過。我很幸運，在電腦科學領域還處於「青少年」時期時，我就開始從事該領域的工作。一些基礎已經打好了，但一切都還很不成熟。這個機會並不常出現。電機工程已經存在了很長一段時間，物理學甚至更早，數學幾乎從一開始就存在。但這並不意味著沒有人再在數學領域做出有趣的發現。仍然存在許多懸而未決的問題，但同時，還有更多需要學習的地方。您正確地註意到，現在的專業化比以前多得多，但這只意味著我們發現自己處於與人類活動的大多數其他領域相同的情況。
阿列克謝：我對這裡問題的更實際方面感興趣。我有數學背景，在學習期間我經常參加會議並研究各種科學主題。我發現聽眾中沒有人理解我的報告，同樣，其他人的報告也只有他們自己能理解。高層次的話題就不是這樣了，但是一旦你開始鑽研某件事，觀眾就跟不上你了。你如何處理這個問題？
邁克爾: 並不總是成功。我最近準備了一份報告，其中對技術細節的探討過於深入。隨著演講的進行，很明顯地大多數觀眾並不理解我的意思，所以我必須即時適應情況。幻燈片無法更改，所以效果不是很好——所以，一般來說，我盡量不使用幻燈片。總的來說，我的建議是考慮你的受眾。您需要知道您正在與誰交談，他們的知識水平如何，以及他們需要聽到什麼來欣賞您的工作。
維塔利：您能為我們介紹一下本次講座的內容嗎？
邁克爾：說實話，我不想擴展這個主題，以免讓相關人士匿名。關鍵是，我們經常對我們正在解決的問題的複雜性過於深入，因此我們很難在演講開始時解釋為什麼這個問題有趣且重要，以及它與我們所討論的問題有何關係。根據我的觀察，學生學習這項技能是最困難的。這也是我最近的報告的弱點。一份結構合理的報告應該從一開始就與受眾建立聯繫，向他們解釋問題到底是什麼以及它與已知主題的關係。這種介紹的技術性取決於聽眾。如果完全是雜七雜八的，那麼報告可以是多階段的。每個人都應該能夠理解簡介，到最後這篇文章可能無法跟上您的步伐，但相對熟悉您的領域的人將能夠弄清楚。
學生變笨了嗎？全球趨勢，國際化。
阿列克謝：您觀察學生已經有幾十年了。十年又十年或一年又一年，學生變得更笨還是更聰明？在俄羅斯，教授們不斷抱怨學生一年比一年笨，真的不知道該怎麼辦。
邁克爾: 你確實可以從我們老年人口中聽到很多負面的聲音。我們潛意識裡傾向於期望學生吸收我們已經擁有的 30 年經驗。如果我比1985年有更深的理解，為什麼學生沒有？可能是因為他們都20歲了，你覺得呢？我認為近幾十年來最顯著的變化是人口組成：現在我們的國際學生明顯增多，加拿大人除外。以前有很多加拿大人，因為我們離加拿大邊境很近，那裡的學生週末可以回家。但現在加拿大有很多好大學，而加拿大人更喜歡在這裡學習，而而來美國的人卻明顯減少了。
阿列克謝：您認為這是本地趨勢還是全球趨勢？
邁克爾：我不記得是誰了，但有人說世界是平的。我們的領域變得更加國際化。 此前，它們只在美國舉辦，後來決定每四年在其他國家舉辦一次，現在在世界各地舉辦。這些變化影響更大 ，因為它一直是一個比 ACM 更國際化的組織。計畫主席來自中國、印度、俄羅斯、德國和許多其他國家，因為現在各地都在發生很多事情。
阿列克謝：但是，這種國際化可能會有一些負面影響嗎？
邁克爾：我想說，所有負面方面都與技術無關，而是與政治有關。曾幾何時，主要問題是美國正在從世界各國竊取最聰明、最有才華的人才。現在的主要問題是不同國家之間圍繞簽證和移民的政治遊戲。
阿列克謝: 就是說，障礙之類的。天氣晴朗。
弗拉基米爾：就我個人而言，我對您在向學生教授新科目時採取的方法感興趣。有不同的選擇：你可以先嘗試激勵他們嘗試新事物，或者你可以更專注於某種技術如何運作的細節。你喜歡哪一個？
與學生進行有效的合作
阿列克謝：如何在第一和第二之間找到該死的平衡？
邁克爾：問題是課程並不總是按照我想要的方式進行。我通常會提前給學生閱讀材料，讓他們深入研究，盡其所能地理解它，並針對他們不理解的部分提出問題。然後在課堂上你們可以專注於最困難的時刻並一起探索它們。這是我最喜歡的授課方式。但考慮到現在學生的負擔，我並不總是能夠確保他們提前做好準備。結果，你必須投入比你想要的更多的時間來整體重述材料。儘管如此，我還是盡力保持我們的課堂互動。否則，錄製影片供學生在家觀看會更容易。直播課的重點是人際互動。在課堂上，我更喜歡使用粉筆和黑板而不是幻燈片，除非在某些情況下圖表太複雜而無法在黑板上描繪。多虧了這一點，我不必遵守嚴格的課程計畫。由於我提供材料沒有嚴格的順序，因此我可以根據收到的問題為觀眾量身定製材料。一般來說，我嘗試使課程盡可能具有互動性，以便我呈現的材料取決於向我提出的問題。
弗拉基米爾： 這很棒。根據我的經驗，要讓聽眾提出問題是相當困難的。即使你提前詢問有什麼問題，無論多麼愚蠢或聰明，他們仍然保持沉默。你如何處理這個問題？
邁克爾：你會笑，但如果你沉默地站得夠長，遲早每個人都會感到不舒服，有人會問問題。或者你可以問一個簡單的技術問題，回答是或否，以確定人們是否理解剛才所說的內容。例如，上面的例子中是否存在數據競爭？誰這麼認為？誰不認為呢？誰根本不懂任何事情，因為總共只有一半的人舉手？
維塔利: 如果你回答錯誤，你就會被踢出課堂:)
邁克爾: 如果您沒有回答任何問題，那麼您應該提出問題。我需要了解學生到底需要知道什麼才能回答我剛才提出的問題。我需要他們幫我幫助他們。我已經準備好適應他們，以便他們理解問題所在。但如果我不知道他們腦子裡在想什麼，我就做不到。如果你沒有給學生足夠長的時間平靜，有時他們最終會提出正確的問題，也就是說，那些問題可以讓我看到學生們腦中到底在想什麼。
阿列克謝：這些問題有時會帶來你自己以前沒有想到的想法嗎？他們出乎意料嗎？它們能讓你以新的眼光看待問題嗎？
邁克爾：有些問題開啟了一種呈現材料的新方式。常常有一些問題會導致我不打算談論的有趣問題。學生們經常告訴我，當這種情況發生時，我很容易偏離主題。據他們說，這往往是課程中最有趣的部分。學生提出的問題很少，只有幾次，引發了新的研究方向，最後形成了一篇文章。這種情況在與學生交談時比在課堂上更常見，但偶爾也會在課堂上發生。
阿列克謝：所以學生問了你一些問題，然後才可以發表文章？
邁克爾： 是的。
維塔利：您與學生進行此類對話的頻率如何？他們什麼時候想了解課程內容以外的更多內容？
邁克爾：一直和我的研究生在一起。我大約有五、六個人，我們總是和他們討論一些事情。與只參加我的課程的學生進行這種對話並不常見。儘管我希望這種情況更頻繁地發生。我懷疑他們只是害怕在辦公時間來教職員。每個學期都會有一些學生剋服這種心理障礙，課後與他們交談總是很有趣。確實，如果所有學生都那麼勇敢，我根本就沒有足夠的時間。所以也許一切都在以其應有的方式進行。
維塔利：您是如何抽出時間與學生溝通的？據我所知，在美國老師有很多工作——申請助學金之類的。
邁克爾：老實說，與學生一起工作是我最喜歡的工作。所以我有足夠的動力去做這件事。我在辦公室的大部分時間都花在了各種會議上。現在是夏天，所以我的日程安排不那麼繁忙，但在學年期間，每天從 9 點到 17 點我都把所有東西都收拾好了。研究工作、評論、資助——所有這一切都只有晚上和週末。
如何跟上新課程和書籍的準備。
阿列克謝：您目前是否繼續教授您長期教授的課程？類似於計算機科學入門之類的東西。
邁克爾：這裡首先想到的是程式語言課程。
阿列克謝：本課程今天的版本與 10、20、30 年前有何不同？也許這裡更有趣的不是特定課程的細節，而是整體趨勢。
邁克爾：我的程式語言課程在我創建它時有點不尋常。我在 1980 世紀 XNUMX 年代末開始閱讀這本書，取代了我的同事 Doug Baldwin（）。課程的主題與我的專業無關，但當他離開時，我是教授這門課程的最佳人選。我不喜歡當時存在的任何教科書，所以我最終自己編寫了這門課程的教科書。 （編按：我們正在談論這本書）現已在全球200多所大學使用。我的方法的不同尋常之處在於，它故意混合了語言設計和實現的問題，並且非常注重這些方面在所有可能的領域中的相互作用。基本方法保持不變，許多基本概念也保持不變：抽象、命名空間、模組化、類型。但演示這些概念的語言集已經完全改變了。當課程剛創建時，有很多 Pascal 的例子，但今天我的許多學生甚至沒有聽說過這種語言。但他們知道 Swift、Go、Rust，所以我必須談談今天正在使用的語言。此外，學生現在已經精通腳本語言，但當我開始教授這門課程時，一切都是關於編譯語言的。現在我們需要大量關於 Python、Ruby 甚至 Perl 的資料，因為這就是當今編寫程式碼的方式，而這些語言中發生了很多有趣的事情，包括在語言設計領域。
維塔利: 那麼我的下一個問題將與上一個問題相關。如何跟上這個領域的腳步？我懷疑更新這樣的課程需要大量的工作——你需要理解新的語言，理解主要思想。你怎麼做到這一點？
邁克爾：我不能誇耀我總是 100% 成功。但大多數時候我只是做其他人所做的事情——閱讀網路。如果我想了解 Rust，我會用 Google 搜索，前往 Mozilla 頁面並閱讀那裡發布的手冊。這是商業開發中發生的事情的一部分。如果我們談論科學，那麼你需要關注主要會議的報告。
商業界和學術界之間的聯繫
維塔利：我們來談談商業和科學研究之間的連結。在您的作品清單中，我發現了幾篇關於快取一致性的文章。據我所知，快取一致性演算法在發佈時不穩定？或者還不夠廣泛。您的想法在實踐中有多普遍？
邁克爾: 我不太確定你說的是什麼出版品。我和我的學生 Bill Bolosky 做了很多工作（）和列奧尼達·康托塔納西斯（）在 1990 世紀 XNUMX 年代初關於 Neumann 機器的記憶體管理。當時，企業還沒有了解如何正確地構建多處理器系統：是否值得在硬體級別創建對訪問遠端內存的支持，是否值得使內存分佈式，是否可以從遠程內存，還是需要在操作室系統中移動頁面？ Bill 和 Leonidas 都在這一領域工作，並探索了無需遠端快取加載的方法。這與快取一致性沒有直接關係，但它仍然是 NUMA 記憶體管理的工作，隨後現代作業系統中頁面放置的現代方法由此發展而來。總體而言，比爾和列奧尼達斯做了重要的工作，儘管不是該領域最有影響力的——當時還有許多其他人在做同樣的事情。後來，我研究了與硬體事務記憶體背景下的快取一致性相關的主題。與我一起解決這個問題的小組最終獲得了多項專利。它們背後有一些非常有趣的想法，但我認為它們最終不會在實踐中實施。無論如何，我很難判斷他們的獲利能力。
阿列克謝：就此而言，一個更私人的問題：你的想法付諸實踐對你來說有多重要？或者你不考慮一下嗎？
邁克爾：我喜歡在面試其他人、想要加入學院的申請人或候選人時問這個問題。我認為這個問題沒有正確的答案。做很酷的事情的人可能有非常不同的動機。我被問題吸引是因為我個人覺得它們很有趣，而不是因為它們的實際好處。但另一方面，當一些有趣的東西仍然可以應用時，我真的很喜歡它。所以這裡並不容易。但在我的工作之初，我的驅動力仍然不是世界的最終用途的想法，而是這個想法的和諧以及探索它並看看它會產生什麼結果的願望。如果最終能給出實際結果，那就太好了。
阿列克謝：由於您的教育背景和經驗，您比大多數人更能判斷他人想法的價值。您可以對它們進行比較並確定哪個更適合哪一個。我相信您對英特爾等大型製造商目前正在實踐中使用的東西有自己的看法。從您的角度來看，這些公司所採取的做法有多正確？
邁克爾：實踐總是圍繞著什麼能夠在商業上取得成功，也就是創造利潤，這個你最好問別人。我的工作主要發表在出版物上，在作業系統領域，它們是根據效能指標進行評估的：速度、能耗、程式碼大小。但在我看來，這些實證結果被添加到文章中只是為了發表，而人們工作的真正動機是美學。研究人員從藝術的角度評估解決方案，他們關心想法的優雅程度，並嘗試創造出比現有方法更好的東西。研究者受到個人、主觀、美感動機的驅動。但你不能在文章本身寫這個；這些東西不是程序委員會的論點。幸運的是，優雅的解決方案通常也快速且便宜。大約 15 年前，我和十幾個同事討論了這個主題，最後寫了一篇關於它的文章。我想你現在還能找到它，它的名字叫 或類似的東西，它有十幾位作者。這是唯一一篇我與作者共同撰寫的文章 ，所以如果你在我的出版物清單中搜尋她的名字，你就會找到你需要的東西。它討論了評估系統研究以及優雅的重要性。
阿列克謝：所以科學界和商業界的好標準是有差別的。此科學評估性能、功耗、TDP、實施難易度等等。您有機會在大學進行此類研究嗎？您是否擁有一個擁有不同機器和不同架構的實驗室來進行實驗？
邁克爾：是的，我們部門有很多不同的有趣的機器。大多數情況下它們都很小，我們有一個小集群和許多具有不同加速器的多處理器系統。此外，校園還擁有一個巨大的計算中心，為數十個不同學科的科學家提供服務。它有大約一千個節點和兩萬個核心，全部都運行在 Linux 上。如果有需要，您隨時可以購買一些 AWS。所以我們對硬體沒有重大限制。
阿列克謝: 三十年前是什麼樣子？那時有問題嗎？
邁克爾: 那時候有點不一樣。在 1980 世紀 XNUMX 年代中後期，科學被認為缺乏計算資源。為了改變這種情況，美國國家科學基金會 ）創建了協調實驗研究計劃（協調實驗研究，CER）。該計劃的使命是為計算機科學系提供計算基礎設施，並且已經實現了重大變革。 1984年，我們羅徹斯特大學用她提供的錢買了一艘128節的BBN Butterfly，那是我到達那裡的前一年。當時它是世界上最大的共享記憶體多處理器系統。它有 128 個處理器，每個處理器位於一個單獨的主機板上，並佔用四個機架。每個處理器都有128兆位元組的內存，XNUMX兆位元組的RAM在當時是一個難以想像的數量。在這台機器上我們第一次實現了 MCS 鎖定。
阿列克謝：那麼，如果我理解正確的話，那麼目前硬體問題已經解決了？
邁克爾: 整體來說是的。有一些注意事項：首先，如果您正在晶片層級研究電腦架構，那麼在學術環境中很難做到這一點，因為在商業中有更好的工具可以做到這一點。如果您需要小於 10 奈米的產品，則必須向其他人訂購。在這個領域，成為英特爾的研究員要容易得多。如果您正在研究晶片或固態記憶體上的光通信，您會發現商業中尚未出現的技術，因此您必須建立聯盟。例如，史蒂芬·斯旺森（）創建 新的記憶體技術。這種形式並不總是有效，但在某些情況下它可能會非常成功。此外，在科學領域，開發最強大的計算系統更加困難。目前美國、日本和中國最大的超級電腦專案都以商業為重點。
想法的實際實施。 MCS、MS、CLH、JSR 166，與 Doug Lee 等人合作。
維塔利：您已經談到了您是如何開始研究同步演算法的。你有兩篇非常著名的文章 и ，從某種意義上說，它是用 Java 實現的。 （編按：所有出版品均可查看 ）。在那裡，這種封鎖是透過一些改變來實現的，結果是 ，隊列按預期實現。但從您的文章發表到實際應用，已經過去了很多年。
阿列克謝: 排隊的話好像有10年左右。
邁克爾：這些功能在Java標準庫中出現之前？
維塔利： 是的。為了讓這件事發生，你做了什麼？還是他們什麼也沒做？
邁克爾：我可以告訴您 MS Queue 是如何進入 Java 5 的。他為他認識的正在研究多線程中有趣問題的人組織了一個研討會，因為他想找到可以賣給他們公司的主題。那是我第一次見到道格李的地方。 Doug 和我以及來自 Sun 的大約 25 名其他人員一起討論了 Doug 的演講 ，後來成為 java.util.concurrent。一路上，Doug 說他想使用 MS 佇列，但為此他需要一個計數器來記錄介面佇列中元素的數量。也就是說，這應該透過單獨的方法來完成，原子的、準確的和快速的。我建議簡單地在節點上加上序號，取得第一個節點和最後一個節點的編號，然後從另一個節點中減去一個。道格搔了搔頭，說“為什麼不呢”，最後就這麼做了。我們討論了在圖書館實施這種方法，但道格自己完成了大部分工作。結果，他成功地在 Java 中建立了出色的多線程支援。
阿列克謝：那麼，如果我理解正確的話，.size()方法應該是標準佇列介面的一部分，並且它的演算法複雜度應該是O(1)？
邁克爾：是的，除此之外，還需要一個單獨的計數器。
阿列克謝：因為如果在Java中呼叫.size()方法，結果預計會立即可用，而不是基於集合的實際大小。我明白了，謝謝。
邁克爾：幾年後，我和我的學生 Bill Scherer 一起研究雙資料結構 - 事實上，這就是我要討論的內容 。 Doug 來找我們並說他可以在 Java Executor Framework 中使用它們。他們與 Bill 一起創建了兩種實現，即所謂的公平隊列和不公平隊列。我為他們提供了這個專案的建議，儘管我沒有參與實際程式碼的編寫。結果，執行器的速度顯著提高。
弗拉基米爾：您是否遇到演算法實作不正確或新增功能的請求？一般來說，實踐應該與理論一致，但很多時候它們是不同的。假設您編寫了一個演算法，並且在紙面上它可以工作，但是參與實現的人員開始要求您提供更多功能或對演算法進行某種調整。你有過這樣的情況嗎？
邁克爾：唯一有人來找我問「如何實施」的例子是 Doug 的問題，我已經討論過。但也有一些案例為了滿足實際需求而做了有趣的改變。例如，IBM 的 K42 團隊轉換了 MCS 鎖定並使其成為標準接口，因此無需在獲取和釋放例程中來回傳遞佇列節點。借助這個標準接口，理論上美好的想法開始在實踐中發揮作用。令人驚訝的是，他們從未發表過相關文章，儘管他們獲得了專利，但後來又放棄了。這個想法很棒，只要有可能，我都會試著談論它。
在其他情況下，人們對我發布的演算法進行了改進。例如，MS隊列具有兩步驟安裝機制，這意味著隊列的關鍵路徑上有兩個CAS。在較舊的汽車上，CAS 相當昂貴。英特爾和其他製造商最近對它們進行了很好的優化，但曾幾何時，這些指令都是 30 個週期的指令，因此在關鍵路徑上有多個指令是不可取的。因此，開發了與 MS 隊列類似的不同隊列，但它在關鍵路徑上只有一個原子操作。這是因為在特定時間段內該操作可能需要 O(n) 時間，而不是 O(1) 時間。這不太可能，但有可能。發生這種情況的原因是，在某些時刻，演算法從佇列的開頭遍歷佇列到目前位置。總的來說，該演算法非常成功。據我所知，它的使用並不是很廣泛，部分原因是原子操作所需的資源比以前少得多。但這個主意很棒。我也非常喜歡 Oracle 的 Dave Dice 的工作。他所做的一切都很實用，而且用鐵也很巧妙。他參與了許多 NUMA 感知同步演算法和多線程資料結構。
弗拉基米爾：當您編寫演算法或教導學生時，您的工作結果不會立即可見。社群需要一些時間來熟悉（例如）一篇新文章。新演算法並沒有立即得到應用。
邁克爾：目前還不清楚這篇文章是否重要。我認為對在會議上獲獎的論文進行研究會很有趣。就是看那些程序委員會的人一度認為最好的文章。你需要嘗試透過連結數量和對業務的影響來計算這些文章在 10、20、25 年後的真正影響力有多大。我懷疑兩者之間是否有強烈的相關性。它不會為零，但很可能會比我們希望的弱得多。許多想法在廣泛傳播之前很長一段時間都無人認領。例如，我們以事務記憶體為例。從最初的文章發表到人們真正開始用它建造機器已經過去了 10 多年。在這種記憶體出現在商業產品之前 - 以及所有 20 個。要提前預測這一點是很困難的。另一方面，有時想法會立即實施。幾年前，我與 Joe Izraelevitz 為 DISC 撰寫了一篇論文，提出了持久資料結構有效性的新正式定義，該資料結構可以在運行它們的電腦崩潰後使用。我從一開始就喜歡這篇文章，但結果它比我預期的更受歡迎。它被幾個不同的團體使用，並最終成為持久性結構的標準定義。這當然很好。
弗拉基米爾：你們有什麼評估技巧嗎？您是否嘗試評估您的文章和您的學生？就看你教的人是否走在正確的方向。
邁克爾: 和其他人一樣，我更專注於我現在正在做的事情。再次，像其他人一樣，我偶爾會檢查谷歌學術，看看我過去的論文是否被引用，但這更多是出於好奇。大多數時候，我全神貫注於我的學生現在所做的事情。當談到評價當前的作品時，一部分是出於美學考慮，什麼是優雅的，什麼是不優雅的。在日常層面，開放性議題扮演重要角色。例如，一名學生帶著一些結果的圖表來找我，我們試著去了解圖表中一些奇怪行為的來源。一般來說，在我們的工作中，我們不斷地試圖理解我們尚未理解的事物。
事務記憶體
維塔利：也許我們可以談談事務記憶體？
邁克爾: 我覺得至少值得說一點，因為我付出了很多努力。我在這個主題上發表的出版物比其他任何主題都多。但同時，奇怪的是，我總是對事務性記憶體非常懷疑。在我看來， （M. Herlihy、J. E. B. Moss）的出版超前於時代。在 1990 世紀 166 年代初，他們提出事務記憶體可以幫助有才華的程式設計師處理多執行緒資料結構，以便普通程式設計師可以將這些結構用作庫。也就是說，這將有助於 Doug Lee 執行他的 JSR 2000。但這正是它在 XNUMX 年代初開始被人們所認識的方式，當時它變得普遍。它被宣傳為解決並行程式設計問題的一種方法。這種方法對我來說一直顯得毫無希望。事務記憶體只能使編寫並行資料結構變得更容易。在我看來，這就是她所取得的成就。
關於編寫多執行緒程式碼的難點
阿列克謝： 很有意思。普通程式設計師和能夠編寫多執行緒程式碼的程式設計師之間似乎存在著一定的障礙。去年，我與正在實作某些演算法框架的人進行了幾次交談。例如，與 Martin Thomson 以及從事多執行緒庫工作的程式設計師一起。 （編按：Martin Thompson 是一位非常著名的開發者，他寫道 и 。而且他還有 在我們的 Joker 2015 會議上，視訊錄製 。他也一樣 本次會議 也提供）。他們說，主要的挑戰是使演算法既快速又易於使用。也就是說，他們正在努力克服這個障礙，吸引盡可能多的人來到這個地區。你怎麼看呢？
邁克爾：這就是多執行緒的主要問題：如何在不增加系統複雜度的情況下實現高效能。
阿列克謝：因為當他們試圖避免複雜性時，演算法就會變得不那麼通用。
邁克爾：這裡的關鍵是正確設計的抽象。在我看來，這通常是電腦系統領域的主要內容。巴特勒·蘭普森喜歡使用這個詞，他稱我們為「抽象商人」。今天不存在簡單的技術。我們使用的處理器有 10 億個電晶體——簡單性是不可能的。同時，ISA 比處理器簡單得多，因為我們花了很長時間為其提供高效能和相對簡單的介面。但她也並非一切順利。現在市面上出現的加速器也存在著同樣的問題。問題出現了 - 如何為 GPU 製作正確的介面、加密機制、壓縮、轉碼機制、線性代數機制，甚至更靈活的 FPGA。如何創建一個使工具易於使用並隱藏複雜性的介面？它不會擺脫它，而是向簡單的程式設計師隱藏它。
阿列克謝：據我了解，我們在理解抽象方面仍然存在障礙。以記憶體模型為例，在我們科技發展的階段，這是主要的抽象之一。多虧了它，所有程式設計師都被分為兩類：較大的一部分是那些不理解它的人，較小的一部分是那些理解或認為自己理解的人。
邁克爾：這是一個很好的問題——我們真的了解記憶體模型嗎？
維塔利: 特別是在 C++ 中。
邁克爾：找個時間和漢斯伯姆談談。他是我認識的最聰明的人之一，也是記憶模型的領先專家。他會立即告訴你，他有很多不懂的地方。但如果我們回到抽象的問題，那麼，在我看來，過去30年記憶體模型領域最重要的想法就表達出來了 。 （編者註：完整的出版品清單已提供 ).
阿列克謝：我的問題是：這個障礙是否來自概念的本質？
邁克爾： 不。 Sarita 的結論是，透過正確的方法，您可以成功隱藏所有複雜性，獲得高效能並為程式設計師提供簡單的 API。而如果遵循這個API，就可以達到一致的一致性。我認為這是正確的模型。編寫沒有資料競爭的程式碼並獲得順序一致性。當然，為了減少賽車的可能性，需要特殊的工具，但那是另一回事。
弗拉基米爾：在您的職業生涯中，是否有過這樣的情況：看似解決的問題突然變成了災難，或者事實證明這個問題無法解決？例如，理論上您可以因式分解任何數字或確定任何數字是否為質數。但實際上這可能很難做到；使用目前的硬體很難分解數字。你身上也發生過類似的事情嗎？
邁克爾: 我一下子就記不起來了。有時候，我覺得某個地區已經沒什麼好做的了，但後來那裡發生了一些新的、有趣的事情。例如我認為無限排隊這個領域已經成熟了。在對 MNS 隊列進行了多次改進之後，沒有發生任何事情。然後莫里森（Adam Morrison）和阿菲克（Yehuda Afek）發明了 。很明顯，無限的多執行緒隊列是可能的，大多數時候關鍵路徑上只有一條獲取和遞增指令。這使得實現一個數量級的更好性能成為可能。我們並不是不知道獲取和遞增是一個非常有用的東西。 Eric Freudenthal 在 1980 世紀 XNUMX 年代末與 Allan Gottlieb 合作的超級電腦中寫到了這一點，但它是關於有限的隊列。 Morrison 和 Afek 能夠在無界隊列上使用獲取和增量。
新架構。事務內存的勝利即將來臨嗎？
弗拉基米爾：您是否正在尋找對演算法有用的新架構解決方案？
邁克爾：當然，有很多事情我希望看到實現。
弗拉基米爾: 比如說什麼類型的？
邁克爾：首先，對 Intel 和 IBM 處理器中的硬體級事務記憶體進行一些簡單的擴充。特別是，我希望剛剛發生的非事務性載入和儲存在事務中立即可用。它們會立即導致發生在序列中的循環，因此它們可能很困難。但是，如果您維護抽象層，那麼您可以在事務發生時在事務之外做很多非常有趣的事情。我不知道實施起來會有多困難，但它會非常有用。
另一個有用的事情是從遠端記憶體載入快取。我想這件事遲早會完成。這項技術將允許創建具有分解記憶體的系統。可以在機架中保留 100 TB 的非揮發性內存，作業系統本身將動態決定該內存的哪些部分應對應於處理器的物理位址空間。這對於雲端運算來說非常有用，因為它可以為需要它的任務提供大量記憶體。我想有人會這麼做。
維塔利：為了結束事務性記憶體的討論，我還有一個關於這個主題的問題。事務記憶體最終會取代標準的多執行緒資料結構嗎？
邁克爾： 不。交易是一種投機機制。在程式層面，這些是原子鎖，但在內部它們是推測。如果大多數猜測都是正確的，這樣的預測就會起作用。因此，當線程彼此幾乎不交互時，事務性記憶體可以很好地工作，並且您只需要確保不存在交互。但如果訊息在執行緒之間啟動，則事務就沒什麼用處了。讓我解釋一下，我們正在討論事務圍繞整個原子操作的情況。它們仍然可以成功地用作多執行緒資料結構的元件。例如，如果您需要一個三字 CAS，並且需要在同時處理 20 個執行緒的真正多執行緒演算法中對三個小東西進行多執行緒處理。一般來說，事務可能很有用，但它們不會消除正確設計多執行緒資料結構的需要。
非揮發性記憶體、Optane DIMM、超高速設備。
維塔利：我最後想談的是您目前研究的主題：非揮發性記憶體。在不久的將來，我們對這領域可以期待什麼？也許您知道已經存在的任何有效實施？
邁克爾：我不是硬體專家，我只知道我在新聞中看到的以及同事告訴我的。大家都已經聽過Intel賣 ，其讀取延遲約為動態 RAM 的 3 倍，寫入延遲約為動態 RAM 的 10 倍。它們很快就會推出大容量版本。有趣的是，您可以擁有一台具有數 TB 位元組可尋址 RAM 的筆記型電腦。很可能在 10 年內我們將決定使用這項新技術，因為我們使用 DRAM - 只需增加容量即可。但由於能源獨立，我們迎來了全新的機會。我們可以從根本上改變儲存堆疊，以便位元組尋址工作記憶體和區塊結構持久記憶體之間不存在分離。因此，我們不需要將需要從一個程式運行轉移到另一個程式的所有內容序列化為區塊結構檔案。由此我們可以得到許多影響作業系統、執行時期環境和分散式資料儲存的重要原則。這個領域的工作非常有趣。就我個人而言，我很難預測這一切會導致什麼，但這裡的問題非常有趣。這裡可能會發生革命性的變化，它們自然地從多執行緒工作中產生，因為故障復原是系統正常操作旁邊的「多執行緒」過程。
我目前正在研究的第二個主要主題是管理超高速設備並透過系統策略控制從用戶空間安全存取設備。近年來，出現了將對設備的存取轉移到用戶空間的趨勢。這樣做是因為 TCP-IP 核心堆疊無法在每 5 微秒需要一個新資料包的網路介面之上運行，它根本無法跟上。因此，製造商提供對設備的直接存取。但這意味著作業系統失去了對進程的控制，並且無法為競爭應用程式提供對設備的正確存取。我們的研究團隊認為這個缺點是可以避免的。本月我們將在 USENIX ATC 上發表一篇有關此問題的文章。它與持久性工作相關，因為長壽命位元組可尋址持久性記憶體本質上是一種具有超快 I/O 的設備，需要在用戶空間中進行存取。這項研究使得微核心、外核心和其他傳統嘗試將功能從作業系統核心安全地轉移到用戶空間的新方法成為可能。
弗拉基米爾：位元組尋址記憶體很棒，但有一個物理限制——光速。這意味著與設備互動時不可避免地會出現延遲。
邁克爾： 絕對正確。
弗拉基米爾：是否有足夠的容量來應付新的負載？
邁克爾: 這是一個很好的問題，但我很難回答。在記憶體中處理的想法已經存在相當長一段時間了，它非常有趣，但也非常複雜。我沒有在這個領域工作過，但如果在那裡有一些發現那就太好了。恐怕我沒有什麼好補充的了。
弗拉基米爾: 還有一個問題。新的、大得多的 RAM 將無法裝入 CPU 中。因此，由於物理限制，該RAM必須隔離。
邁克爾：這完全取決於積體電路生產中的缺陷數量。如果能夠製造出完全沒有缺陷的半導體晶片，那麼就有可能用它來製造整個微電路。但現在我們不知道如何製造比郵票更大的微電路。
弗拉基米爾：但我們仍在談論巨大的尺寸，大約厘米。這不可避免地會對延遲產生影響。
邁克爾： 是的。對於光速你無能為力。
弗拉基米爾： 很遺憾。
下一個大趨勢。雙資料結構。九頭蛇。
維塔利：據我了解，你很快就能抓住新趨勢。您是最早從事事務性記憶體工作的人之一，也是最早從事非揮發性記憶體工作的人之一。您認為下一個大趨勢是什麼？或者也許這是一個秘密？
邁克爾: 說實話，我也不知道。希望當有新的東西出現時我能夠注意到。我沒有足夠幸運自己發明任何新領域，但我有一些運氣並且能夠很早就開始在其他人創造的新領域中工作。我希望我將來能夠做到這一點。
阿列克謝：本次訪談的最後一個問題是關於您在 Hydra 的表現以及您在學校的活動。如果我沒理解錯的話，學校的報告是關於無阻塞演算法的，會議上是關於雙資料結構的。您能否對這些報道說幾句話？
邁克爾：在某種程度上，我們已經在這次訪談中與您討論過這些主題。這是關於我和我的學生 Bill Scherer 所做的工作。他就此寫了一篇論文，Doug Lee 也對此做出了貢獻，它最終成為 Java 庫中多線程同步隊列的一部分。我們假設資料結構的讀寫是無阻塞的，也就是每個操作的關鍵路徑上的指令數量有限。如果您嘗試從空容器中刪除數據，或嘗試刪除不在該容器中的某些數據，您會立即收到通知，無法執行此操作。但如果執行緒確實需要這些數據，這種行為可能是不可接受的。那麼首先想到的就是創建一個循環，不斷詢問是否出現了必要的數據。但其他人也會受到干擾。另外，使用這種方法，您可以等待 10 分鐘，然後其他執行緒就會過來，並且它會意外地先收到必要的資料。雙資料結構仍然沒有鎖，但它們允許執行緒正確等待。術語“雙”意味著該結構包含資料或資料請求，我們稱它們為反資料。因此，如果您嘗試從空容器中檢索某些內容，則會將請求放入該容器中。現在線程可以等待請求而不會打擾其他任何人。此外，資料結構會為請求分配優先級，以便在收到請求時將其傳遞給正確的人。結果是一種非鎖定機制，在實踐中仍然具有正式的規範和良好的性能。
阿列克謝：您對這個資料結構有什麼期望？它會提高所有常見情況下的效能，還是更適合某些情況？
邁克爾：如果首先您需要一個沒有鎖定的容器，其次您需要在需要從容器中檢索不存在的資料的情況下等待，那麼它很有用。據我所知，當滿足這兩個條件時，我們的框架提供最佳行為。因此，在這些情況下我建議使用它。無鎖定資料結構的主要優點是可以避免效能問題。如果資料從一個線程傳輸到另一個線程，則等待在許多演算法中非常重要。
維塔利：讓我澄清一下：你會在學校和會議上談論同樣的事情嗎？
邁克爾： 在學校 關於多執行緒資料結構的一般性知識，以及課程開始時概述的基本原理。我假設觀眾知道什麼是線程並且熟悉鎖。基於這個基礎知識，我來談談無鎖資料結構。我將概述該領域最重要的問題，並涉及記憶體管理等主題。我認為不會有比 MS 隊列更複雜的事情了。
阿列克謝：您打算在學校課程結束時教授雙重資料結構嗎？
邁克爾：我會提到它們，但不會花太多時間。 Hydra 報告將專門獻給他們。它將涵蓋最終進入 Java 的項目，以及與 Joe Israelevich 合作創建 LCRQ 隊列的雙變體，並為雙資料結構創建近乎通用的設計。
阿列克謝：所以學校的講座可以推薦給初學者，而關於 Hydra 雙資料結構的講座可以推薦給已經有一定經驗的人嗎？
邁克爾：如果我錯了，請糾正我，但 Hydra 的受眾非常多樣化，包括許多 Java 專家，以及一般不專門參與多執行緒程式設計的人。
維塔利： 是的，它是真實的。
阿列克謝: 至少我們希望如此。
邁克爾：在這種情況下，我將面臨與我們開始這次訪談時相同的問題：如何使報告既具有足夠豐富的技術細節，又可供所有聽眾理解。
維塔利：您會像講課一樣做報告嗎？即與觀眾交談並適應情況？
邁克爾：恐怕這樣不行，因為報告會有幻燈片。當聽眾最初講不同的語言時，幻燈片就很重要。很多人會覺得很難理解我的英語，特別是如果我說得太快的話。我選擇這些主題是因為 讓我在 SPTDC 學校講講無鎖資料結構；然後我需要一份 Java 使用者小組會議的報告，並且我想選擇 Java 程式設計師特別感興趣的內容。最簡單的方法就是談論我以某種方式參與的 Java 庫中的那些東西。
阿列克謝：我們假設 Hydra 的觀眾已經了解一些有關無鎖程式設計的知識，並且可能在這方面有一些經驗。但這只是一個假設，會議本身情況將會變得更加清晰。不管怎樣，謝謝你的時間。我相信這次採訪對我們的讀者來說會非常有趣。多謝！
維塔利： 謝謝。
邁克爾：我很高興在聖彼得堡見到您。
阿列克謝：我們也是，我們有一座美麗的城市。你以前來過這裡嗎？
邁克爾：不，我根本沒去過俄羅斯。但聖彼得堡一直在我還沒去過但又很想去的地方名單上，所以我很高興收到邀請。
阿列克謝：順便說一句，我們將為演講者準備一個遊覽計劃。非常感謝您接受採訪，祝您有愉快的一天！
您可以在 Hydra 2019 會議上繼續與 Michael 對話，該會議將於 11 年 12 月 2019 日至 XNUMX 日在聖彼得堡舉行。他會帶著一份報告來 . 可以購買門票 .
來源： www.habr.com
