Monthly Archives: January 2022

CS代写 Question 2: Enzyme Kinetics – cscodehelp代写

Question 2: Enzyme Kinetics
Enzymes are catalysts that help convert molecules that we will call substrates into other
molecules that we will products. They themselves are not changed by the reaction. Within
cells, enzymes are typically proteins. They can speed up biological reactions, sometimes by
up to millions of times. They are also regulated by a very complex set of positive and
negative feedback systems. Computational biologists are painstakingly mapping out this
complex set of reactions. In this problem, we will model and simulate a simplified enzyme
An enzyme E converts the substrate S into the product P through a two-step process. First,
E forms a complex with S to form an intermediate species ES in a reversible manner at the
forward rate k1 and reverse rate k2. The intermediate ES then breaks down into the product
Pat a rate k3, thereby releasing E. Schematically, we write
8.1. Using the law of mass action, write down four equations for the rate of changes of the
four species, E, S, ES, and P.
8.2. Write a code to numerically solve these four equations using the fourth-order Runge-
Kutta method. For this exercise, assume that the initial concentration of E is 1 uM, the initial
concentration of S is 10 uM, and the initial concentrations of ES and Pare both 0. The rate
constants are: K1=100/uM/min, K2=600/min, k3=150/min.
8.3. We define the velocity, V, of the enzymatic reaction to be the rate of change of the
product P. Plot the velocity V as a function of the concentration of the substrate S. You
should find that. when the concentrations of S are small. the velocity V increases
approximately linearly. At large concentrations of S, however, the velocity V saturates to a
maximum value, Vm. Find this value Vm from your plot.

留学生作业代写 ISIT312 or ISIT912. – cscodehelp代写

Question 1. (4 marks)
Based on your own experience of using Apache Pig and Apache Spark in this subject, briefly explain
(i) the similarity of data processing between Apache Pig and Apache Spark, and (ii) the advantages of
Apache Spark over Apache Pig.
Question 2. (4 marks)
A table named X contains a column of keys and a column of values:

Note that the first row of X contains the column names. Explain how to implement the following SQL-
like query in the MapReduce model:
SELECT key, SUM(value) FROM X GROUPBY key
You need to specify the key-value data in the input and output of the Map and Reduce stages.
Question 3. (12 marks)
Read and analyse a specification of data warehouse domain described below.
A university administration would like to record time spent by the students in the lecture classes. To
achieve that, the administration installed at the entries to the lecture halls the devices that can read and
recognise student cards. Now, each time a student enters and leaves a lecture hall she/he swaps a
card against a device, and the total time spent by a student in a lecture hall is computed and recorded.
The administration has the operational databases that contain information about students, subjects,
timetables and enrolments. The administration would like to use these databases and information
obtained from scanning of student cards to create a data warehouse. It should be possible to get from
the warehouse information about the total time spent by each student in lecture classes per given period
of time, such as per day, per week, per month, per session, and per year. It should be possible to get
information about the total number of times each student attended the lectures per day, per week, per
month etc. It should be possible to get information about time spent by each student in the lecture
classes per subject, per degree enrolled, and per school that offers the subjects. It should be also
possible to get information about the total number of students who attended lectures per subject, per
degree enrolled, and per school that offers the subjects.
In your solution, describe each level of dimension with at least 1 and at most 3 attributes. The names
of attributes that you choose must relate to the domain described above. Use either ID tags or
underscores to denote the identifiers. The notations that you use must conform with the one taught in
ISIT312 or ISIT912.
(3.1) Create a conceptual schema for the above specification of a sample data warehouse domain. The
graphical notation that you use must conform with the one taught in ISIT312 or ISIT912.
(10 marks)
(3.2) Use the relational-algebraic notation to specific the following OLAP query:
“Find the total time spent by each student in lecture classes per session and lecture”

Question 4 (8 marks)
Consider the following conceptual schema of some data cube:
first-name
(4.1) Present a drawing of a logical schema based on the above conceptual schema. The notation that
you use must conform with the one taught in ISIT312 or ISIT912.
(3.5 marks)
(4.2) Write the HQL statements that implement the logical schema resulted in the previous step as
internal tables in Hive. (You should make reasonable assumption about the row, column and file formats
of the physical data.)
(4.3) Write an HQL query for finding “the average number of drivers which are associated with a truck”.
(1.5 marks)
Question 5. (6 marks)
Implement as a single Base table a database that contains information described by the following
conceptual schema.

(5.1) Write HBase shell commands that create the HBase table and load some sample data into the
table. The sample data includes information about at least two accidents and two cars and one person
involved in both accidents. All other information is up to vou.
(5.2) Assume that this HBase table has been in use and a lot of data has been populated in it. Write
the HBase shell commands that implement the following queries.
(a) Find all information about the accidents having damages higher than 1000
(b) List the first and last names of people involved in accidents in Sydney in 2019.

CS代考 ECS713U/P Functional Programming 2021/22 – cscodehelp代写

ECS713U/P Functional Programming 2021/22
Individual Coursework
Task: During this individual project you will implement a Haskell stack app that uses threads and concurrent computation. Your task to simulate a social network. The main program
should spawn ten “user” threads, and each of these threads model a user in the social network. The customers should then (at random intervals) choose one of the other users (at
random) and send a random message to that user.
1. Your project should define an appropriate Haskell data type User, which should include their username, and a Message type to keep track of messages between users.
2. Your project should also contain a main thread which creates ten “users” (ten values of type User), and spawns ten threads, one for each of these users.
3. Each user thread should behave as follows: at random time intervals, the thread should select one of the other users at random, and send a random message to that user.
4. Your system should simulate 100 messages, and then terminate and output the final count of how many messages each user received.
5. Make sure each definition includes haddock style comments.
6. You should also write a one-page report, detailing any issues you have faced, and justifying any design decisions you’ve had to make (e.g. how you chose to model the User and
Message types, and how did you choose which MVars to use).
For the top 20% of the mark you must come up with some extension of the given basic specification above. Try to be creative and unique, and describe your extension in the report
(one paragraph should be enough).

CS代考 ECE 391 Exam 2, Fall 2015 – cscodehelp代写

Name: NetID:
ECE 391 Exam 2, Fall 2015
Thursday, November 5, 2015
• Be sure that your exam booklet has 13 pages (not including this one).
• Please write your NetID at the bottom of each page in the space provided. • This is a closed book exam.
• You are allowed two 8 1/2 × 11” sheet of notes.
• Absolutely no interaction between students is allowed.
• Show all of your work.
• Don’t panic, and good luck!

ECE 391, Exam 2
Monday, November 5, 2015
Page Points Score 2 13 45
65 7 11 88
10 10 11 5 12 8 13 5
Points: / 0

