第九章協(xié)議處理(編輯修改稿)
2024-08-28 12:56 本頁面
【文章內(nèi)容簡介】 完，一個 分配較少的 用戶想多要一 些 緩沖區(qū)，就從當前分配最多的用戶那兒竊取。 ? 即使一個用戶最初攫取了全部緩沖區(qū)，其它用戶通過緩沖區(qū)竊取可以獲得他們公平的份額。 ? 緩沖區(qū)竊取的通用解決方案 ： ? 使用一個 大頂 堆，代價 O(logn)， n為當前活躍的用戶數(shù) 。 如何實現(xiàn)得更快？ 問題分析 ? 如果允許 用戶一次獲取任意數(shù)量的緩沖區(qū)，那么使用 O(logn)的堆是必需的 。 問題分析 ? 如果允許 用戶一次獲取任意數(shù)量的緩沖區(qū)，那么使用 O(logn)的堆是必需的 。 ? 為獲得常數(shù)時間的算法，假設可以降低要求： ? 一個用戶一次只能竊取一個緩沖區(qū) ? 每個用戶擁有的 緩沖區(qū)數(shù)量是一個小整數(shù) 緩沖區(qū)竊取的常數(shù)時間算法 ? 如果允許 用戶一次獲取任意數(shù)量的緩沖區(qū)，那么使用 O(logn)的堆是必需的 。 ? 為獲得常數(shù)時間的算法，假設可以降低要求： ? 一個用戶一次只能竊取一個緩沖區(qū) ? 每個用戶擁有的 緩沖區(qū)數(shù)量是一個小整數(shù) ? 采用桶排序： ? 將 分配了 i 個緩沖區(qū)的進程 鏈接到 第 i 個桶中 ? 一個指針指向當前分配了最多緩沖區(qū)的進程鏈表 Mckenney算法 ? 將 分配了 i 個緩沖區(qū)的進程組織在一個鏈表中，頭指針保存在第 i 個桶中 ? 一個變量 highest指 向 分配了最多緩沖區(qū)的進程鏈表 竊取一個緩沖區(qū) ? 當進程 P 希望獲取一個緩沖區(qū)時 ： ? 算法從 highest指向的進程鏈表頭部取進程 Q， Q的緩沖區(qū) 數(shù)量 減 1， P的緩沖區(qū) 數(shù)量 加 1 ? 將 P從鏈表 i 移到鏈表 i+1 ? 將 Q從鏈表 j 移到鏈表 j1 ? 如果 highest指向的鏈表為空， 更新 highest為 j1 ? 算法是常數(shù)時間的： ? 由于 限定 了 每次只能增加或減少一個緩沖區(qū)，算法 更新 highest指針最多 只需移動一個桶 。 TCP頭部預測 ? tcp_input是 TCP中最長的一部分代碼，約 1100行： ? 許多實現(xiàn)完全遵循 RFC 793中定義的輸入事件處理步驟 ? 基本
教學教案相關推薦
鄂ICP備17016276號-1