1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
+---------------------------+
| ProgOS |
| PROJECT 2: VIRTUAL MEMORY |
| DESIGN DOCUMENT |
+---------------------------+
---- GROUP ----
>> Fill in the names and email addresses of your group members.
Peter Ketscher <e9651415@mail.student.tuwien.ac.at>
Karoline Knoth <e0326266@student.tuwien.ac.at>
Manuel Mausz <manuel-uni@mausz.at>
---- PRELIMINARIES ----
>> If you have any preliminary comments on your submission, notes for the
>> TAs, or extra credit, please give them here.
>> Please cite any offline or online sources you consulted while
>> preparing your submission, other than the Pintos documentation, course
>> text, lecture notes, and course staff.
PAGE TABLE MANAGEMENT
=====================
---- DATA STRUCTURES ----
>> A1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration. Identify the purpose of each in 25 words or less.
struct thread:
struct hash page_table ...supplemental page table of thread
struct page_table_entry:
void *upage ...virtual address of page
bool loaded ...indicates if page is loaded
struct segment ...structure needed for lazy loading of data segments
struct hash_elem elem ...Hash element.
---- IMPLEMENTATION ----
>> A2: Describe how you implemented lazy page loading. How do you
>> determine the file and file offset corresponding to a virtual
>> address?
When we try to insert a new segment into our supplemental page table we record
some information in the struct segment of each page table entry.
This struct contains:
* the virtual address of the page
* if the page is already loaded or not
* the associated file
* the offset in the file
* if the page is writable or not
Lazy loading of pages is accomplished by not loading the page instantly. The
actual page-loading is done when a page-fault occurs.
---- SYNCHRONIZATION ----
>> A3: How do you deal with or prevent page faults in file system
>> routines. Argue why your solution is deadlock free.
All system calls assert that a page fault can never occur while the
file system is locked. As for this reason syscall_read uses a temporary page
as buffer which is copied into user space after the filesystem is unlocked
again. This means if a page fault occurs during copying the file system is not
locked an therefore this cannot create a deadlock.
STACK GROWTH
============
---- DATA STRUCTURES ----
>> B1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration. Identify the purpose of each in 25 words or less.
extern void *syscall_sp ...stored stack pointer for the "page fault inside
syscall/kernel"-case
---- IMPLEMENTATION ----
>> B2: Describe how you integrated the (potentially growing) stack segment
>> into your page table management implementation.
The stack growth itself is triggered by the page fault handler just as the
lazy loading of pages. Other than that there's no association between the pages
of the stack and the pages of segments/mmapped files.
So pages of the stack don't get tracked inside the page table at all!
---- ALGORITHMS ----
>> B3: Explain how you detect a page fault which should trigger a
>> stack growth. What assumptions are needed for your implementation
>> to work?
If we do not find a valid entry in our supplemental page-table it could be
very well be a valid stack access. The maximum offset we consider a valid
access is caused by the PUSHA instruction, which may try to access an address
32 bytes below the current stack pointer. Everything higher we consider
an exception.
MEMORY MAPPED FILES
===================
---- DATA STRUCTURES ----
>> C1: Copy here the declaration of each new or changed `struct' or
>> `struct' member, global or static variable, `typedef', or
>> enumeration. Identify the purpose of each in 25 words or less.
struct mmap_table:
struct mmap_table_entry **ids;
int id_free; ...lowest-index free
int id_max; ...highest-index used
int id_cap; ...mmap table capacity
struct mmap_table_entry:
void *upage; ...virtual address of first page of mmapped file
struct file *file; ...file handle
int pages; ...number of pages the mapping needs
---- ALGORITHMS ----
>> C2: Describe how memory mapped files integrate into your virtual
>> memory subsystem.
For every page required by the memory mapped file we create an associated entry
in the page table. It contains the first virtual address of the memory mapped file,
the file handler and the number of pages which are needed for the mapping.
Additionally we store the lowest free index, the highest used index and the
capacity of the mmap table. We then create for every page required by the
memory mapped file a new page table entry.
>> C3: Explain how you determine whether a new file mapping overlaps
>> any existing segment.
We avoid overlaps of file mappings by determining in the systemcall which tries
to map a file if the required number of pages for the mapping are still free.
To obtain this information we lookup the entries in the page table
that imply that the memory space needed for the mapping is occupied by other
pages. Furthermore we must check if any page not in the page table (for
instance loaded pages on the stack) occupies the space we want to map our file
to.
---- RATIONALE ----
>> C4: Mappings created with "mmap" have similar semantics to those of
>> data demand-paged from executables, except that "mmap" mappings are
>> written back to their original files, not to swap. This implies
>> that much of their implementation can be shared. Explain why your
>> implementation either does or does not share much of the code for
>> the two situations.
As our implementation of the supplemental page table does not distinguish
between pages of memory mapped files and pages of data segments they share
the same insert and loading code.
SURVEY QUESTIONS
================
Answering these questions is optional, but it will help us improve the
course in future quarters. Feel free to tell us anything you
want--these questions are just to spur your thoughts. You may also
choose to respond anonymously in the course evaluations at the end of
the quarter.
>> In your opinion, was this assignment, or any one of the three problems
>> in it, too easy or too hard? Did it take too long or too little time?
>> Did you find that working on a particular part of the assignment gave
>> you greater insight into some aspect of OS design?
>> Is there some particular fact or hint we should give students in
>> future quarters to help them solve the problems? Conversely, did you
>> find any of our guidance to be misleading?
>> Do you have any suggestions for the TAs to more effectively assist
>> students, either for future quarters or the remaining projects?
>> Any other comments?
|
