09/08/2005 08:33 PMUNIVERSITY OF CALIFORNIAPage 1 of 6file:///Users/tcondie/Workspace/CS186/Hw1/hw1_files/hw1.htmlUNIVERSITY OF CALIFORNIACollege of EngineeringDepartment of EECS, Computer Science DivisionAssignment 1 Prof. Joe HellersteinDr. Minos GarofalakisAssignment 1: PostgreSQL 8.0.3 Buffer ManagerIn the previous assignment, we learned how to set up a database cluster (using initdb), how to start the postgres master process (usingpg_ctl), how to create a specific database (using createdb), and how to query this database (using a front end tool like pgaccess or psql).Now we start with the actual C code hacking. The aim is to modify functionality in the backend server of PostgreSQL. For this firstassignment, we focus on just one core module - the buffer manager. The actual coding for this assignment is minimal, given the highlyorganized and modular PostgreSQL code (the code for the buffer manager policy is cleanly separated from the rest of the code base).However, you have to figure out what code to modify, which is non-trivial! There are three major parts to this project:Understanding different buffer management strategiesExamining, understanding and modifying existing codeTesting your code in a real systemPartners?There are two parts to this assignment, the first of which is to be done individually and the second in teams of 2 people. For this, youwill work in groups of 2. Please form a your team of 2 and register at the group registration webpage by Friday Sept. 9.DeadlinesYou have to submit this assignment in TWO PHASES:. 1 The first part will test your understanding of different buffer replacement strategies and is due on Tuesday Sept 13 at 11:59pm. This part must be done individually.. 2 The second phase requires that you and your partner code a buffer replacement policy and create tests code. The due date for thepart is Tuesday Sept. 20 at 11:59pm.The second part is expected to take much more time than the first. So manage your time accordingly!The rest of this document describes your tasks in each phase.Tasks and Grade Percentage. 1 Understanding different buffer replacement strategies. (20%). 2 Implement the CLOCK buffer replacement strategy. (80%). 3 Add test code using the provided test harness. (0%)09/08/2005 08:33 PMUNIVERSITY OF CALIFORNIAPage 2 of 6file:///Users/tcondie/Workspace/CS186/Hw1/hw1_files/hw1.htmlThe rest of this document describes these steps in detail. Note that in the code and in this document a "buffer" or "slot" is what the textand course notes refer as a "buffer frame". Similarly, the terms "refcount" and "pincount" are used interchangeably.1. Understanding Different Buffer Replacement Strategies. (20%)The textbook describes LRU, MRU and CLOCK strategies in section 9.4.1. However, you may need to read the entire section (9.4) toget a full image of a buffer manager in the DBMS. A fourth (more recent) strategy is called 2Q, and is used in the latest version ofPostgres (8.0.3). LRU, MRU, and CLOCK strategies work well enough for most systems so we are going to replace 2Q with a CLOCKstrategy. But first you'll need to exercise your understanding of the LRU, MRU, and CLOCK buffer replacement strategies.This part of the assignment requires no code. We will give you the number of page slots that the buffer manager must manage and asequence of data blocks accessed by the different DBMS layers above the buffer manager layer. You will have to track the behavior ofthe buffer manager (which pages it has to replace, when, etc.) using your, and yours alone, knowledge of the three aforementioned bufferreplacement strategies.Solution format for this step: You must record your answers in three plain text files called strategy.lru, strategy.mru, strategy.clock.These files will contain the buffer/slot state and buffer manager replacement decisions in accordance to the LRU, MRU, and CLOCKpolicies respectively. The format of each file is as follows:Three columns of text, separated by spacesOne line of text each time a page miss occursEach row lists the time of a page miss, a space, the buffer pool page (P1, P2, P3, P4), a space and, if an eviction occurs, the pageevicted from memoryFor example, assume there are four page slots your buffer manager must manage: P1, P2, P3, P4. All four slots are initially empty. Whenthe buffer pool has unused slots (e.g., in the beginning when all four slots are empty), it will put the newly read data in the first unusedslot. The blocks to be read from disk are labeled A through F. For simplicity here, we assume that after each access the page is pinned,and then immediately unpinned (you cannot make this same assumption when writing the actual code. A page may be pinned for anylength of time in a DBMS!)Given this information and the following workload:Time T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11Block Accessed A A B C D E F A B C Dthe files should be as follows:strategy.lruT1 P1T3 P2T4 P3T5 P4T6 P1 AT7 P2 BT8 P3 CT9 P4 DT10 P1 ET11 P2 Fstrategy.mruT1 P1T3 P2T4 P3T5 P4T6 P4 DT7 P4 ET11 P3 Cstrategy.clockT1 P1T3 P2T4 P3T5 P4T6 P1 AT7 P2 BT8 P3 CT9 P4 DT10 P1 ET11 P2 FNote that certain times (e.g., T2) are missing for each strategy. This is due to the different buffer miss patterns exhibited by the givenreplacement policy. Note also that the third column will be blank when the buffer miss does not result in an eviction. Finally, observethat in this case, for the given number of pages and sequence of block accesses, MRU emerges the winner (least number of misses).09/08/2005 08:33 PMUNIVERSITY OF CALIFORNIAPage 3 of 6file:///Users/tcondie/Workspace/CS186/Hw1/hw1_files/hw1.htmlNow we come to the problem that you will have to solve. Suppose the buffer manager has five page slots to manage: P1, P2, P3, P4, P5.All slots are initially empty. Suppose seven disk blocks (A, B, ..., G) are accessed by the layers above the buffer manager layer in theDBMS. To access your access pattern, login to your cs186 account and type mypattern at the prompt. Remember that you must use your cs186class account to get your access pattern. Based on this information, you should perform a similar analysis as the one above. Generate the three files strategy.lru, strategy.mru, and strategy.clock for this problem. Stick to the specified format (e.g., no extra line atthe end of a file), as we will use file comparison scripts to evaluate your answers.How to submit: You will need to use the unix submit program to hand in your assignment:1. Save your three files in a directory
View Full Document
Unlocking...