[發明專利]在線性棧上高效恢復協同例程

有效

• 申請號: 201110008477.0
• 申請日: 2011-01-06
• 公開（公告）號: CN102141937A
• 公開（公告）日: 2011-08-03
• 發明（設計）人: N·M·加夫特;M·托格森;H·J·M·梅杰;N·古斯塔夫松
• 申請（專利權）人: 微軟公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 黃嵩泉;高見

背景技術

在計算機科學中，協同例程是通常概括子例程并且可允許多個入口點以進行掛起和恢復執行的程序組件。協同例程有時被用于實現協作任務、迭代器、無限列表和管道。雖然子例程通常是后進先出構造，但協同例程的壽命可按其用途來規定。雖然子例程只能返回一次，但協同例程可返回或讓步一次以上。雖然子例程的開始通常是其唯一入口點，但協同例程的開始是第一入口點且后續入口點可跟隨讓步(yield)命令。例如，同子例程一樣，在協同例程中讓步可將結果和控制返回給調用方協同例程，但不同于子例程，在該協同例程下次被調用時，執行可剛好在讓步調用之后開始而非在協同例程開頭開始。

由于協同例程可返回多次，因此有可能在后續調用時返回附加的值。其中后續調用產生附加結果的協同例程常常被稱為生成器。傳統子例程使用可在程序執行開頭被預分配的單個棧。相反，由于協同例程能夠作為對等體調用其他協同例程，因此通常為協同例程分配附加的棧。有時，預分配棧或者高速緩存預先分配的棧。

生成器還一般化子例程，并且常常被用于簡化迭代器的編寫。生成器中的讓步語句通常不指定要跳轉到的協同例程，而是將值回傳給父例程。然而，仍然有可能在頂級分派器例程的輔助下在生成器設施上實現協同例程，頂級分派器例程將控制顯式地傳遞給從生成器傳回的令牌所標識的子生成器。

許多流行編程語言(包括C、C++和C#)由于基于棧的子例程實現的限制因而在該語言內不直接支持協同例程。在其中協同例程將在邏輯上被用于在可能的情況下實現一機制的情形中，通常創建使用布爾標志和其他狀態變量的組合來在調用之間維護內部狀態的子例程。條件語句導致基于狀態變量的值而執行不同代碼路徑。或者，實現開關語句形式的顯式狀態機。

提供使用協同例程的替換方案的方法是使用線程。線程提供用于管理基本上同時執行的代碼片斷的實時協作交互的能力。線程通常被優先調度。協同例程通常不是。由于線程可在任何時刻被重新調度且能并發地執行，因此使用線程的程序必須注意鎖定。相反，由于協同例程只能在程序中的特定點被重新調度并且不并發地執行，因此使用協同例程的程序常常完全避免了鎖定問題。

在高級語言中實現協同例程的一種方法放棄了便攜性。相反，處理器系列專用的實現對于函數是用匯編語言編寫的，以節約和恢復協同例程上下文。必須注意這些函數的使用和編寫，從而在協同例程共享相同棧時位于該棧上的變量不被覆寫。因此，通常對于高級語言中基于棧的協同例程，需要函數來創建替換棧并在替換棧之間跳轉。可提供第三機器專用函數以創建用于新協同例程的上下文。傳統上，協同例程的棧大小是固定的且在執行期間不能增長。通常，程序分配比所需的更大的棧以避免潛在的棧溢出。

概述

在使用單個線性機器調用棧在沒有直接協同例程支持的語言中執行的計算機系統中，驅動程序例程控制協同例程執行。當協同例程最初被另一協同例程調用時，被調用的協同例程被放到棧上調用者的幀之上。協同例程被首次掛起時，其所有棧幀向下直至驅動程序棧幀并且包括驅動程序棧幀被復制到堆。然而，若協同例程被再次掛起，則其棧幀不被再次復制到堆。當協同例程恢復時，驅動程序例程僅將葉例程放到棧上。盡管該方法中的單個掛起對于深度d的棧將花費O(d)，但由于每一幀僅被復制到堆一次，因此該方法的總分攤成本為O(m)，其中m是曾掛起的幀數，且m通常小于被調用的總幀數n。

若在葉例程中拋出異常，則驅動程序例程檢測或抓住該異常。驅動程序在棧上用與調用者相關聯的棧幀來代替與被調用者(被調用)葉例程相關聯的棧幀。驅動程序執行調用方例程，并且異常被再次拋出。

提供本概述以便以簡化形式介紹將在以下詳細描述中進一步描述的一些概念。本概述并非旨在標識出要求保護的主題的關鍵特征或必要特征，亦非旨在用于限定要求保護的主題的范圍。

附圖簡述

在附圖中：

圖1示出根據本文所公開主題的各方面用于在線性棧上高效恢復協同例程的系統100的示例；

圖2是根據如關于圖1所描述的本文所公開主題的各方面用于在線性棧上高效恢復協同例程的方法200的示例的流程圖。

圖3是示出其中可實現本文所公開主題的各方面的計算環境的示例的框圖；以及

圖4是根據本文所公開主題的各方面的集成開發環境的示例的框圖。

詳細描述

概覽