(4 points) From the documentation of PAE, you recognize the following properties about the size of the tables:
• The sizes of Page Directories, Tables, and Pages could be different (i.e., they are not all the size of a page like in x86 2-level page table system).
• The total size of the Page Directory is 128 bytes.
• The sizes of Page Table 1 and Page Table 2 are the same.
• The physical pages are 4KB in size, just as in x86.
• Page Table and Directory entries are 64 bits long.
Given this, list out the lengths of each of the fields in the 32-bit virtual address:
PT1 = bits
PT2 = bits Offset = bits
(9 points) Next you found the important information on how each of the entries are stored:
• The Present bit is the most significant bit of each of the entries. If the Present bit is 1, then the entry is valid. Otherwise the entry is invalid.
• The address of the next level of the page tables is stored in the lower bits of the entry.
• The other bits are reserved. You should not change or access them.
• Each Page Directory, Page Table, and Page are aligned to its own size.
• The void * pointers are 64-bit physical addresses. You may want to cast them to the uint64_t
unsigned 64-bit integer data type; gcc allows the full range of arithmetic, logical, and shift operations to operate on this type.
Write the helper functions below to move from one level of the page tables to the next.
/* Takes in the base address of Page Directory and
* virtual address as the argument.
* Returns the base address of Page Table 1 if valid.
* If invalid, returns NULL */
void* PD_to_PT1 (void * PD_addr, uint32_t v_addr) {
ECE 391, Exam 2 Monday, November 5, 2015
Q1: Paging …………………………………………………………………………… 18points The Physical Address Extension (PAE) mode of x86 uses 3-level page entries to be able to address more than 4 GB of physical memory, while keeping a 32-bit virtual address space. It is your job to create a page table walking functions for this page table system that translate a 32-bit virtual address into a 64-bit physical address.
/ 13 2 of 13 NetID:

Question 1 continues. . . ECE 391, Exam 2 Monday, November 5, 2015
/* Takes in the base address of Page Table 1 and
* virtual address as the argument.
* Returns the base address of Page Table 2 if valid.
* If invalid, returns NULL */
void* PT1_to_PT2 (void* PT1_addr, uint32_t v_addr) {
/* Takes in the base address of Page Table 2 and
* virtual address as the argument.
* Returns the base address of the Page if valid.
* If invalid, returns NULL */
void* PT2_to_Page (void* PT2_addr, uint32_t v_addr) {
Points: / 0 3 of 13

Question 1 continues. . . ECE 391, Exam 2 Monday, November 5, 2015
(c) (3 points) Write the full page table walking function to translate a virtual address into its corresponding physical address.
void* PD_to_PT1 (void* PD_addr, uint32_t v_addr);
void* PT1_to_PT2 (void* PT1_addr, uint32_t v_addr);
void* PT2_to_Page (void* PT2_addr, uint32_t v_addr);
void* get_Physical_Address (void* PDBR, uint32_t v_addr) {
(d) (2points) What’sthepurposeofhavingmorethan4GBofphysicalmemoryifonly4GBofvirtualmemory can be addressed?
Points: / 5 4 of 13 NetID:

ECE 391, Exam 2 Monday, November 5, 2015 Q2: Attack of the Stackman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 points
All italicized text is completely optional and unnecessary
There was unrest in the college of engineering. Several incidents of network failure and data loss had frustrated students enough to draw the attention of Obi- and his young apprentice, Stackman John. While Kebailey visited various buildings to investigate, Stackman stayed in a computer lab with LC-3PO and R2-EK to work on a test program for the Tux controller, which he had heard was used by ECE 391 students; he wanted to be just like them.
After several hours of development, EWS went down yet again, while Stackman was editing the graphical compo- nent of his program. Not knowing when it would be possible to continue his work, Stackman set out to investigate on his own, starting with 238 Everitt (the 391 lab at the time). He spotted a shadowy figure in the doorway and ducked behind a corner to listen. The figure was talking on a phone, and from what Stackman could tell, he was a TA of ECE 391, quite possibly the best. The students had procrastinated on a machine problem, and all of the last minute debugging was overloading the network. Somewhat bitterly, he added that due to his relative fame, the students blamed all problems on him, regardless of the situation.
Suddenly, LC-3PO and R2-EK approached in a less than stealthy manner (loudly debating the proper way to indent code). Stackman was not sure if the imposing figure would be as wrathful as the students seemed to think, but he did not want to be caught lurking suspiciously in a dimly lit hallway, so he flew down the stairs and ran across the street to hide in a crowded restaurant. One plate of hot and spicy chicken later, Stackman headed to the depths of Siebel, where he found Kebailey and relayed what he had discovered so they could discuss potential solutions.
A week later, Stackman and Kebailey rode into 238 Everitt on a festive pink pony, bearing exciting news for ECE 391: they would be receiving a server for their class alone, so they would hopefully avoid similar problems in the future. The students and several teaching assistants cheered, but among the balloons and confetti, Stackman could not help but detect one notable absence. . .
Stackman John wrote a Tux driver test program which can display the button status and expected LED status on the screen in Mode X. The LED segments are drawn to the screen when the program attempts to set the LEDs on the device. Buttons are redrawn when a change in status is detected; button and LED drawing are handled in separate threads. For simplicity, all details are drawn directly to video memory (no build buffer).
/ 6 5 of 13
(6 points) Stackman lost several unsaved changes to his code. Complete the redraw_buttons function by filling in the blanks. You may assume that the rest of the code is correct and that button images always start at logical addresses that are multiples of 4.
#define SCREEN_HEIGHT 200
#define SCREEN_WIDTH 320
#define SCREEN_AREA (SCREEN_WIDTH * SCREEN_HEIGHT)
#define SCREEN_PLANE (SCREEN_AREA >> 2)
#define SCREEN_PLANE_WIDTH (SCREEN_WIDTH >> 2)
//button palette indices
#define RED 2
#define GREEN 3
#define BUTTON_DIM 4
#define NUM_BUTTONS 8
/* Provided function defined elsewhere.
* Sets draw mask using lowest four bits, so 0x01 corresponds to plane 0,
* 0x02 corresponds to plane 1, etc.
void set_mask(uint8_t mask);
//Pointer to the start of video memory.
uint8_t * video;
//Array of logical coordinates to upper left corner of each button, in row

Question 2 continues. . . ECE 391, Exam 2 Monday, November 5, 2015
/ 5 6 of 13 NetID:
(2 points) Suppose Stackman wanted to change the color of the LED representation whenever the status of the buttons changes. How could this be done without redrawing the LED segments?
(3 points) The buttons and LED segments do not share any areas of video memory. What synchronization concern, if any, exists? What could go wrong on the screen?
//Button data is stored in the following order:
// {start, c, b, a, right, left, down, up}
uint32_t button_offsets[NUM_BUTTONS];
/* * * * * * * * *
redraw_buttons
Draws buttons as 4×4 squares on the screen,
green for pressed and red otherwise.
uint8_t mask- Bitmask representing the status of each button
(1 for pressed)
in the following order (most significant bit on the left):
| up | down | left | right | a | b | c | start |
Return value: none
void redraw_buttons(uint8_t buttons) {
uint32_t i, j;
uint8_t c;
for (i = 0; i < NUM_BUTTONS; i++) { //determine button color if(buttons & ________________) c = GREEN; //draw button to screen set_mask(_____________); for(j = 0; j < BUTTON_DIM; j++){ video[(_____________________) + j*___________________] = c; ECE 391, Exam 2 Monday, November 5, 2015 Q3: Scheduling....................................................................................19points (a) (8 points) Listed below is a table of processes and associated arrival and run times. Process ID Arrival Time Run Time A04 B23 C45 D61 Show the scheduling order for these processes under the following schedulers: • First-In-First-Out (FIFO) • Shortest-Job First (SJF) with run to completion • Round-Robin (RR) with a quantum = 2 time units Assume that the context switch overhead is 0 and the new processes should be scheduled first if all else is equal. A process arriving at time t can first be scheduled for time slot t to t + 1. If a process ends part way through a quantum, the next process is scheduled immediately. Time Slot 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8 8-9 9-10 10-11 11-12 12-13 13-14 14-15 15-16 16-17 17-18 FIFO SJF RR A A A / 11 7 of 13 (b) (1 point) How long is a typical time slice (quantum)? Circle the correct choice. A. 10–100ns B. 10–100ms C. 10–100s (c) (2 points) What measurement of scheduler performance gets better as the quantum gets bigger? What mea- surement of scheduler performance gets worse as quantum gets bigger? Question 3 continues. . . ECE 391, Exam 2 Monday, November 5, 2015 (d) (2 points) In practice, why can’t we have an arbitrarily small quantum? / 8 8 of 13 NetID: (e) (2 points) What function call in the kernel, previously discussed in class, might cause the process to go to sleep before its allotted time and cause another process to be scheduled? (f) (4 points) In what type of computing environment would a FIFO make the most sense and why? In what type of computing environment would a RR make the more sense and why? (Environments include but are not limited to: home desktop, server, supercomputer, etc. Choose one environment per question.) 1. 08048000-0804c000 r-x 4 1212749 /usr/bin/bar 2. 0804c000-0804d000 rw- 1 1212749 /usr/bin/bar 3. 08642000-08663000 rw- 9 0 4. b7e56000-b7e6f000 r-x 25 13238 5. b7e6f000-b7e70000 r-- 1 13238 6. b7e70000-b7e72000 rw- 2 13238 7. bf99f000-bf9a6000 rw- 7 0 The fields are (from left to right): /lib/libc-2.7.so /lib/libc-2.7.so /lib/libc-2.7.so ECE 391, Exam 2 Monday, November 5, 2015 Q4: Memory Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points On this page, you are presented with the memory maps for two programs, foo and bar. These are edited versions of what you would see in /proc/pid/maps on Linux. 1. 08048000-0804c000 r-x 4 2296660 /usr/bin/foo 2. 0804c000-0804d000 rw- 1 2296660 /usr/bin/foo 3. 09d82000-09d8b000 rw- 9 0 4. b7de0000-b7df9000 r-x 25 13238 5. b7df9000-b7dfa000 r-- 1 13238 6. b7dfa000-b7dfc000 rw- 2 13238 7. bf8e9000-bf8f0000 rw- 7 0 /lib/libc-2.7.so /lib/libc-2.7.so /lib/libc-2.7.so • The memory region number within the process. • Starting and ending virtual address of the mapped region • Mapped region permissions (read, write, execute) • Number of pages in map (decimal) • inode of the file used to provide the data, if any • The file used to provide the data, if any Each row represents a specific memory region. In particular, the 7 rows in each block are memory usage records for the following: 1. Program executable code for the foo/bar program 2. Global variables 4. Executable code from the C library 5. Constants used by the C library 6. Global variables used by the C library 7. Program stack Points: / 0 Question 4 continues. . . ECE 391, Exam 2 Monday, November 5, 2015 / 10 10 of 13 NetID: (a) (4 points) Which of the areas are shared between the foo and bar processes? (I.e., use the same physical memory.) List the area numbers (1–7) (b) (4 points) The user starts a new foo process (from another shell). Which areas are shared between the two foo processes? (2 points) The bar process executes fork() to create a copy of itself. How much extra physical memory is used right after the fork() call? Only count physical pages, and not the space used by page tables or kernel data structures. Explain your answer. (2 points (bonus)) How much space is used by the page tables of the bar process? Assume that all pages of each memory region are currently present in physical memory. Do not include the space used by the page directory or any kernel data structures. ECE 391, Exam 2 Monday, November 5, 2015 Q5: TLB(caching).................................................................................18points Consider a virtual memory system with 4 KB pages, and a TLB that has 3 translation entries. The TLB uses a “least recently used” (LRU) replacement policy. A program operates on a 2-dimensional array of 4 × 2048 32-bit integers, int matrix[4][2048]. The array is stored consecutively in memory, starting at virtual address 0x940000. Table 1 shows the layout of the array. Virtual address 0x940000 0x940004 0x940008 ... 0x942000 0x942004 ... Data matrix[0][0] matrix[0][1] matrix[0][2] ... matrix[1][0] matrix[1][1] ... Consider the following code: result = 0; for (x = 0; x < 2048; x++) { for (y = 0; y < 4; y++) { result += matrix[0][x]*matrix[y][x]; Table 1: matrix array storage in memory (5 points) Show the state of the TLB after each iteration of the inner loop, i.e., after the result += ... instruction has been executed. For each TLB translation entry, write down the virtual address of the corre- sponding page. Assume that the TLB starts out empty, and that the variables x, y, and result are stored in registers and thus do not require memory accesses; likewise, instruction fetches do not use the TLB. The table captures the first six iterations, with the first column already filled in for you. round 1 (x=0, y=0) 0x940000 empty empty round 2 (x=0, y=1) round 3 (x=0, y=2) round 4 (x=0, y=3) round 5 (x=1, y=0) round 6 (x=1, y=1) TLB entry 1 TLB entry 2 TLB entry 3 Question 5 continues. . . ECE 391, Exam 2 Monday, November 5, 2015 (b) (3 points) What is the number of TLB misses that will occur during the execution of the entire program (i.e., 4 × 2048 rounds).? (c) (5 points) Rewrite this code to perform the same calculation with fewer TLB misses Points: / 8 12 of 13 NetID: Question 5 continues. . . ECE 391, Exam 2 Monday, November 5, 2015 (d) (2 points) How many TLB misses will occur during the execution of your revised code? (e) (3 points) Your partner, , has configured the scheduler so that there is a context switch after every inner loop iteration. He notes, with pride, that your optimized code and the original now both incur the same number of TLB misses. Explain why. Points: / 5 13 of 13

CS代考 ECE391: Computer Systems Engineering Fall 2021 – cscodehelp代写

ECE391: Computer Systems Engineering Fall 2021
Machine Problem 2
Midterm 1: Tuesday 28 September Checkpoint 1: Tuesday 5 October Checkpoint 2: Tuesday 12 October
Device, Data, and Timing Abstractions
Read the whole document before you begin, or you may miss points on some requirements, such as the bug log.
In this machine problem, you will extend a video game consisting of about 5,000 lines of code with additional graphical features and a serial port device. The code for the game is reasonably well-documented, and you will need to read and understand the code in order to succeed, thus building your ability to explore and comprehend existing software systems. Most code that you will encounter is neither as small nor as well documented—take a look at some of the Linux sources for comparison—but this assignment should help you start to build the skills necessary to extend more realistic systems. As your effort must span the kernel/user boundary, this assignment will also expose you to some of the mechanisms used to manage these interactions, many of which we will study in more detail later in the course. Before discussing the tasks for the assignment, let’s discuss the skills and knowledge that we want you to gain:
• Learn to write code that interacts directly with devices.
• Learn to abstract devices with system software.
• Learn to manipulate bits and to transform data from one format into another. • Learn the basic structure of an event loop.
• Learn to use a mutex with the pthread API.
Device protocols: We want you to have some experience writing software that interacts directly with devices and must adhere to the protocols specified by those devices. Similar problems arise when one must meet software interface specifications, but you need experience with both in order to recognize the similarities and differences. Unfortunately, most of the devices accessible from within QEMU have fully developed drivers within Linux. The video card, however, is usually managed directly from user-level so as to improve performance, thus most of the code is in other software packages (such as XFree86). We are also fortunate to have a second device designed by and , two previous staff members. The device is a game controller called the Tux Controller (look at the back of the board) that attaches to a USB port. You can find one on each of the machines in the lab. On the Tux Controller board is an FTDI “Virtual Com Port” (VCP) chip, which together with driver software in Windows makes the USB port appear to as an RS232 serial port. QEMU is then configured to map a QEMU-emulated serial port on the virtual machine to the VCP-emulated serial port connected to the Tux Controller. In this assignment, you will write code that interacts directly with both the (emulated) video card and the game controller board.
Device abstraction: Most devices implement only part of the functionality that a typical user might associate with them. For example, disk drives provide only a simple interface through which bits can be stored and retrieved in fixed-size blocks of several kB. All other functionality, including everything from logical partitions and directories to variable-length files and file-sharing semantics, is supported by software, most of which resides in the operating system. In this machine problem, you will abstract some of the functionality provided by the Tux controller board.
Format interchange: This machine problem gives you several opportunities for working with data layout in memory and for transforming data from one form to another. Most of these tasks relate to graphics, and involve taking bit vectors or pixel data laid out in a form convenient to C programmers and changing it into a form easily used by the Video Graphics Array (VGA) operating in mode X. Although the details of the VGA mode X layout are not particularly relevant today, they do represent the end product of good engineers working to push the limits on video technology. If you work with cutting-edge systems, you are likely to encounter situations in which data formats have been contorted for performance or to meet standards, and you are likely to have to develop systems to transform from one format to another.
Event loops: The idea of an event loop is central to a wide range of software systems, ranging from video games and discrete event simulators to graphical user interfaces and web servers. An event loop is not much different than a state

machine implemented in software, and structuring a software system around an event loop can help you to structure your thoughts and the design of the system. In this machine problem, the event loop is already defined for you, but be sure to read it and understand how the implementation enables the integration of various activities and inputs in the game.
Threading: Multiple threads of execution allow logically separate tasks to be executed using synchronous operations. If one thread blocks waiting for an operation to complete, other threads are still free to work. In this machine problem, we illustrate the basic concepts by using a separate thread to clear away status messages after a fixed time has passed. You will need to synchronize your code in the main thread with this helper thread using a Posix mutex. You may want to read the class notes on Posix threads to help you understand these interactions. Later classes will assume knowledge of this material.
Software examples and test strategies: In addition to the five learning objectives for the assignment, this machine problem provides you with examples of software structure as well as testing strategies for software components.
When you design software interfaces, you should do so in a way that allows you to test components separately in this manner and thus to deal with bugs as soon as possible and in as small a body of code as possible. Individual function tests and walking through each function in a debugger are also worthwhile, but hard to justify in an academic setting.
The modex.c file is compiled by the Makefile to create a separate executable that returns your system to text mode. We also made use of a technique known as a memory fence to check some of the more error-prone activities in the file; read the code to understand what a memory fence is and what it does for you.
The Pieces Provided
You are given a working but not fully-functional copy of the source tree for an adventure game along with a skeletal kernel module for the Tux controller. The Tux controller boards are attached to each machine in the lab.
The table below explains the contents of the source files.
adventure.c Game logic, including the main event loop, helper thread, timing logic, display control logic (motion and scrolling), and a simple command interpreter (command execution code is in world.c).
assert.c Support for assertions and cleanups as design and debugging aids.
input.c Input control. Provides for initialization and shutdown of the input controller. The version pro-
vided to you supports keyboard control. You must write the support for the Tux controller. Can be
compiled stand-alone to test the input device.
modex.c Functions to support use of VGA mode X. Includes things like switching from text mode to mode
X and back, and clearing the screens. Provides a logical view window abstraction that is drawn in normal memory and copied into video memory using a double-buffering strategy. When the logical view is shifted, data still on the screen are retained, thus only those portions of the logical view that were not previously visible must be drawn. Finally, supports mapping from pixelized graphics in formats convenient to C into drawing a screen at a certain logical position. Relies on photo.c to provide vertical and horizontal lines from the photo images. Is also compiled stand-alone to create the tr text mode restoration program.
photo.c Support for reading photo and object image data and mapping them into VGA colors. Also draws vertical and horizontal lines into graphics buffers for use with scrolling.
text.c Text font data and conversion from ASCII strings to pixelized graphic images of text (you must write the latter).
world.c Populates game world by setting up virtual rooms, placing objects, and executing commands issued by the player.
We have also included two stripped binaries to illustrate your end goal. The adventure-demo program is a fully working version of the game that allows both keyboard and Tux controller input. The input-demo program is a stand-alone compilation of input.c, again allowing both forms of input. Finally, the mp2photo.c program can be used to transform 24-bit BMP files into photos for the game, and the mp2object.c program can be used for object images. Neither tool is needed for your assignment.

The tr Program
The make file provided to you builds both the adventure game and a text-mode-restoration program called tr. The latter program is provided to help you with debugging. One difficulty involved with debugging code that makes use of the video hardware is that the display may be left in an unusable (that is, non-text-mode) state when the program crashes, hangs, or hits a breakpoint. In order to force the display back into text mode for debugging purposes (or, if you are not running the program in a debugger, to regain control of your shell), you can run the tr program. Unless you are fairly confident in your ability to type without visual feedback, we recommend that you keep a second virtual console (CTRL-ALT-F1 through F6) logged in with the command to execute the text restoration program pre-typed, allowing you to simply switch into that console and press Enter. Using this program is substantially easier than rebooting your machine to put it back into text mode.
You should also look at the cleanup handlers provided by the assert module (assert.h and assert.c). These cleanup handlers provide support for fatal exceptions, putting the machine back into a usable state when your program crashes. However, there may be instances and problems not covered by the handlers, and GDB can stop the program before the handlers are invoked, leaving the machine in an unusable state until you restore text mode with tr.
Mode X and Graphic Images
Mode X is a 256-color graphics mode with 320×200 resolution. It was not supported by the standard graphics routines that came with the original VGAs, but was supported by the VGA hardware itself, and was quickly adopted as the stan- dard for video games at the time because of certain technical advantages over the documented 256-color mode (mode 13h, where the ‘h’ stands for hexadecimal). In particular, mode X supports multiple video pages, allowing a program to switch the display between two screens, drawing only to the screen not currently displayed, and thereby avoiding the annoying flicker effects associated with showing a partially-drawn image. This technique is called double-buffering.
Each pixel in mode X is represented by a one-byte color value. Although only 256 colors are available in mode X, the actual color space is 18-bit, with 6-bit depth for red, green, and blue saturation. A level of indirection is used to map one-byte pixel color values into this space. The table used in this mapping is called a palette, as it is analogous to a painter’s palette, which in theory holds an infinite range of colors, but can only hold a few at any one time. Palettes are often used to reduce the amount of memory necessary to describe an image, and are thus useful on embedded devices even today. For your final projects, some of you may want to play with graphic techniques such as palette color selection to best represent a more detailed image and dithering to map a more detailed image into a given palette.
The mapping between screen pixels and video memory in mode X is a little contorted, but is not as bad as some of the older modes. The screen is first separated into blocks four pixels wide and one pixel high. Each block corresponds to a single memory address from the processor’s point of view. You may at this point wonder how four bytes of data get crammed into a single memory address (one byte in a byte-addressable memory). The answer, of course, is that they don’t. For performance reasons, the VGA memory was 32-bit, and the interface between the processor and the VGA is used to determine how the processor’s 8-bit reads and writes are mapped into the VGA’s 32-bit words. For example, when the processor writes to a memory address, four bits of a specific VGA register are used to enable (1 bits) or disable (0 bits) writes to 8-bit groups of the corresponding word in VGA memory. When drawing rectangles of one color, this mask reduces the work for the processor by a factor of four. When drawing images, however, it poses a problem in that adjacent pixels must be written using different mask register settings. As changing a VGA register value is relatively slow, the right way to use mode X is to split the image data into four groups of interleaved pixels, set the mask for each group, and write each group as a whole using the x86 string instructions (you won’t need to write any of these, although you may want to look at how it is done in the existing code or in the x86 manual).
address 0xA1284 (0xA1234 + 80)
address 0xA12D4 (0xA1234 + 160)
2 3 0 1 2 3 0 1 2 3 0 1 2 3
address 0xA1234
address 0xA1235
address 0xA1236
address 0xA1237
(all at 0xA1236) plane 3

Mode X video memory is memory-mapped and runs from (physical) memory address 0xA0000 to 0xAFFFF, for a total of 216 addresses and 256 kB of addressable memory (counting all four planes). The addresses used in your program are virtual rather than physical addresses, a concept to be discussed later in the course; don’t be surprised if they are not the same as the physical addresses, though. A full screen occupies 320 × 200/4 = 16, 000 addresses, so four fit into the full memory, with a little extra room. The VGA can be directed to start the display from any address in its memory; addresses wrap around if necessary. In the figure shown above, for example, the screen starts at address 0xA1234.
Due to the timing behavior of emulated interactions with video memory, the code provided to you does not use a traditional double-buffering model in which the off-screen image is drawn directly within video memory. As with double-buffering, we do maintain two regions within the video memory for screen images. However, we use regular memory to maintain an image of the screen and to update that image in place. When a new image is ready for display, we copy it into one of two regions of the video memory (the one not being displayed) and then change the VGA registers to display the new image. Copying an entire screen into video memory using one x86 string instruction seems to take about as long as writing a small number of bytes to video memory under QEMU, thus our image display is actually faster than trying to draw a vertical line in video memory, which requires one MOV instruction per vertical pixel.
Only the modex.c file relies on mode X. The rest of the code should use a graphics format more convenient to C. In particular, an image that is X pixels wide and Y pixels high should be placed in an array of dimensions [Y ][X]. The type of the array depends on the color depth of the image, and in our case is an unsigned char to store the 8-bit color index for a pixel. When you write code to generate graphic images from text, as described in a later section, you should use the same format.
Graphical Mapping in the Game
The game shows a two-dimensional photo for each virtual room in the simulated world, and the screen at any time shows a region of the current photo. The photo is fully resident in memory, but could in theory be constructed dynamically as necessary to fill the screen. This facet is useful for games in which drawing the entire virtual world at once requires too much memory.
build buffer
plane 3 of logical view
plane 2 of logical view
plane 1 of logical view
plane 0 of logical view
mapped into build buffer using photo coordinates for mode X planes
planes shift in the build buffer as the logical view moves within the room photo
room photo pixels
(show_x,show_y)
size of scrolling portion of video screen
logical view window
We use a build buffer to keep the pixel data relevant to the screen organized in a form convenient for moving into video memory in mode X. However, in order to avoid having to move the data around a lot in the build buffer (or redraw the whole screen each time we move the logical view window by one pixel), we break the room photo into 4×1 pixel chunks using the mode X mapping illustrated in the previous section. The address of the logical view window in the room photo is used to decide where to place the image planes within the build buffer, and moves around within the build buffer as the logical window moves in the room photo, as shown in the figure below.

this address is in the window for planes 1, 2, and 3
this address is in the window for plane 0
logical view window
The mapping that we have described has a subtle detail: the address range used for the different planes within the logical view window may not be the same. Consider the case shown above, in which show x & 3 == 1. As we move the logical view window around in the room photo, we need to keep each address block at a fixed plane in the build buffer (again to avoid having to copy data around). If we were to keep the planes in the order 0 to 3 and not put any extra space between them, the image of plane 0 would in this case overlap with the image of plane 1 in the build buffer. By reversing the order, we can avoid this problem (alternatively, we could have used a one-byte buffer zone between consecutive planes).
The next problem is mapping the build buffer into the video memory. We use two buffers in video memory and map into the non-displayed buffer, then change the VGA register to show the new screen. You can read about this double- buffering technique in the code and see how it works. The complexity with regard to the plane mapping is that we must map the build buffer planes, which are defined in terms of the room photo coordinates, into the video planes, which are defined in terms of the screen coordinates. The picture below illustrates this problem. In general, a cyclic shift of the planes suffices for the mapping.
logical view window
video screen memory
build buffer layout
build video buffer memory
00 11 22 33
(a cyclic shift of planes)
The next question is the size of the build buffer. If we can limit the size of the room photo, we can allocate a build buffer large enough to hold any logical view window. If the window starts at pixel (0,0) in the room photo, plane 3 is placed at the beginning of the build buffer. If the window occupies the lower right corner of the room photo, plane 0 is placed at the end of the build buffer. Such calculations are not particularly hard.
However, we do not want to restrict the size of the room photo, so we add a level of indirection and move the relative offset of the logical view window within the build buffer as the logical view shifts within the room photo. The room photo can thus be of almost arbitrary size, and is limited only by the size of the coordinate types (32-bit indices).
The img3 and img3 off variables provide the additional level of indirection. At any point in time, adding the address calculated from the logical view window coordinates (show x,show y) to the img3 pointer produces a pointer to the start of plane 3 in the build buffer. However, the actual position of that plane in the build buffer may change over time. Whenever a new logical view window setting is requested, the code checks whether all four planes of the new window

CS代考 ECE391: Computer Systems Engineering Fall 2021 – cscodehelp代写

ECE391: Computer Systems Engineering Fall 2021
Machine Problem 2
Midterm 1: Tuesday 28 September Checkpoint 1: Tuesday 5 October Checkpoint 2: Tuesday 12 October
Device, Data, and Timing Abstractions
Read the whole document before you begin, or you may miss points on some requirements, such as the bug log.
In this machine problem, you will extend a video game consisting of about 5,000 lines of code with additional graphical features and a serial port device. The code for the game is reasonably well-documented, and you will need to read and understand the code in order to succeed, thus building your ability to explore and comprehend existing software systems. Most code that you will encounter is neither as small nor as well documented—take a look at some of the Linux sources for comparison—but this assignment should help you start to build the skills necessary to extend more realistic systems. As your effort must span the kernel/user boundary, this assignment will also expose you to some of the mechanisms used to manage these interactions, many of which we will study in more detail later in the course. Before discussing the tasks for the assignment, let’s discuss the skills and knowledge that we want you to gain:
• Learn to write code that interacts directly with devices.
• Learn to abstract devices with system software.
• Learn to manipulate bits and to transform data from one format into another. • Learn the basic structure of an event loop.
• Learn to use a mutex with the pthread API.
Device protocols: We want you to have some experience writing software that interacts directly with devices and must adhere to the protocols specified by those devices. Similar problems arise when one must meet software interface specifications, but you need experience with both in order to recognize the similarities and differences. Unfortunately, most of the devices accessible from within QEMU have fully developed drivers within Linux. The video card, however, is usually managed directly from user-level so as to improve performance, thus most of the code is in other software packages (such as XFree86). We are also fortunate to have a second device designed by and , two previous staff members. The device is a game controller called the Tux Controller (look at the back of the board) that attaches to a USB port. You can find one on each of the machines in the lab. On the Tux Controller board is an FTDI “Virtual Com Port” (VCP) chip, which together with driver software in Windows makes the USB port appear to as an RS232 serial port. QEMU is then configured to map a QEMU-emulated serial port on the virtual machine to the VCP-emulated serial port connected to the Tux Controller. In this assignment, you will write code that interacts directly with both the (emulated) video card and the game controller board.
Device abstraction: Most devices implement only part of the functionality that a typical user might associate with them. For example, disk drives provide only a simple interface through which bits can be stored and retrieved in fixed-size blocks of several kB. All other functionality, including everything from logical partitions and directories to variable-length files and file-sharing semantics, is supported by software, most of which resides in the operating system. In this machine problem, you will abstract some of the functionality provided by the Tux controller board.
Format interchange: This machine problem gives you several opportunities for working with data layout in memory and for transforming data from one form to another. Most of these tasks relate to graphics, and involve taking bit vectors or pixel data laid out in a form convenient to C programmers and changing it into a form easily used by the Video Graphics Array (VGA) operating in mode X. Although the details of the VGA mode X layout are not particularly relevant today, they do represent the end product of good engineers working to push the limits on video technology. If you work with cutting-edge systems, you are likely to encounter situations in which data formats have been contorted for performance or to meet standards, and you are likely to have to develop systems to transform from one format to another.
Event loops: The idea of an event loop is central to a wide range of software systems, ranging from video games and discrete event simulators to graphical user interfaces and web servers. An event loop is not much different than a state

machine implemented in software, and structuring a software system around an event loop can help you to structure your thoughts and the design of the system. In this machine problem, the event loop is already defined for you, but be sure to read it and understand how the implementation enables the integration of various activities and inputs in the game.
Threading: Multiple threads of execution allow logically separate tasks to be executed using synchronous operations. If one thread blocks waiting for an operation to complete, other threads are still free to work. In this machine problem, we illustrate the basic concepts by using a separate thread to clear away status messages after a fixed time has passed. You will need to synchronize your code in the main thread with this helper thread using a Posix mutex. You may want to read the class notes on Posix threads to help you understand these interactions. Later classes will assume knowledge of this material.
Software examples and test strategies: In addition to the five learning objectives for the assignment, this machine problem provides you with examples of software structure as well as testing strategies for software components.
When you design software interfaces, you should do so in a way that allows you to test components separately in this manner and thus to deal with bugs as soon as possible and in as small a body of code as possible. Individual function tests and walking through each function in a debugger are also worthwhile, but hard to justify in an academic setting.
The modex.c file is compiled by the Makefile to create a separate executable that returns your system to text mode. We also made use of a technique known as a memory fence to check some of the more error-prone activities in the file; read the code to understand what a memory fence is and what it does for you.
The Pieces Provided
You are given a working but not fully-functional copy of the source tree for an adventure game along with a skeletal kernel module for the Tux controller. The Tux controller boards are attached to each machine in the lab.
The table below explains the contents of the source files.
adventure.c Game logic, including the main event loop, helper thread, timing logic, display control logic (motion and scrolling), and a simple command interpreter (command execution code is in world.c).
assert.c Support for assertions and cleanups as design and debugging aids.
input.c Input control. Provides for initialization and shutdown of the input controller. The version pro-
vided to you supports keyboard control. You must write the support for the Tux controller. Can be
compiled stand-alone to test the input device.
modex.c Functions to support use of VGA mode X. Includes things like switching from text mode to mode
X and back, and clearing the screens. Provides a logical view window abstraction that is drawn in normal memory and copied into video memory using a double-buffering strategy. When the logical view is shifted, data still on the screen are retained, thus only those portions of the logical view that were not previously visible must be drawn. Finally, supports mapping from pixelized graphics in formats convenient to C into drawing a screen at a certain logical position. Relies on photo.c to provide vertical and horizontal lines from the photo images. Is also compiled stand-alone to create the tr text mode restoration program.
photo.c Support for reading photo and object image data and mapping them into VGA colors. Also draws vertical and horizontal lines into graphics buffers for use with scrolling.
text.c Text font data and conversion from ASCII strings to pixelized graphic images of text (you must write the latter).
world.c Populates game world by setting up virtual rooms, placing objects, and executing commands issued by the player.
We have also included two stripped binaries to illustrate your end goal. The adventure-demo program is a fully working version of the game that allows both keyboard and Tux controller input. The input-demo program is a stand-alone compilation of input.c, again allowing both forms of input. Finally, the mp2photo.c program can be used to transform 24-bit BMP files into photos for the game, and the mp2object.c program can be used for object images. Neither tool is needed for your assignment.

The tr Program
The make file provided to you builds both the adventure game and a text-mode-restoration program called tr. The latter program is provided to help you with debugging. One difficulty involved with debugging code that makes use of the video hardware is that the display may be left in an unusable (that is, non-text-mode) state when the program crashes, hangs, or hits a breakpoint. In order to force the display back into text mode for debugging purposes (or, if you are not running the program in a debugger, to regain control of your shell), you can run the tr program. Unless you are fairly confident in your ability to type without visual feedback, we recommend that you keep a second virtual console (CTRL-ALT-F1 through F6) logged in with the command to execute the text restoration program pre-typed, allowing you to simply switch into that console and press Enter. Using this program is substantially easier than rebooting your machine to put it back into text mode.
You should also look at the cleanup handlers provided by the assert module (assert.h and assert.c). These cleanup handlers provide support for fatal exceptions, putting the machine back into a usable state when your program crashes. However, there may be instances and problems not covered by the handlers, and GDB can stop the program before the handlers are invoked, leaving the machine in an unusable state until you restore text mode with tr.
Mode X and Graphic Images
Mode X is a 256-color graphics mode with 320×200 resolution. It was not supported by the standard graphics routines that came with the original VGAs, but was supported by the VGA hardware itself, and was quickly adopted as the stan- dard for video games at the time because of certain technical advantages over the documented 256-color mode (mode 13h, where the ‘h’ stands for hexadecimal). In particular, mode X supports multiple video pages, allowing a program to switch the display between two screens, drawing only to the screen not currently displayed, and thereby avoiding the annoying flicker effects associated with showing a partially-drawn image. This technique is called double-buffering.
Each pixel in mode X is represented by a one-byte color value. Although only 256 colors are available in mode X, the actual color space is 18-bit, with 6-bit depth for red, green, and blue saturation. A level of indirection is used to map one-byte pixel color values into this space. The table used in this mapping is called a palette, as it is analogous to a painter’s palette, which in theory holds an infinite range of colors, but can only hold a few at any one time. Palettes are often used to reduce the amount of memory necessary to describe an image, and are thus useful on embedded devices even today. For your final projects, some of you may want to play with graphic techniques such as palette color selection to best represent a more detailed image and dithering to map a more detailed image into a given palette.
The mapping between screen pixels and video memory in mode X is a little contorted, but is not as bad as some of the older modes. The screen is first separated into blocks four pixels wide and one pixel high. Each block corresponds to a single memory address from the processor’s point of view. You may at this point wonder how four bytes of data get crammed into a single memory address (one byte in a byte-addressable memory). The answer, of course, is that they don’t. For performance reasons, the VGA memory was 32-bit, and the interface between the processor and the VGA is used to determine how the processor’s 8-bit reads and writes are mapped into the VGA’s 32-bit words. For example, when the processor writes to a memory address, four bits of a specific VGA register are used to enable (1 bits) or disable (0 bits) writes to 8-bit groups of the corresponding word in VGA memory. When drawing rectangles of one color, this mask reduces the work for the processor by a factor of four. When drawing images, however, it poses a problem in that adjacent pixels must be written using different mask register settings. As changing a VGA register value is relatively slow, the right way to use mode X is to split the image data into four groups of interleaved pixels, set the mask for each group, and write each group as a whole using the x86 string instructions (you won’t need to write any of these, although you may want to look at how it is done in the existing code or in the x86 manual).
address 0xA1284 (0xA1234 + 80)
address 0xA12D4 (0xA1234 + 160)
2 3 0 1 2 3 0 1 2 3 0 1 2 3
address 0xA1234
address 0xA1235
address 0xA1236
address 0xA1237
(all at 0xA1236) plane 3

Mode X video memory is memory-mapped and runs from (physical) memory address 0xA0000 to 0xAFFFF, for a total of 216 addresses and 256 kB of addressable memory (counting all four planes). The addresses used in your program are virtual rather than physical addresses, a concept to be discussed later in the course; don’t be surprised if they are not the same as the physical addresses, though. A full screen occupies 320 × 200/4 = 16, 000 addresses, so four fit into the full memory, with a little extra room. The VGA can be directed to start the display from any address in its memory; addresses wrap around if necessary. In the figure shown above, for example, the screen starts at address 0xA1234.
Due to the timing behavior of emulated interactions with video memory, the code provided to you does not use a traditional double-buffering model in which the off-screen image is drawn directly within video memory. As with double-buffering, we do maintain two regions within the video memory for screen images. However, we use regular memory to maintain an image of the screen and to update that image in place. When a new image is ready for display, we copy it into one of two regions of the video memory (the one not being displayed) and then change the VGA registers to display the new image. Copying an entire screen into video memory using one x86 string instruction seems to take about as long as writing a small number of bytes to video memory under QEMU, thus our image display is actually faster than trying to draw a vertical line in video memory, which requires one MOV instruction per vertical pixel.
Only the modex.c file relies on mode X. The rest of the code should use a graphics format more convenient to C. In particular, an image that is X pixels wide and Y pixels high should be placed in an array of dimensions [Y ][X]. The type of the array depends on the color depth of the image, and in our case is an unsigned char to store the 8-bit color index for a pixel. When you write code to generate graphic images from text, as described in a later section, you should use the same format.
Graphical Mapping in the Game
The game shows a two-dimensional photo for each virtual room in the simulated world, and the screen at any time shows a region of the current photo. The photo is fully resident in memory, but could in theory be constructed dynamically as necessary to fill the screen. This facet is useful for games in which drawing the entire virtual world at once requires too much memory.
build buffer
plane 3 of logical view
plane 2 of logical view
plane 1 of logical view
plane 0 of logical view
mapped into build buffer using photo coordinates for mode X planes
planes shift in the build buffer as the logical view moves within the room photo
room photo pixels
(show_x,show_y)
size of scrolling portion of video screen
logical view window
We use a build buffer to keep the pixel data relevant to the screen organized in a form convenient for moving into video memory in mode X. However, in order to avoid having to move the data around a lot in the build buffer (or redraw the whole screen each time we move the logical view window by one pixel), we break the room photo into 4×1 pixel chunks using the mode X mapping illustrated in the previous section. The address of the logical view window in the room photo is used to decide where to place the image planes within the build buffer, and moves around within the build buffer as the logical window moves in the room photo, as shown in the figure below.

this address is in the window for planes 1, 2, and 3
this address is in the window for plane 0
logical view window
The mapping that we have described has a subtle detail: the address range used for the different planes within the logical view window may not be the same. Consider the case shown above, in which show x & 3 == 1. As we move the logical view window around in the room photo, we need to keep each address block at a fixed plane in the build buffer (again to avoid having to copy data around). If we were to keep the planes in the order 0 to 3 and not put any extra space between them, the image of plane 0 would in this case overlap with the image of plane 1 in the build buffer. By reversing the order, we can avoid this problem (alternatively, we could have used a one-byte buffer zone between consecutive planes).
The next problem is mapping the build buffer into the video memory. We use two buffers in video memory and map into the non-displayed buffer, then change the VGA register to show the new screen. You can read about this double- buffering technique in the code and see how it works. The complexity with regard to the plane mapping is that we must map the build buffer planes, which are defined in terms of the room photo coordinates, into the video planes, which are defined in terms of the screen coordinates. The picture below illustrates this problem. In general, a cyclic shift of the planes suffices for the mapping.
logical view window
video screen memory
build buffer layout
build video buffer memory
00 11 22 33
(a cyclic shift of planes)
The next question is the size of the build buffer. If we can limit the size of the room photo, we can allocate a build buffer large enough to hold any logical view window. If the window starts at pixel (0,0) in the room photo, plane 3 is placed at the beginning of the build buffer. If the window occupies the lower right corner of the room photo, plane 0 is placed at the end of the build buffer. Such calculations are not particularly hard.
However, we do not want to restrict the size of the room photo, so we add a level of indirection and move the relative offset of the logical view window within the build buffer as the logical view shifts within the room photo. The room photo can thus be of almost arbitrary size, and is limited only by the size of the coordinate types (32-bit indices).
The img3 and img3 off variables provide the additional level of indirection. At any point in time, adding the address calculated from the logical view window coordinates (show x,show y) to the img3 pointer produces a pointer to the start of plane 3 in the build buffer. However, the actual position of that plane in the build buffer may change over time. Whenever a new logical view window setting is requested, the code checks whether all four planes of the new window

CS代考 ECE 391 Exam 2, Fall 2014 – cscodehelp代写

Discussion Section:
ECE 391 Exam 2, Fall 2014
Monday, November 10, 2014
⃝ 10 a.m. ( ) ⃝ 11 a.m. ( ) ⃝ 1 p.m. ( ) ⃝ 2 p.m. ( ) ⃝ 3 p.m. ( )
• Be sure that your exam booklet has 10 pages.
• Write your net ID at the top of each page.
• This is a closed book exam.
• You are allowed two 8 1/2 × 11” sheet of notes.
• Absolutely no interaction between students is allowed. • Show all of your work.
• Don’t panic, and good luck!

ECE 391, Exam 2
Monday, November 10, 2014
Page Points Score 39
Points: / 0

ECE 391, Exam 2 Monday, November 10, 2014
Question1: FileSystemFairyTale…………………………………………………………16points In a land far away a file system stood. One from MP3, something to expect, you should. It was a magical place with wonder infused, yet there was one man who was a tad bit confused. He was taking a class, the workload a ton. This class, indeed, was 391. The file system had inodes, files, and even a byte, which the brilliant student just could not get right. He struggled for awhile, he was not a fan. The confusion continued until he developed a plan. He remembered his family, forever matriarchal, whose mother just happened to be the pony Twilight Sparkle. She had some connections to some students who knew, everything that the student would have to do. The student was pleased and thought it was great, anxiously hoping it wasn’t too late. The information finally landed him here, where he requires you students to displace all his fear. If you finish his quest and finish it well, you will be rewarded with points and all will be swell. So grab your quill, pencil, or pen, and finish every task, requested by Ben.
1KB = 1024 B
You may leave expressions in unsimplified form.
Assume only regular files and directories (e.g. no devices).
Points: / 0 2 of 10 NetID:

Question 1 continues. . . ECE 391, Exam 2 Monday, November 10, 2014 (a) (2 points) What is the maximum number of files that this file system can support?
(b) (2 points) What is the maximum size of any single file in this file system?
(c) (5 points) Assume that your file system contains the maximum number of files and that each of those files is 4B. What fraction of the total filesystem size is used for actual data?
Points: / 9 3 of 10 NetID:

Question 1 continues. . . ECE 391, Exam 2 Monday, November 10, 2014 (d) (2 points) Why do the reserved bytes exist in the boot block as well as in each of the directory entries?
(e) (5 points) Describe the process of reading a file from this file system step-by-step
(f) (5 points (bonus)) Implementing write on this filesystem would be inefficient. Explain why and suggest an additional file system data structure that would help.
Points: / 7 4 of 10 NetID:

20 4kB 1 1GB 2 4B ns
ECE 391, Exam 2 Monday, November 10, 2014
Question2: PagingTradeoffs……………………………………………………………..14points
(a) (10 points) wants to explore the tradeoffs between different (hypothetical) paging schemes. Help him fill in the tables below. One row is filled in for you as an example. Assume that the index bits are divided equally between all levels and that the size of one entry in a paging structure is always 4 bytes.
In the last row, you may assume that s is a power of 2 and that n and s are chosen such that the number of index bits (per level) is an integer.
# Levels Size of Pages # Page Offset Bits # Index Bits (/level) 2 4kB 12 10
Size of Pages
Size of One Entry
4B 4B 4B 4B 4B
# Entries (/level) 1024
Size of Paging Data (/level) 4kB
Points: / 10

Question 2 continues. . . ECE 391, Exam 2 Monday, November 10, 2014
(b) (2 points) Why would we choose the paging scheme with one level of 1GB pages over the scheme with 20 levels of 4kB pages?
(c) (2 points) Why would we choose the paging scheme with two levels of 4B pages over the scheme with one level of 1GB pages?
Points: / 4 6 of 10 NetID:

ECE 391, Exam 2 Monday, November 10, 2014
Question3: TLB(caching)………………………………………………………………..18points Consider a virtual memory system with 4 KB pages, and a TLB that has 3 translation entries. The TLB uses a “least recently used” (LRU) replacement policy. A program operates on a 2-dimensional array of 4 × 1024 32-bit integers, int matrix[4][1024]. The array is stored consecutively in memory, starting at virtual address 0xc80000. Table 1 shows the layout of the array.
Virtual address 0xc80000 0xc80004 0xc80008
… 0xc81000 0xc81004
Data matrix[0][0] matrix[0][1] matrix[0][2] … matrix[1][0] matrix[1][1] …
Consider the following code:
result = 0;
for (x = 0; x < 1024; x++) { for (y = 0; y < 4; y++) { result += matrix[0][x]*matrix[y][x]; TLB entry 1 TLB entry 2 TLB entry 3 Table 1: matrix array storage in memory (5 points) Show the state of the TLB after each iteration of the inner loop, i.e., after the result += ... instruction has been executed. For each TLB translation entry, write down the virtual address of the corre- sponding page. Assume that the TLB starts out empty, and that the variables x, y, and result are stored in registers and thus do not require memory accesses; likewise, instruction fetches do not use the TLB. The table captures the first six iterations, with the first column already filled in for you. round 1 (x=0, y=0) 0xc80000 empty empty round 2 (x=0, y=1) round 3 (x=0, y=2) round 4 (x=0, y=3) round 5 (x=1, y=0) round 6 (x=1, y=1) Question 3 continues. . . ECE 391, Exam 2 Monday, November 10, 2014 (b) (3 points) What is the number of TLB misses that will occur during the execution of the entire program (i.e., 4 × 1024 rounds).? (c) (5 points) Rewrite this code to perform the same calculation with fewer TLB misses Points: / 8 8 of 10 NetID: Question 3 continues. . . ECE 391, Exam 2 Monday, November 10, 2014 (d) (2 points) How many TLB misses will occur during the execution of your revised code? (e) (3 points) Your partner, , has configured the scheduler so that there is a context switch after every inner loop iteration. He notes, with pride, that your optimized code and the original now both incur the same number of TLB misses. Explain why. Points: / 5 9 of 10 NetID: ECE 391, Exam 2 Monday, November 10, 2014 Question 4: Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 points (a) (4 points) Give one example each of a IO-bound and a compute-bound process. (b) (4 points) Which of the two processes should have higher priority and why? (c) (2 points) How long is a typical time slice (quantum)? Circle the correct choice. A. 10–100ns B. 10–100ms C. 10–100s (d) (4 points) Describe one advantage and one disadvantage of making a quantum larger. Points: / 14 10 of 10 NetID:

CS代考 ECE391: Computer Systems Engineering Fall 2021 Machine Problem 0 Due: in of – cscodehelp代写

ECE391: Computer Systems Engineering Fall 2021 Machine Problem 0 Due: in office hours by 11:59PM CST Wednesday 1 September
Preparing your Environment
This assignment will help you to prepare your work environment for the class and will introduce you to the tools that you will be using. As mentioned in class, much of your work will be done in the context of a Linux kernel executing on a virtual machine (VM) within Windows. Most of the actual programming and development will be done within the VM. You will demo all of your work to a staff member on one of the lab machines in ECEB at UIUC.
You may want to read the documentation on the tools¡ªavailable on the ECE391 web page¡ªto familiarize yourself with them before starting this assignment. The tools used in this lab include QEMU, Git, GNU Make, and GDB. In addition to the reference materials provided on the web page, you can find information online and can get hands-on experience by logging into one of the EWS Linux machines in ECEB using Windows Remote Desktop (you may need to install this application if you use a Mac). See the class web page for additional instructions on connecting to the lab machines. We encourage you to learn to use a Unix editor, such as vi(m), inside the VM. VSCode, Sublime, and GVIM have also been popular with previous students, so you may want to check those out (install them), but they are not available inside the VM. You can, however, read from and write to the same work directory files that you will compile in your VM. Keep in mind that familiarity with Git¡¯s command-line interface will be useful both in the demo for MP0 and in general in the course.
In this document, Windows menu and submenu selections are represented as slash-separated sequences in small capi- tals. For example, START/COMPUTER means to bring up the START menu, then pick MY COMPUTER. Typing as well as LinuxnamesandcommandsappearinCourier,suchascat > hat.
Step by Step Instructions
Please read through this whole section before you begin, and follow the instructions carefully. Done correctly, on an unloaded network (which will not be the case near the deadline!), the entire machine problem takes less than two hours. Note that if anything gets corrupted, you will have to start over, so start early.
1. Start by opening the class directory (V:ece391) and your work directory (Z:) under Windows. These should appear under THIS PC (START/THIS PC), but you may want to create shortcuts on the desktop by right-clicking on the icons and selecting CREATE SHORTCUT. If the drives are not mapped on lab machine (in ECEB 3026), you may want to map them yourself using THIS PC/VIEW/MAP NETWORK DRIVE. The V: drive should mount \ad.uillinois.eduengr-ewsclassesece391, and the Z: drive should mount \engr-ece-391.ad.uillinois.edu.
2. Open the mp0 folder in the class directory and double click on the ece391setup script. This script takes about seven minutes on an unloaded network and creates the directories vm and source in your work di- rectory. The vm directory holds the snapshot disks for your VM. The source directory contains the source code for the Linux Kernel. The script creates two virtual machines for you: a development machine and a test machine. The development machine is for writing and compiling code. The test machine is for running your code. When debugging the Linux Kernel, your test machine runs your test kernel, while the develop- ment machine runs GDB. The script also creates four shortcuts on your desktop: devel, devel local, test debug, and test nodebug. The devel local is used only for completing MP0. The devel (after step 11) and test (no)debug shortcuts launch their respective virtual machines in QEMU. You will primarily use devel and test debug. test debug launches the test machine and waits for a connection from GDB from the development machine.

Complete steps 3-11 on the same lab machine without logging off. To reduce network load, this lab uses a local file to hold your virtual disk (devel.qcow). Other machines can not make use of this file, and the file will be deleted when you log off. Be sure to copy the file (Step 11) before you log off. If you make a mistake, return to Step 1.
3. You are now ready to boot your new virtual machines. Start by booting the development machine: double click on devel local on your desktop. If a QEMU window does not pop up, you may want to investigate the failure (this skill will be useful later in the class). Right-click on the shortcut on your desktop. Copy the QEMU directory given in the START IN: of the properties dialog. Go to START/RUN, and paste the path from START IN:. The QEMU directory will appear. The stderr.txt file contains error output from the last time QEMU was run, and may help you to identify the problem.
4. Once a QEMU window pops up, wait for the Linux kernel to boot. Ignore errors about IPv6 support. If you click in the QEMU window, you must press Ctrl-Alt to release the mouse. You can type in the virtual machine without clicking in the virtual machine: simply switch to QEMU using Alt-Tab or click on the title bar. When you see a login prompt, log in as user with password ece391. The root account has the same password, but you should not need super-user privileges often on the development machine.
5. Using your favourite Unix editor, open the .bashrc file. Files starting with a period are hidden by default in directory listings; type ls -al to see a more detailed listing if you feel the need to see files before you open them. Find the place in which your NetID should be specified according to the comments in the file and fill it in.
6. Now source the .bashrc script (in other words, use it as a source of commands) by typing either source .bashrcor. .bashrc.Thescriptwillattempttomounttheclassdirectoryandyourworkdirectory within the virtual machine. Normally, this process occurs when you log into the machine, but was skipped the first time because the script did not know your NetID. You need to type your AD password twice, once for each drive. Please do NOT use the number pad to enter your password: certain versions of QEMU/keyboards do not always map the number pad scancodes correctly. If you type your password correctly, the class direc- tory appears under /ece391, and your work directory appears under /workdir. If you need to unmount or remount the drives for some reason, such as mistyping your AD password, use the /root/unmntdrives and /root/mntdrives commands, respectively.
7. Change directory to your virtual machine work directory (cd /workdir/vm) and type ls. Notice that one of the virtual machine snapshot disk files is now visible within the virtual machine (under /workdir/vm). This visibility is analogous to being able to stand outside your body and observe yourself. Changing the file is analogous to conducting surgery on yourself rather than simply observing. If you decide to try it and fail, start again at Step 2.
8. The /workdir/source/linux-2.6.22.5 directory is a working directory for the Linux source. It is a check- out of the Subversion repository located at /workdir/repos/. This code is located on the EWS server so it is backed up. This step requires no action on your part.
9. The next step is to build the Linux kernel. To do so, you must configure the kernel, make dependency informa- tion, clean up the source directories, and then finally compile the sources. We have pre-configured your kernel with minimal options. Kernel configuration allows a wide range of options. Normally, a kernel is configured by themake menuconfigcommandwithinthekernelsourcedirectory(/workdir/source/linux-2.6.22.5). You do not need to do this now since we provide a default configuration. The configuration is stored at /home/user/build/.config (the Linux kernel requires symlinks and a case-sensitive file-system to build on which is why we use /home/user/build to build the kernel while the source is stored on the Engineering file server). After changing the configuration, you must normally re-make the dependency information by typing make dep,thencleanupthedirectoriesbytypingmake clean.Again,thissteprequiresnoactiononyour part.

10. Now you are ready to compile the kernel. Execute the make command in the kernel source directory (/home/user/build). Compiling will take around 50-75 minutes, and much longer if the network is slow (for example, when many people are trying to compile at the same time¡ªdon¡¯t wait for the due date!). If the system reports any errors during the process (the warnings that are generated are not a problem), delete the source folder in your Z: drive, re-run the setup script in Step 2, and execute the make command again.
11. Now you must copy the local QCOW file to your work drive. First, shut down the development machine: type halt,waitforthemessageSystem halted.,andclosethewindow.Aftershuttingdownthedevelopmentma- chine, copy the devel.qcow file from the local machine (C:Users
etiddevel.qcow) to your workdrive (Z:vmdevel.qcow). After the copy has finished, boot the development machine using the devel shortcut on your desktop and log in as user. We also recommend making a backup of the devel.qcow file¡ªa simple copy operation suffices in Windows. If you corrupt your drive later, you can roll back easily to the virtual disk state after finishing the Linux build in the previous step.
12. From the kernel build directory (/home/user/build/) type make install to install the kernel into the cor- rect directories. We have customized the Linux install scripts to copy the bzImage kernel image and vmlinux debug image into the kernel source directory, because the source directory location is accessible to QEMU when you debug your test machine, whereas the build directory resides in the virtual disk of your development machine.
13. Now it¡¯s time to debug your new kernel! Start debugging the test machine by double clicking on test debug. (Ignore messages about the the Windows Firewall, if any appear.) This shortcut opens a QEMU window that is paused waiting for a connection from GDB. Switch back to your development machine and make sure that you are in the kernel build directory (/home/user/build). Start up GDB on the development machine for the kernel (gdb vmlinux). Once GDB has loaded, issue the command target remote 10.0.2.2:1234. This command connects GDB to the kernel executing in the test machine. Ignore the warning about not being able to set a breakpoint.
14. Once GDB is connected to your test kernel, list the CIFS (Common Internet File System) code to open a file by typing: list cifs open. Set a breakpoint at this function by typing: break cifs open. Next, allow the kernel to continue execution by typing c for continue.
Switch to the test virtual machine and wait for the kernel to boot, then log in as user. Repeat Steps 5 and 6 again in the test machine so that your network drives are mounted. Once the directories are mounted in the test machine, type touch /workdir/test and switch back to the development machine. Notice that GDB stopped at the breakpoint when the test kernel tried to open the file. You can now step through the instructions and inspect variables in the kernel, just like debugging any other program. To continue, type c again (you may need to do this a couple times).
15. The last step is to shut down both machines. On the test machine, shut it down cleanly with the halt command. Once it is shut down (The line System halted. will be displayed), you may close the window. Next, quit GDB in the development machine by issuing the quit command. You may have to press Ctrl-C first. Then shut down the development machine, again using the halt command.
16. Good work!

For handin, find any TA in office hours and repeat Steps 13 and 14.
In addition, you will be asked to demonstrate basic knowledge of Git (Note: We will not test Subversion!), GDB, and version control concepts. Being able to use GDB to debug your code is a critical skill for success in this class. For Git, you may want to read the documentation on the course web page in preparation, particularly if you have not already used Git in previous classes (version control systems are all solving the same problem, so don¡¯t panic).
Version control, in the context of this course, is a tool to manage and track changes to your program code. When there are multiple collaborators working on the same project, it becomes a nearly indispensable tool.
For all ECE 391 assignments, you will be required to learn and use Git. All your repositories will be stored on Engineering IT¡¯s instance of GitLab: http://gitlab.engr.illinois.edu/. You may log in using your NetID and password. At the beginning of the semester and before each of the remaining assignments, you will receive an invitation to the ECE 391 group and your repository.

A Couple of Tips
You can keep valuable data in your virtual hard drives, and you may even gain some slight performance advantage by doing so, but if you ever corrupt them, that data is gone. Instead, keep all of your important data under /workdir and use your GitLab repository for your source code.
You may want to use a graphical interface and window manager (GNOME), particularly on your development machine. To do so, log in and perform the following steps:
1. Open /etc/X11/xorg.conf in a text editor, either as root or using sudo to act as root (that is, either log in as roottomakethischange,ortypesomethinglikesudo vi /etc/X11/xorg.conf).
2. Under the Device section, set the Driver to vesa. 3. Save and close the file.
4. Execute the command startx.
When you¡¯re done, you may shut down the virtual machine by using the GNOME menu. Be aware of two issues if you choose to use X, however. We will use some graphics card functionality later in the semester, and X may not play nicely with competing applications, so you should not run it on your test machine with those labs (this aspect doesn¡¯t matter for the development machine).
Your work directory will be deleted at the end of the semester. Be sure to save any source code that you wish to retain by moving it to your home directory or to your own personal data storage.
If you would like to understand the virtual machine organization and how the environment works, see the figure below or ask a TA.
Windows lab machine
network address translation
EWS server
hard drive network /dev/hda eth0
devel machine
hard drive network
devel test .qcow .qcow
work drive (Z:)
MP source code
class drive (V:)
test machine
ece391 .qcow
ece391 .qcow
local disk (C:)
GDB tcp port 1234
tcp kernel port 1234
tcp connection
Figure 1: Diagram of the ECE391 execution environment. Class, home directory, and work directory mounts from the two virtual machines occur as network file systems, and thus occur over the virtual machines¡¯ Ethernet ports. The connections for these mounts are not shown in the diagram. The hard drive connections from the virtual machines are dotted for clarity; only the ECEB Ethernet and ECE server to storage connections are physical.

CS代考 ECE391: Computer Systems Engineering Fall 2021 – cscodehelp代写

ECE391: Computer Systems Engineering Fall 2021
Machine Problem 1
Due: September 14, 5:59 PM
Text-Mode Missile Command
In this machine problem, you will implement a text-mode version of Missile Command, the classic arcade video game, in x86 assembly as an extension to the Linux real-time clock (RTC) driver. This assignment should provide substantial experience with the x86 ISA and provide an introduction to how drivers accomplish tasks inside the Linux kernel. This handout first explains your assignment in detail, then explains several concepts that you will need to understand and implement.
Please read the entire document before you begin.
A Note On This Handout: The sections entitled “Linux Device Driver Overview,” “RTC Overview,” “Ioctl Func- tions,” and “Tasklets” contain background Linux knowledge which is not critical for you to complete this MP. The material described in these background sections will be covered in lecture in the next few weeks, but it may be helpful to read these sections to familiarize yourself with the context of your code in this MP.
Missile Command
In our version of Missile Command, you control a missile silo and try to protect your cities from enemy missiles. You direct your missiles by moving the crosshairs to the intended destination and pressing the spacebar to fire. The explosion generated at that location destroys enemy missiles within a two-square radius. The game ends when enemy missiles destroy all of your cities. Your score is the number of enemy missiles that you destroy.
The implementation of this game centers around a linked list containing an element for each active missile in the game. The game consists of two separate components: the kernel-space code, which manages this list, and the user- space code, which implements the rest of the game and processes user input. You will write a tasklet (see the section “Tasklets”, below) to execute on each interrupt generated by the RTC (see “RTC Overview”) and update the missiles in real-time. This linked list will reside inside the RTC driver in the kernel, so you will also write five ioctl’s (see “Ioctl Functions”) to provide the necessary interface between the kernel-space components of the game and the user-space components.
MP1 Data Structure
Themainstructureyouwillbeworkingwithisstruct missile.
struct missile {
struct missile* next;
int vx, vy;
int dest_x, dest_y;
int exploded;
/* pointer to next missile in linked list */
/* x,y position on screen */
/* x,y velocity vector */
/* location at which the missile explodes */
/* explosion duration counter */
/* character to draw for this missile */
This structure definition is usable only in C programs. There are constants defined for you at the top of the provided mp1.S that give you easy access to the fields in this struct from your assembly code. See the comments in mp1.S for further information on how to use them.
Youmustmaintainalinkedlistofmissileswithonestruct missileforeachactivemissileinthegame.Avariable mp1 missile list has been declared in mp1.S. You should maintain this variable as a pointer to the first element in the linked list.
The x and y fields of the structure contain the current location of the missile on the screen. The text-mode video screen is 80 × 25, i.e., there are 80 columns and 25 rows. In order to allow finer control over the missiles’ velocities, each text-mode location is subdivided into 65536 × 65536 sub-squares. The low 16 bits of the x and y fields determine

which of these sub-squares the missile is in, and the high 16 bits of x and y determine the text-mode video location to draw the missile. This organization makes simultaneously updating both the “game” and “screen” coordinates easy.
The vx and vy fields contain the missile’s velocity, which you must use in your tasklet to update the x and y fields. The dest x and dest y fields contain the missile’s destination, which is the screen location at which it must explode.
When the missile reaches this location, it should stop moving and begin exploding, as explained below.
The exploded field specifies the current state of the missile. When exploded == 0, the missile has not exploded and should continue moving. When it explodes (either because it reached its destination or because another missile exploded nearby), this field will be set to a positive number by the provided function missile explode (see “MP1 Tasklet” for details). While exploded is non-zero, your tasklet treats the missile differently. The missile should not move and should be drawn with the EXPLOSION character defined in mp1.S. Your tasklet should also decrement this field; when it reaches zero the explosion is over and your tasklet should remove the missile from the list and free the associatedstruct missile.
The c field specifies the character with which the missile should be drawn while it is in flight. This ability allows players to visually distinguish between enemy missiles and their own missiles.
MP1 Tasklet
The first function you need to write is called mp1 rtc tasklet. The tasklet must update the state of the game and notify the user-level portion of the code if any cities have been destroyed or the game score has changed. Its C prototype is:
void mp1 rtc tasklet (unsigned long arg);
Every time an RTC interrupt is generated, mp1 rtc tasklet will be called. Your tasklet must perform three different operations. We recommend that you implement each of them as a separate function, and call those functions from mp1 rtc tasklet.
First, your tasklet should walk down the struct missile linked list. For each missile, you should check whether it is currently exploding. If not, then you should update the x and y fields as explained above in the “MP1 Data Structure” section. There are then three cases based on the state and position of the missile.
Processing a missile requires three steps. First, if the missile has moved off of the screen (that is, its screen x coordinate is outside of the range 0-79 or its y coordinate is out of the range 0-24), then the missile should be erased from the screen, removed from the linked list, and its struct missile freed with mp1 free (see “Allocating and Freeing Memory”). Removing a missile from the list should be implemented as a separate function since you may need to perform this operation in more than one place in the code (possibly outside of the tasklet). In this document, we will refer to this function as mp1 missile remove, though you may name it whatever you chose.
Second, if the missile has reached its destination or is currently exploding, you must call missile explode with a pointertothemissile’sstruct missileasanargument.Themissileexplodefunction(providedtoyou)checks whether this missile’s exposion causes any other missiles or any of your cities to explode. If so, it returns a non-zero value. Otherwise, it returns zero. After calling missile explode, you must decrement the exploded field for this missile. If it reaches zero, then the missile is finished exploding and must be erased from the screen, removed from the list, and freed with mp1 free. Otherwise, it should be drawn to the screen with the EXPLOSION character.
Finally, if the missile is simply moving toward its destination, is not exploding, and is still on the screen, you should check whether its screen position has changed. If so, you should erase it from its old position and re-draw it in its new position.
Note that in every case the missile should be re-drawn—it could have been over-written by another missile or the crosshairs moving through the same text-video location. For information on how to draw to the screen, see the “Text- Mode Video” section.
If any call made to missile explode by the tasklet indicated that the status of the game changed (any non-zero return value), you must notify the user-space program once by calling mp1 notify user before the tasklet returns.
After procesing all missiles, your tasklet must proceed with its second operation: redrawing the cities to ensure that

any destroyed cities are drawn as destroyed. Also, if any missile has moved into a text-video location occupied by a city, the city should still be visible. The three cities should be drawn in the bottom row of the screen centered in columns 20, 40, and 60. There are two five-character arrays declared in mp1.S for you, base pic and dead base pic for drawing live and destroyed cities. So, for example, the first city should be drawn in the five video locations from (18,24) to (22, 24). The base alive array indicates whether each city has been destroyed. It contains four bytes; each of the first three is zero if the corresponding base is dead and non-zero if it is alive. The fourth byte is padding.
The third thing your tasklet must do is to redraw the crosshairs. It may have been overwritten by a missile or by a city, and we want to ensure that it is always visible.
MP1 Ioctls
The next function you must write is called mp1 ioctl. Its C prototype is:
int mp1_ioctl (unsigned long arg, unsigned long cmd);
This function serves as a “dispatcher” function. It uses the cmd argument to determine which of the next five functions to jump to. The table below gives a brief summary of cmd values, the corresponding core function, and a brief descrip- tion of what that core function does. Each of the core functions are described in the section entitled “Core Functions.” Note that you must check this cmd value; if it is an invalid command, return -1.
cmd value 0
Core function
mp1 ioctl startgame mp1 ioctl addmissile mp1 ioctl movexhairs mp1 ioctl getstatus mp1 ioctl endgame
Description
starts the missile command game add a new missile
move the crosshairs
get the current game status
end the game
Any value other than 0-4 is an error. Return -1.
The method used to jump to one of the core functions is to use assembly linkage without modifying the stack. A picture of the stack at the beginning of mp1 ioctl is shown below.
(previous stack)
Each of the core functions takes arg directly as its parameter. Since this parameter is passed to the mp1 ioctl func- tion as its first parameter, mp1 ioctl can simply jump directly to the starting point of one of the core functions without modifying the stack. The arg parameter will already be the first parameter on the stack, ready to be used by the core function. In this way, it will appear to the core functions as if they were called directly from the RTC driver using the standard C calling convention without the use of this assembly linkage. Your mp1 ioctl must use a jump table—see the section “Jump Tables” below.
return address
command number

Core Functions
You must implement each of the following five functions in x86 assembly in the mp1.S file.
int mp1 ioctl startgame (unsigned long ignore);
This function is called when the game is about to start. The parameter passed in arg is meaningless and should be ignored. This function should initialize all of the variables used by the driver—all of the variables declared in mp1.S—and the crosshairs should be set to the middle of the screen: (40, 12).
int mp1 ioctl addmissile (struct missile* user missile);
This ioctl must add a new missile to the game. The parameter is a pointer to a struct missile in user space. This function needs to copy the user’s missile into a dynamically allocated buffer in kernel space. If either the dynamic memory allocation (see “Allocating and Freeing Memory” below) or the data copy (see “Moving data to/from the kernel”) fails, this function should return -1. If it does fail, it should be sure to free any memory it has allocated before returning. If it succeeds, it should add the new missile into the linked list and return 0.
int mp1 ioctl movexhairs (unsigned long xhair delta packed);
This function moves the crosshairs. The parameter is a 32-bit integer containing two signed 16-bit integers packed into its low and high words. The low 16 bits contain the amount by which the x component of the crosshair position should change, and the high 16 bits contain the amount by which the y component should change. This function should not allow the crosshairs to be moved off of the screen—that is, it should ensure that the x component of its position stays within the range 0-79, and its y component stays within the range 0-24. If the position of the crosshairs does change, this function should redraw it at its new location. It should never fail, and always return 0.
int mp1 ioctl getstatus (unsigned long* user status);
This function allows the user to retrieve the current score and the status of the three cities. The argument is a pointer to a 32-bit integer in user space. This function should copy the current score into the low 16-bits of that integer, and the status of the three cities into bits 16, 17, and 18. The missile explode function maintains the user’s current score in the mp1 score variable declared in mp1.S. If a city is currently alive, the corresponding bit should be a 1; if it has been destroyed, the bit should be 0. The missile explode function maintains this information in the base alive array, as described above. This function should return 0 if the copy to user space succeeds, and -1 if it fails.
int mp1 ioctl endgame (unsigned long ignore);
Called when the game is over, this function must perform all the cleanup work. It should free all the memory being used by the linked list and then return success. When freeing the list, be careful to avoid accessing any memory that has already been freed.
Synchronization Constraints
The code (both user-level and kernel) for MP1 allows the tasklet to execute in the middle of any of the ioctls, so you must be careful to order the updates properly in some of the operations. Since the tasklet does not modify the list, the main constraint is that any ioctl that modifies the list does so in a way that never leaves the list in an unusable state.
In particular, mp1 ioctl addmissile must fill in the newly allocated structure, including the next field, before changing the head of the list to point to the new structure.
Similarly, mp1 missile remove must remove the element from the list before freeing it; copying the structure’s next pointer into a register is not sufficient, since the tasklet could try to read the structure after the call to mp1 free.

Getting Started
Be sure that your development environment is set up from MP0. In particular, have the base Linux kernel compiled and running on your test machine. Begin MP1 by following these steps:
• We have created a Git repository for you to use for this project. The repository is available at https://gitlab.engr.illinois.edu/ece391 fa21/mp1
and can be accessed from anywhere.
• Access to your Git repositories will be provisioned shortly after the MP is released. Watch your @illinois.edu email for an invitation from Gitlab.
• To use Git on a lab computer, you’ll have to use Git Bash on Windows, not the VM. You are free to download other Git tools as you wish, but this documentation assumes you are using Git Bash. To launch Git Bash, clicktheStartbuttoninWindows,typeingit bash,thenclickonthesearchresultthatsaysGit Bash.
• Run the following commands to make sure the line endings are set to LF (Unix style): git config –global core.autocrlf input
git config –global core.eol lf
• Switch the path in git-bash into your Z: drive by running the command: cd /z
• If you do NOT have a ssh-key configured, clone your git repo in Z: drive by running the command (it will
prompt you for your NETID and AD password):
git clone https://gitlab.engr.illinois.edu/ece391 fa21/mp1 .git mp1 If you do have a ssh-key configured, clone your git repo in Z: drive by running the command:
git clone fa21/mp1 .git mp1
In your devel machine:
• Change directory to your MP1 working directory (cd /workdir/mp1). In that directory, you should find a file called mp1.diff. Copy the file to your Linux kernel directory with
cp mp1.diff /workdir/source/linux-2.6.22.5
• Now change directory to the Linux kernel directory (cd /workdir/source/linux-2.6.22.5). Apply the
mp1.diff patch using
cat mp1.diff | patch -p1
The last argument contains a digit 1, not the lowercase letter L. This command prints the contents of mp1.diff to stdout, then pipes stdout to the patch program, which applies the patch to the Linux source. You should see that the patch modified three files, drivers/char/Makefile, drivers/char/rtc.c, and include/linux/rtc.h. Do NOT try to re-apply the patch, even if it did not work. If it did not work, re- vertall3filestotheiroriginalstateusingSVN(svn revert ).Afterthat,youmaytrytoapply the patch again.
• Change directory back to /workdir/mp1. You are now ready to begin working on MP1.
• Do not commit the Linux source or the kernel build directory. The number of files makes checking out your code take a long time. If during handin, we find the whole kernel source, any object files or the build directory in your repository, you will lose points. We have added a .gitignore file to your initial repository. This file contains all the Git ignore rules that tells Git to not commit the specified file types. The Linux source and kernel build directory are one such example of files that are ignored. Try and explore the .gitignore file to
see what other file types are ignored.
Be sure to use your repository as you work on this MP. You can use it to copy your code from your development ma- chine to the test machine, but it’s also a good idea to commit occasionally so that you protect yourself from accidental loss. Preventable losses due to unfortunate events, including disk loss, will not be met with sympathy.

Due to the critical nature of writing kernel code, it is better to test and debug as much as possible outside the kernel. For example, let’s say that a new piece of code has a bug in it where it fails to check the validity of a pointer passed in to it before using it. Now, say a NULL pointer is passed in and the code attempts to dereference this NULL pointer. When running in user space, Linux catches this attempt to dereference an invalid memory location and sends a signal,1 SEGV, to the program. The program then terminates harmlessly with a “Segmentation fault” error. However, if this same code were run inside the kernel, the kernel would crash, and the only recourse would be to restart the machine.
In addition, debugging kernel code requires the setup you developed in MP0—two machines, connected via a virtual TCP connection, with one running the test kernel and the other running a debugger. In user space, all that’s necessary is a debugger. The development cycle (write-compile-test-debug) in user space is much faster.
For these reasons, we have developed a user-level test harness for you to test your implementation of the additional ioctls and tasklet. This test harness compiles and runs your code as a user-level program, allowing for a much faster development cycle, as well as protecting your test machine from crashing. Using the user-level test harness, you can iron out most of the bugs in your code from user space before integrating them into the kernel’s RTC driver. The functionality is nearly identical to the functionality available if your code were running inside the kernel.
The current harness tests some of the functionality for all the ioctls, but it is not an exhaustive test. It is up to you to ensure that all the functionality works as specified, as your code will be graded with a complete set of tests.
Note: For this assignment, a test harness is provided to you that can test some of the functionality of your code prior to integration with the actual Linux kernel. Future assignments will place progressively more responsibility on you, the student, for develo

CS代考 CS440/ECE448 Artificial Intelligence – cscodehelp代写

CS440/ECE448 Artificial Intelligence
Assignment 1: Naive Bayes
Due date: Monday January 31st, End of the Day Spring 2022

Spam emails are a common issue we all encounter! In this assignment, you will use the Naive Bayes algorithm to train a Spam classifier with a dataset of emails that is provided to you. The task in Part 1 is to learn a bag of words (unigram) model that will classify an email as spam or ham (not spam) based on the words it contains. In Part 2, you will combine the unigram and bigram models to achieve better performance on email classification.

Basic instructions are similar to MP 1:

For general instructions, see the main MP page.
In addition to the standard python libraries, you should import nltk and numpy.
Code will be submitted on gradescope.
Problem Statement
You are given a dataset consisting of Spam and Ham (not spam) emails. Using the training set, you will learn a Naive Bayes classifier that will predict the right class label given an unseen email. Use the development set to test the accuracy of your learned model, with the included function grade.py. We will have multiple hidden test sets that we will use to run your code after you turn it in.

The dataset that we have provided to you consists of 1500 ham and 1500 spam emails, a subset of the Enron-Spam dataset provided by Ion Androutsopoulos. This dataset is split into 2000 training examples and 1000 development examples. This dataset is located in the spam_data folder of the template code provided. You will also find another dataset located under the counter-data folder of the template code – this data is only used by our grade.py file to check whether your model implementation is correct.
Background
The bag of words model in NLP is a simple unigram model which considers a text to be represented as a bag of independent words. That is, we ignore the position the words appear in, and only pay attention to their frequency in the text. Here, each email consists of a group of words. Using Bayes theorem, you need to compute the probability that the label of an email (Y) should be ham (Y=ham) given the words in the email. Thus you need to estimate the posterior probabilities:
P(Y=ham|words)=P(Y=ham)P(words)∏x∈words in the e−mailP(X=x|Y=ham)
P(Y=spam|words)=P(Y=spam)P(words)∏x∈words in the e−mailP(X=x|Y=spam)
You will need to use log of the probabilities to prevent underflow/precision issues; apply log to both sides of the equation. Notice that P(words) is the same in both formulas, so you can omit it (set term to 1).
Part 1: Unigram Model
Before starting: Make sure you install the nltk package with ‘pip install nltk’ and/or ‘pip3 install nltk’, depending on which Python version you plan on using (we suggest you use Python 3.8 or 3.9). Otherwise, the provided code will not run. More information about the package can be found here
Training Phase: Use the training set to build a bag of words model using the emails. Note that the method reader.load_dataset_main is provided which will already pre-process the training set for you, such that the training set is a list of lists of words (each list of words contains all the words in one email). The purpose of the training set is to help you calculate P(X=x|Y=ham) and P(X=x|Y=spam) during the testing (development) phase.
Hint: Think about how you could use the training data to help you calculate P(X=x|Y=ham) and P(X=x|Y=spam) during the development (testing) phase. Note that P(X=tiger|Y=ham) is the probability that any given word, in a ham e-mail, is the word “tiger.” After the training phase, you should be able to compute P(X=x|Y=ham) and P(X=x|Y=spam) for any word. Also, look into using the Counter data structure to make things easier for you coding-wise.

Development Phase: In the development phase, you will calculate the P(Y=ham|words) and P(Y=spam|words) for each email in the development set. You will classify each email in the development set as a ham or spam email depending on which posterior probability is of higher value. You should return a list containing labels for each of the emails in the development set (label order should be the same as the document order in the given development set, so we can grade correctly). Note that your code should use only the training set to learn the individual probabilities. Do not use the development data or any external sources of information.
Hint: Note that the prior probabilities will already be known (since you will specify the positive prior probability yourself when you run the code) and remember that you can simply omit P(words) by setting it to 1. Then, your only remaining task is: for each document in the development set, calculate P(X=x|Y=ham) and P(X=x|Y=spam) for each of the words. After that, you will be able to compute P(Y=ham|words) and P(Y=spam|words) for each email in the development set using the formulas above.

Laplace Smoothing: You will need to make sure you smooth the likelihoods to prevent zero probabilities. In order to accomplish this task, use Laplace smoothing. This is where the Laplace smoothing parameter will come into play. You can use the following formula for Laplace smoothing when calculating the likelihood probabilities:
P(X=x|Y=y)=Count(X=x|Y=y)+kN(Y=y)+k(1+|X|Y=y)
where Count(X=x|Y=y) is the number of times that the word was x given that the label was y, k is the Laplace smoothing parameter, N(Y=y)=∑xCount(X=x|Y=y) is the total number of word tokens that exist in e-mails that are labeled Y=y, and |X|Y=y is the number of distinct word types that exist in e-mails labeled Y=y. A note on out of vocabulary (OOV) words: Suppose that the dev set includes any words that never occurred in the training set. In that case, the term Count(X=x|Y=y)=0, but all of the other terms in the above formula are nonzero, so P(X=x|Y=y)≠0. This should not be something you compute during your analysis of the training set, but it’s a backoff value that you’ll need to have available when you analyze the dev set.

Part 2: Unigram and Bigram Models
For Part 2, you will implement the naive Bayes algorithm over a bigram model (as opposed to a unigram model like in Part 1). Then, you will combine the bigram model and the unigram model into a mixture model defined with parameter λ:
P(Y=Spam|email)=(P(Y=Spam)∏xi∈unigrams in the emailP(X=xi|Y=Spam))1−λ(P(Y=Spam)∏bi∈bigrams in the emailP(Bigrami=bi|Y=Spam))λ
You should not implement the equation above directly — you should implement its logarithm.

You can choose to find the best parameter λ that gives the highest classification accuracy. There are additional parameters that you can tune (for more details, see here). However, I should note that you can get away with not tuning these parameters at all, since the autograder will choose these values for you when you grade. So feel free to play around with these parameters, but in the end, the hyperparameters you choose when you run on your local machine won’t matter in grading.

Some weird things happen when using the bigram model. One of them happens when you use Laplace smoothing to estimate P(Bigrami=bi|Y=y) from training set data. Obviously, Count(Bigrami=bi|Y=spam) is the number of times bigram bi occurred in spam e-mails, and k is the bigram Laplace smoothing coefficient. The weird thing is that N(Y=spam) should equal the total number of bigrams that occurred in spam emails, plus the total number of unigrams that occurred in spam emails. Similarly, |X|Y=spam should equal the total number of distinct bigrams that occurred in spam emails, plus the total number of distinct unigrams that occurred in spam emails. We’re not sure why the bigram model gives higher accuracy with unigrams counted in the denominator, but for some reason, it does.

Part 3: Extra credit
For the extra credit part of this MP, you can try a more informative measure of the importance of each word. tf-idf is used in information retrieval and text mining applications to determine how important a word is to a document within a collection of documents. The tf (term-frequency) term determines how frequently a word appears in a document (thus tf is kind of related to naive Bayes, though it’s not exactly the same thing). The idf (inverse document frequency) term determines how rare (and thus perhaps more informative) a word is in the collection. A high tf-idf score might indicate that a word has high term frequency in a particular document, and also that it is has a low document frequency (low number of documents that contains the given word).

Like a bag-of-words, tf-idf can be used in classifying documents. For the extra credit portion, you will implement tf-idf on the same dataset as Parts 1 and 2. However, since the extra credit portion is worth only 10%, we will ask you to complete an easier task than in Parts 1 and 2. For this part, instead of classifying the documents, you will find the word with the highest tf-idf value from each of the documents in the development set. Your task is to return a list of these words (with the highest tf-idf values).

For this MP, you should treat the entire training dataset (both ham and spam documents) as the collection of documents from which to calculate your idf term. Your idf term for any given word should be calculated based on only the training dataset, not the development dataset. Meanwhile, you should calculate your tf term based on the term frequency in the document you are evaluating from the development set. Please follow this methodology to obtain results consistent with the autograder.

There are multiple ways in which tf-idf gets implemented in practice. For consistency, we will use the following formula to compute tf-idf for any given word:

tf-idf(word w,document A)=(# of times word w appears in doc. A)(total # of words in doc. A)⋅log(total # of docs in train set1 + # of docs in train set containing word w)

If there are terms with the same tf-idf value within the same document, choose the first term for tie-breaking.

Sidenote: A cursory look at the words would show you the importance of governing the outputs of such methods before deploying them on products, but that’s beyond the scope of this assignment. Interested students could look up literature on bias and fairness in AI.

Provided Code Skeleton
We have provided (tar, zip) all the code to get you started on your MP.

Note that the only files you should need to modify are naive_bayes.py for Part 1 and tf-idf.py for Part 2. Those are the only files that you will upload to the autograder.

Files Used for Part 1&2
reader.py – This file is responsible for reading in the data set. It takes in all of the emails, splits each of those emails into a list of words, stems them if you used the –stemming flag, and then stores all of the lists of words into a larger list (so that each individual list of words corresponds with a single email). Note that this file is used for both parts of the assignment (Part 1 and Part 2).
mp1.py – This is the interactive file that starts the program for Part 1, and computes the accuracy, precision, recall, and F1-score using your implementation of naive Bayes.
grade.py – This is a test-grader. It will grade your homework using the provided development test data. The autograder online does some of the same grading, and also grades some hidden tests.
naive_bayes.py – This is the file where you will be doing all of your work for Part 1. The function naiveBayes() takes as input the training data, training labels, development set, smoothing parameter, and positive prior probability. The training data provided is the output from reader.py. The training labels is the list of labels corresponding to each email in the training data. The development set is the list of emails that you are going to test your implementation on. The smoothing parameter is the laplace smoothing parameter you specified with –laplace (it is 1 by default). The positive prior probability is a value between 0 and 1 you specified with –pos_prior. You will have naiveBayes() output the predicted labels for the development set from your Naive Bayes model.
Do not modify the provided code. You will only have to modify naive_bayes.py for Part 1.
Here is an example of how you would run your code for Part 1 from your terminal/shell:
python3 mp1.py –training ../data/spam_data/train –development ../data/spam_data/dev –stemming False –lowercase False –laplace 1.0 –pos_prior 0.8

Here is an example of how you would run your code for Part 2 from your terminal/shell:
python3 mp1.py –bigram True –training ../data/spam_data/train –development ../data/spam_data/dev –stemming False –lowercase False –bigram_laplace 1.0 –bigram_lambda 0.5 –pos_prior 0.8

Note that you can and should change the parameters as necessary. To understand more about how to run the MP for Part 1, run python3 mp1.py -h in your terminal.
Optional: How to change your flag
We provide some flags for you to play around when running your code (for help on how to run the code, see here).

For example, you can use the –lower_case flag to cast all words into lower case. You can also tune the laplace smoothing parameter by using the –laplace flag. You can also tune the –stemming and –pos_prior parameters. You should be able to boost the model performance up a bit by tuning these parameters. However, note that when we grade your MP, we will use our own flags (stemming, lower_case, pos_prior, laplace).

This file, similar to MP1, is for you to be able to evaluate whether or not you have implemented the unigram and mixture models correctly. This file consists of three fundamental tests:
It checks if your mixture model approach is correct (whether or not your model is actually a mixture of unigram and bigram models), using the data located under bigram_check
It checks if your unigram model is able to reach the correct accuracy threshold for the development set provided
It checks if your mixture model is able to reach the correct accuracy threshold for the development set provided
Unlike the grade.py file provided to you in MP1, this version provides you with only a subset of the tests that your code will undergo on gradescope. This file should at least give you a general idea on whether or not your implementations are correct. Your code will go through more tests on datasets not provided to you once it is submitted to gradescope. Here is an example of how you would run grade.py from your terminal/shell:
python3 grade.py

Files Used for Extra Credit
reader.py – This is the same file used in Part 1 and Part 2 (see above for description for this file).
run_tf_idf.py – This is the main file that lets you run the program for the Extra Credit Part.
tf_idf.py – (this is the only file you need to edit) This is the file where you will be doing all of your work for the Extra Credit Part. The function compute_tf_idf() takes as input the training data, training labels, and development set. The training data provided is the output from reader.py. The training labels is the list of labels corresponding to each email in the training data. The development set is the list of emails from which you will extract the words with the highest tf-idf values. You should return a list (with size equal to that of dev_set) that contains words from the development set with the highest tf-idf values. More specifically, the list should contain the word with the highest tf-idf value from each document in the development set. The order of the words in the list returned should correspond to the order of documents in the training data.
grade_tfidf.py – This file allows you to test your code on the development test provided. We will test your code on unseen test, but testing on dev set should give you a general sense of whether your implementation is correct or not.
Do not modify the provided code. You will only have to modify tf_idf.py for the Extra Credit Part. Here is an example of how you would run your code for the Extra Credit Part from your terminal/shell:

python3 run_tests_tfidf.py –training data/spam_data/train –development data/spam_data/dev

What to Submit
Submit only your naive_bayes.py file to Gradescope, under the assignment called MP1.

If you completed the extra credit portion, submit only the tf_idf.py file to Gradescope, under the assignment called MP1: Extra Credit