跳到主要內容

臺灣博碩士論文加值系統

(44.200.86.95) 您好!臺灣時間:2024/05/22 13:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:楊淑雯
研究生(外文):Shu-Wen, Yang
論文名稱:發展具有優先權支援的電腦系統
論文名稱(外文):Developing a Priority-Supported Computer System
指導教授:葉佐任
指導教授(外文):Tsozen Yeh
口試委員:洪茂盛白英文黃文吉
口試委員(外文):Mao Cheng, HongYing Wen, BoWen Ji, Huang
口試日期:2011-07-25
學位類別:碩士
校院名稱:輔仁大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:113
中文關鍵詞:優先權硬碟排程系統效能記憶體
外文關鍵詞:prioritydisk schedulingsystem performancememory
相關次數:
  • 被引用被引用:0
  • 點閱點閱:172
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著硬碟空間與CPU 速度快速的成長,硬碟讀取時間成為目前電腦系統的瓶頸之
一。除了改善硬碟排程與硬碟資料的管理外,利用記憶體快取硬碟資料的特性能
有效的降低系統向硬體要求資料的次數,減少程式執行時硬碟的讀取時間。
一部電腦主機上可能同時有很多程式在執行,而使用者會希望某些程式能夠
更快的被執行完成。雖然目前已經提出很多優先權的概念,但只有提供讓使用者
設定程式優先權的機制,才能使系統在特定的時間點達到使用者想要的最佳效
能。
目前的Linux 系統已提供使用者設定CPU 和硬碟排程器的優先權,本論文提
出讓使用者設定記憶體的優先權,將優先權機制加入到記憶體置換的演算法中,
讓高優先權程式所使用的記憶體分頁在程式結束執行前能夠保留於記憶體中,避
免高優先權程式的記憶體分頁被置換出記憶體,而必須再向硬碟讀取資料的情
況。此外並修改CFQ 硬碟排程器目前的優先權機制,使高優先權程式的讀寫要求
能夠更快的被硬碟排程器排程,加快高優先權程式讀寫檔案的速度。
As the storage capacities and CPU speed increases dramatically over the past few years, the
disk performance is one of the performance bottlenecks of modern computer. In addition
to improve the disk scheduler and the data's management in disk, the characteristic caching
data from disk by using memory may efficiently reduce the time that the kernel need to
require data from disk and the time of disk accessing to make the process with higher
priority run more quickly than other processes with lower priority.
There are many processes simultaneously run on a computer system, and users may
hope some of the processes can run more quickly. Although many priority policies have
been proposed, but only the users know which process has a high priority to quickly run
can get the best performance the users want.
Now users can set the different priority about CPU and disk scheduler in current Linux
system. We propose to add priority policy in memory reclaim algorithm, then the page
belong higher priority processes can be keeped in memory before the process be released.
This way may avoid the swap about high priority page and then the high processes need
not to ask disk for access date. We also modify the current CFQ scheduler to make sure
the requests with higher priority can run faster then the lower priority requests.
1 導論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
1.2 研究目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 論文結構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 背景知識與相關研究. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1 優先權概要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 CPU 排程的優先權機制. . . . . . . . . . . . . . . . . . . . . . 13
2.1.2 記憶體置換的優先權演算法. . . . . . . . . . . . . . . . . . . 14
2.1.3 硬碟存取的優先權機制. . . . . . . . . . . . . . . . . . . . . . 15
2.2 硬碟排程器(I/O scheduler) . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Linus Elevator . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 限期式硬碟排程器(Deadline I/O Scheduler) . . . . . . . . . . . 19
2.2.3 預測式硬碟排程器(Anticipatory I/O Scheduler) . . . . . . . . . 20
2.2.4 公平佇存式硬碟排程器(Complete Fair Queue I/O Scheduler) . 21
2.2.5 無作為硬碟排程器(Noop I/O Scheduler) . . . . . . . . . . . . . 22
2.3 目前Linux Kernel 使用的記憶體置換演算法. . . . . . . . . . . . . . 22
3 設計與實作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1 設計概要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 重要的核心資料結構. . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 硬碟排程部分. . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1.1 request_queue . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1.2 request_list . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1.3 bio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1.4 request . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1.5 cfq_io_context . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1.6 elevator_type . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1.7 cfq_data . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1.8 service_tree . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1.9 cfq_group . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1.10 cfq_queue . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1.11 sort queue . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1.12 FIFO queue . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 記憶體管理部分. . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2.1 page . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2.2 address_space . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.3 mm_struct . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.4 vm_area_struct . . . . . . . . . . . . . . . . . . . . . 34
3.2.2.5 task_struct . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 優先權硬碟排程器. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1 I/O 優先權. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.2 以優先權值來排序的佇列. . . . . . . . . . . . . . . . . . . . 36
3.3.3 取得下一個要分派的I/O request . . . . . . . . . . . . . . . . . 36
3.4 優先權記憶體置換演算法. . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.1 高優先權行程表. . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.2 判斷page 的優先權. . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.3 將高優先權的page 留在記憶體中. . . . . . . . . . . . . . . . 40
3.5 使用者介面. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.1 新增控制記憶體優先權的系統呼叫. . . . . . . . . . . . . . . 41
3.5.2 使用者端程式. . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.2.1 設定程式I/O 優先權指令. . . . . . . . . . . . . . . 42
3.5.2.2 設定記憶體優先權程式指令. . . . . . . . . . . . . . 43
4 實驗與分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1 實驗設計. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 實驗一:記憶體置換不忙碌的情形. . . . . . . . . . . . . . . . . . . 47
4.2.1 提高一個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 47
4.2.2 提高三個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 53
4.2.3 提高五個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 59
4.3 實驗二:記憶體置換普通忙碌的情形. . . . . . . . . . . . . . . . . . 63
4.3.1 提高一個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 66
4.3.2 提高三個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 72
4.3.3 提高五個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 76
4.4 實驗三:記憶體置換非常忙碌的情形. . . . . . . . . . . . . . . . . . 85
4.4.1 提高一個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 85
4.4.2 提高三個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 90
4.4.3 提高五個程式的優先權. . . . . . . . . . . . . . . . . . . . . . 95
5 結論與未來研究. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107

