[發明專利]一種在固態硬盤上進行海量數據并行掃描的調度方法

有效

• 申請號: 201010237940.4
• 申請日: 2010-07-27
• 公開（公告）號: CN101901264A
• 公開（公告）日: 2010-12-01
• 發明（設計）人: 陳珂;胡天磊;壽黎但;陳剛;徐昶
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林懷禹

1.一種在固態硬盤上海量數據進行并行掃描的調度方法，其特征在于：

掃描被分成多個掃描組，對于每個掃描組，在計算機內存中分配一個固定大小的窗口用于緩存從固態硬盤上讀進的數據頁面，同組中的掃描共享該窗口中的數據頁面；

當掃描開始時，挑選一個掃描組加入，如果當前沒有掃描組則創建一個，加入掃描組后，檢查并在需要時對該組進行分裂，新加入的掃描以掃描組當前掃描窗口的中間頁面作為自己的起始位置，并更新本組的統計信息；

當窗口中的某一數據頁面被所有掃描處理過后，掃描組發起正向的公共頁面請求，讀取下一個頁面來代換掉它，而當組中較快的掃描在領先組中最慢的掃描超過窗口的長度時，單獨發送從自己起始位置反向的補償頁面請求；各掃描之間通過臨界區交換信息；

當一個掃描所在組的公共正向頁面和它的起始位置交匯時，這個掃描已經掃描完所有的數據頁面，此時掃描結束，退出該組并更新統計信息，如果自己是本組內最后一個掃描則刪除掃描組，掃描結束時需檢查所有現存的其它掃描組是否需要根據當前系統狀況進行調整；

所有的頁面請求被一個請求分發進程統一處理，當有新的頁面請求產生時，掃描或掃描組喚醒請求分發進程，正向的公共頁面請求具有較高的優先級，被優先處理，反向的補償頁面請求在有足夠系統資源的情況下才被處理；當一個正向的公共頁面請求被處理后，發起該請求的掃描組內的所有成員都被請求分發進程喚醒，包括已經發送了反向的補償頁面請求的掃描，當一個反向的補償請求被完成后，發起該請求的掃描被請求分發進程喚醒。

2.根據權利要求1所述的一種在固態硬盤上海量數據進行并行掃描的調度方法，其特征在于：所述分成多個掃描組的方法根據系統的信息和各掃描的統計信息決定，每個掃描在開始時根據貪心算法檢查各個現有掃描組以決定加入哪一個可使系統的負荷增加最小；在加入掃描組后，同樣根據貪心算法檢查按照何種分裂策略可使系統的負荷降低最多。

3.根據權利要求1所述的一種在固態硬盤上海量數據進行并行掃描的調度方法，其特征在于：所述各掃描組的內存窗口大小隨著組數目的增減和計算機內存的可用情況動態調整。

4.根據權利要求1所述的一種在固態硬盤上海量數據進行并行掃描的調度方法，其特征在于：所述公共頁面請求和補償頁面請求被一個請求分發進程統一處理，公共頁面請求和補償頁面請求分別加入各自的隊列，請求分發進程被喚醒后，首先服務正向的公共請求隊列，當請求被完成時喚醒發起請求的該組所有掃描；當正向公共請求隊列為空時服務反向補償請求隊列并處理，當請求被完成時喚醒發起該請求的掃描。

5.根據權利要求1所述的一種在固態硬盤上海量數據進行并行掃描的調度方法，其特征在于：所述掃描與掃描之間依靠臨界區進行信息交換，而掃描與請求分發進程之間依靠信號量進行喚醒。