· 9 years ago · Nov 11, 2016, 11:10 PM
1 +-----------------------------------------------------+
2 | CS 140 |
3 | PROJECT 3: VIRTUAL MEMORY |
4 | DESIGN DOCUMENT |
5 +------------------------------------------------------+
6
7---- GROUP ----
8
9Malvika Nagpal <mnagpal@usc.edu>
10Sean Leonard <stleonarl@usc.edu>
11
12---- PRELIMINARIES ----
13
14 PAGE TABLE MANAGEMENT
15 =====================
16
17---- DATA STRUCTURES ----
18
19>> A1: Copy here the declaration of each new or changed `struct' or
20>> `struct' member, global or static variable, `typedef', or
21>> enumeration. Identify the purpose of each in 25 words or less.
22
23
24Struct Sup_page_entry {
25Uint32_t user_vaddr;
26Uint64_t access_time;
27Bool dirty;
28Bool accessed;
29}
30
31
32Purpose: store additional/supplementary information of each page table entry
33
34
35Struct list frame_table;
36
37
38Purpose: list of frame_table_entry structs, used enable mapping to frame tables
39
40
41Struct frame_table_entry {
42uint32_ t* frame;
43Struct thread *owner;
44Struct sup_page_entry *aux;
45Struct list_elem elem;
46}
47Purpose: individual entries on the main page table that include the actual frame and the owner, also includes a reference to sup_page_entry which has additional information about the frame entry
48
49---- ALGORITHMS ----
50
51>> A2: In a few paragraphs, describe your code for locating the frame,
52>> if any, that contains the data of a given page.
53
54
55Given a virtual address, we see if it’s mapped in the Thread_current() page directory.
56If yes, then get the phys address of the frame and look it up in the global hash table.
57Else, try to obtain a new frame.
58
59
60>> A3: How does your code coordinate accessed and dirty bits between
61>> kernel and user virtual addresses that alias a single frame, or
62>> alternatively how do you avoid the issue?
63
64
65Access to the user stack is fulfilled with Virtual addresses. Ideally, they would be validated in syscall.c (which we have) in addition to the page fault handler in exception.c. Given a valid user vaddress, a page in the supplementary page table is found. The page *could* then be loaded in depending on if that was the intention. The Kernel never uses the kernel vaddresses, as the user vaddress referenced through the supplementary page table is used.
66
67---- SYNCHRONIZATION ----
68
69>> A4: When two user processes both need a new frame at the same time,
70>> how are races avoided?
71
72
73A frame table lock is used to make sure that pages are palloc’d sequentially. So given two processes trying to get a new frame, one would take the lock and get the frame while the other simply doesn’t get a frame / or waits to acquire the lock and does so after the first process gets its page.
74
75---- RATIONALE ----
76
77>> A5: Why did you choose the data structure(s) that you did for
78>> representing virtual-to-physical mappings?
79
80
81We created a frame_table data structures that will map to individual frames. The individual frames will be able to reference additional information associated with them so essentially the page table will be keeping track of the supplementary page tables. We would use a hash table to represent the virtual to physical mapping because that would increase lookup efficiency.
82
83
84 PAGING TO AND FROM DISK
85 =======================
86
87---- DATA STRUCTURES ----
88
89>> B1: Copy here the declaration of each new or changed `struct' or
90>> `struct' member, global or static variable, `typedef', or
91>> enumeration. Identify the purpose of each in 25 words or less.
92
93
94We would want a struct for a frame that would include the physical address of the frame, it would tell us if the frame is pinned or not, a hash_elem so we can reference it into the hash table, and a list of the pages that are in that frame. We would maintain these frames in a list called vm_frames.
95
96---- ALGORITHMS ----
97
98>> B2: When a frame is required but none is free, some frame must be
99>> evicted. Describe your code for choosing a frame to evict.
100
101
102We would implement this by iterating through the list of vm_frames mentioned above and checking to see which frame will need to be replaced next when a frame is required. We will find a frame that has 0 accessed bits and clear those bits as we advance.
103
104>> B3: When a process P obtains a frame that was previously used by a
105>> process Q, how do you adjust the page table (and any other data
106>> structures) to reflect the frame Q no longer has?
107
108
109If eviction or process exit , a good way to do this would be to clear mapping in page directory and dump the pages to disk if not read-only and swap if it’s writable.Then we’d remove the frame from our hashtable.
110
111
112We would free the contents of the page using pagedir_clear_page()
113>> B4: Explain your heuristic for deciding whether a page fault for an
114>> invalid virtual address should cause the stack to be extended into
115>> the page that faulted.
116
117
118If the address of the fault is in the User valid address range and at most 32 bytes below the stack ptr(esp-32), the stack will be expanded by one page. Otherwise, we will catch and execute a failure sequence.
119
120---- SYNCHRONIZATION ----
121
122>> B5: Explain the basics of your VM synchronization design. In
123>> particular, explain how it prevents deadlock. (Refer to the
124>> textbook for an explanation of the necessary conditions for
125>> deadlock.)
126After discussing a little bit in office hours, we would need internal locks on the frame and swap tables and the page list and hashtable inside a process as to not invalidate iterators when searching through those “lists†. Each supplemental page table entry would have a lock since more than one process may access the supp page table.
127
128>> B6: A page fault in process P can cause another process Q's frame
129>> to be evicted. How do you ensure that Q cannot access or modify
130>> the page during the eviction process? How do you avoid a race
131>> between P evicting Q's frame and Q faulting the page back in?
132Each supplemental page table entry has a lock. So during an eviction , if a process Q tries to access, it will page fault and try to look up in the supp page table and hold because the supp page entry lock is already acquired.
133>> B7: Suppose a page fault in process P causes a page to be read from
134>> the file system or swap. How do you ensure that a second process Q
135>> cannot interfere by e.g. attempting to evict the frame while it is
136>> still being read in?
137
138
139Each frame table entry will have a variable note whether or not the page is evictable. If this variable is set to true, then it can be evicted, go ahead, other wise it will be skipped so P can continue its reading in.
140
141>> B8: Explain how you handle access to paged-out pages that occur
142>> during system calls. Do you use page faults to bring in pages (as
143>> in user programs), or do you have a mechanism for "locking" frames
144>> into physical memory, or do you use some other design? How do you
145>> gracefully handle attempted accesses to invalid virtual addresses?
146Invalid addresses will be check and handled in the same sequence as checking out pages and then rejected. If invalid access in page fault then the process will exit.
147If the access is a valid address then we load into main memory and mark specific pin variable to true until we are done accessing (read and write) and then unpin
148.
149---- RATIONALE ----
150
151>> B9: A single lock for the whole VM system would make
152>> synchronization easy, but limit parallelism. On the other hand,
153>> using many locks complicates synchronization and raises the
154>> possibility for deadlock but allows for high parallelism. Explain
155>> where your design falls along this continuum and why you chose to
156>> design it this way.
157
158
159We would have a good number of internal locks that don’t fall under the circular lock dependency for deadlock. We limit how much work is done in a specific lock context which keeps parallelism as opposed to a lock on the whole vm system.
160
161 MEMORY MAPPED FILES
162 ===================
163
164---- DATA STRUCTURES ----
165
166>> C1: Copy here the declaration of each new or changed `struct' or
167>> `struct' member, global or static variable, `typedef', or
168>> enumeration. Identify the purpose of each in 25 words or less.
169
170
171We would create a mapped file struct that includes a file id (file descriptor), a hash_elem for the hash frame able, a thread_elem for the thread’s mapped file list, the user virtual addresses of start and end of the mapped files.
172
173
174We would also create a hash table of files so we can look them up faster.
175
176
177In the thread struct we would add a list of memory mapped files.
178
179---- ALGORITHMS ----
180
181>> C2: Describe how memory mapped files integrate into your virtual
182>> memory subsystem. Explain how the page fault and eviction
183>> processes differ between swap pages and other pages.
184
185
186We are going to keep a list of memory mapped files for each thread/process and handle all of the logic for mapping and unmapping in syscall.c. The hash table for the memory mapped files will be initialized in thread_create. We are choosing hash tables because it will perform quick lookups over a wide range of table sizes.
187
188
189When making the memory mapped file we will add the new file in the hash table and create a file page for the memory mapped file. We will load this file when there is a page fault and check that another page isn’t mapped at the same address → only when everything is successful will we return a unique id.
190
191>> C3: Explain how you determine whether a new file mapping overlaps
192>> any existing segment.
193
194
195We would first check if a page exists in the same address → terminate the process. We will do so by dividing the file into pages and check for each of them if there is already a page at the same user virtual address.
196
197---- RATIONALE ----
198
199>> C4: Mappings created with "mmap" have similar semantics to those of
200>> data demand-paged from executables, except that "mmap" mappings are
201>> written back to their original files, not to swap. This implies
202>> that much of their implementation can be shared. Explain why your
203>> implementation either does or does not share much of the code for
204>> the two situations.
205
206
207The implementation can be shared because both the memory mapped files and the executable files use the same logic when loading or unloading a page. This makes the code more simple and less complex and minimizes duplication.
208
209 SURVEY QUESTIONS
210 ================
211
212Answering these questions is optional, but it will help us improve the
213course in future quarters. Feel free to tell us anything you
214want--these questions are just to spur your thoughts. You may also
215choose to respond anonymously in the course evaluations at the end of
216the quarter.
217
218>> In your opinion, was this assignment, or any one of the three problems
219>> in it, too easy or too hard? Did it take too long or too little time?
220This assignment was difficult but our roadblock was getting project 2 working. So we were extremely delayed on making much progress at all on this project.
221
222>> Did you find that working on a particular part of the assignment gave
223>> you greater insight into some aspect of OS design?
224
225>> Is there some particular fact or hint we should give students in
226>> future quarters to help them solve the problems? Conversely, did you
227>> find any of our guidance to be misleading?
228
229>> Do you have any suggestions for the TAs to more effectively assist
230>> students, either for future quarters or the remaining projects?
231
232>> Any other comments?