[1] Y. Lin, “Providing priority-based services in web proxy servers,”Master's thesis,
Fu Jen Catholic University, 2010.
[2] M. K. Mckusick, W. N. Joy, S. J. Leffler, and R. S. Fabry, “A fast file system for
unix,”ACM Transactions on Computer System, 1984.
[3] M. Rosenblum and J. O. Ousterhout, “The design and implementation od a logstructured
file system,”ACM Transactions on Computer System, 1992.
[4] J. Wang and Y. Hu, “Profs:performance-oriented data reorganization for log- structured
file system on multi-zone disks,”IEEE International Symposium on Mod- eling,
Analysis, and Simulation of Computer and Telecommunications Systems, 2001.
[5] J. Wang and Y. Hu, “Wolf-a novel reordering write buffer to boost the performance
of log-structured file systems,”USENIX 1th Conference on File and Storage Technologies,
2002.
[6] W. Wang, Y. Zhao, and R. Bunt,“Hylog: A high performance approach to managing
disk layout,”USENIX 3th Conference on File and Storage Technologies, 2004.
[7] H. Jeon and S. H.Noh, “A database disk buffer management algorithm based on
prefetching,”7th international Conference on Information and Knowledge Management,
1998.
[8] J. Lewis, M. Alghamdi, M. A. Assaf, X. Ruan, Z. Ding, and X. Qin, “An automatic
prefetching and caching system,”IEEE, 2010.
[9] S. Subha, “An algorithm for buffer cache management,”IEEE, 2009.
[10] T. Yang, T. Liu, E. Berger, S. Kaplan, and J. Moss, “Redline: First class support for
interactivity in commodity operating systems,”8th USENIX Symposium on Operating
Systems Design and Implementation, 2008.
[11] H. Chen and J.Xia, “A real-time task scheduling algorithm based on dynamic priority,”
ACM SIGOPS Operating Systems Review, 2009.
[12] J. R. Haritsa, M. Livny, and M. J. Carey, “Earliest deadline scheduling for real-time
database systems,”ACM/IEEE SIGMOD Int'l Conference of Management of Data,
1991.
[13] E. Jensen, C. Locke, and H. Tokuda, “A time-driven scheduling model for real-time
operating system,”ACM SIGMOD Int'l Conference of Management of Data, 2000.
[14] D. Vengerov, “Adaptive utility-based scheduling in resource-constrainted system,”
ACM SIGMOD Int'l Conference of Management of Data, 2000.
[15] D. Lee, J. Choi, J. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S. Kim, “On the
existence of a spectrum of policies that subsumes the least recently used (lru) and least frequently used (lfu) policies,”ACM SIGMETRICS international conference
on Measurement and modeling of computer systems, 1999.
[16] Z. Chen, Y. Zhou, and K. Li, “Eviction based cache placement for storage caches,”
Real-Time Systems Symposium, 2003.
[17] B. S. Gill and D. S. Modha,“Wow: Wise ordering for writes - combining spatial and
temporal locality in non-volatile caches,”USENIX Annual Technical Conference,
2005.
[18] S. Jiang and X. Zhang, “Ulc: a file block placement and replacement protocol to
effectively exploit hierarchical locality in multi-level buffer caches,”IEEE 24th International
Conference on Distributed Computing Systems, 2004.
[19] X. Jia, A. Trotman, R. O. Keefe, and Z. Huang, “Application-specific disk i/o optimization
for a search engine,”IEEE Int'ln Conference of Parallel and Distributed
Computing, Applications and Technologies, 2008.
[20] T. Johnson and D. Shasha, “2q: A low overhead high performance buffer management
replacement algorithm,”International Conference on Very Large Databases,,
1994.
[21] S. Jiang, F. Chen, and X. Zhang, “Clocl-pro: An effective improvement of the clock
replacement,”USENIX Annual Technical Conference, 2005.
[22] S. Jiang, X. Ding, F. Chen, E. Tan, and X. Zhang, “Dulo: An effective buffer cache
management replacement scheme to exploit both temporal and spatial locality,”4th
USENIX Conference on File and Storage Technologies, 2005.
[23] X. Li, A. Aboulnaga, and K. Salem, “Second-tier cache management using write
hints,”4th conference on USENIX Conference on File and Storage Technologies,
2005.
[24] Y. Zhou, J. Philbin, and K. Li, “The multi-queue replacement algorithm for second
level buffer caches,”USENIX Annual Technical Conference, 2001.
[25] F. I. Popovici, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau, “Robust, portable
i/o scheduling with the disk minic,”USENIX Annual Technical Conference, 2003.
[26] L. Yang, “Developing a multi-level priority disk scheduler,”Master's thesis, Fu
Jen Catholic University, July 2007.
[27] S. Iyer and P. Druschel, “Anticipatory scheduling: a disk scheduling framework
to overcome deceptive idleness in synchronous i/o,”ACM SIGOPS Operating Systems
Review, 2001.
[28] J. Axboe, “Completely fair queueing (cfq) scheduler.”http://en.wikipedia. org/
wiki/CFQ, 2010.
[29] Y. Xu and S. Jiang, “A scheduling framework that makes any disk schedulers nonwork-
conserving solely based on request characteristics,”USENIX 9th Conference
on File and Storage Technologies, 2011.
[30] W. Mauerer, Professional Linux Kernel Architecture. Wiley Publishing, 2008.
[31] R. Love, Linux Kernel Development 3/e. Novell Press, 2010.
[32] R. Abbott and H. Garcia-Molina, “Scheduling i/o requests with deadlines: A performance evaluation,”Real-Time Systems Symposium, 1990.
[33] S. L. Pratt and D. A. Heger, “Workload dependent performance evaluation of thelinux 2.6 i/o schedulers,”Proceedings of the Linux Symposium, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top