课程名称︰Android虚拟机与编译器 课程性质︰选修 课程教师：廖世伟 开课学院：电资学院 开课系所︰资工所、网媒所 考试日期（年月日）︰2014.04.14 考试时限（分钟）： 试题 : Android Virtual Machines and Compilers Read Before Answering ‧ You may get partial credits, so please write down some answer. ‧ The problems are not sorted by their difficulty. It is suggested to skim through every questions before you start to answer the questions. ‧ Please mark the number of the question you are answering clearly. On the exam sheet, you are advised to put down questions' answers in order. ‧ Some questions are marked as Open Questions. There is no standard answer for these questions. You are asked to choose one option, and justify your choice with several arguments. You will get the credit only if your arguments support your choice. ‧ There are 20 questions in total. The full score is 100 point. So, on average each question is about 5 points. A. Building Android: 1. What is bionic in Android? (5%) Ans: bionic is the system library that provides almost everything that we can find in glibc and the math library 2(a). Briefly describe the relationship between the Makefile and Android.mk? (5%) Ans: Android.mk is the Android specific Makefile containing standard Makefile commands and Android specific variables, macros and commands. It directs the build system how to build the module described in it. On the top-level directory, there is a Makefile which is the main entry point of all Android.mk. It populates every Android.mk in the source tree to form a very big Makefile that contains every build targets described in each Android.mk. The build system then uses some predefined build commands (gcc or clang or custom tools with options) to build each target. 2(b). When you want to build all of the modules in the current directory, but not their dependencies, what command would you use? (2%) a) make b) mm c) mmm d) m Ans: (b) mm B. Basic Concept on communication and virtualization: 3(a). What is IPC (Inter Process Communication)? (3%) Ans: The way processes in the OS communicate with each other. Shared memory, pipe, sockets are the traditional IPC mechanism. 3(b). Briefly describe the mechanism behind "binder", the Android specific IPC mechanism. (5%) Ans: Binder is the Android specific IPC mechanism. It further abstracts the traditional IPC mechanism in an object/interface oriented fashion. A service provider describes its interface in aidl, the Android interface definition language, then uses the aidl compiler to generate the stub for marshalling/unmarshalling. 4. We had mentioned the concept about "virtualization", please give a brief explanation. (HINT: describe the characteristic of the mapping) (10%) Ans: Virtualization is an isomorphism. In abstract algebra, an isomorphism is a bijective homomorphism. Two mathematical structures are said to be isomorphic if there is an isomorphism between them. ┌───┐ ╭──╮ e(S1) ╭──╮ │Guest │ │ S1 │─────│ S2 │ └───┘ ╰──╯ ╰──╯ State mapping │ │ ↙ V(S1)│ Emulation │V(S2) ↓ ↘ ↓ ┌───┐ ╭──╮ e'(S1') ╭──╮ │Host │ │ S1'│─────│ S2'│ └───┘ ╰──╯ ╰──╯ 5. Regarding JIT & AOT: Which one is using dynamic translation? (2%) Ans: JIT 6. There are "HLL VM Code", "JITed Code", "Native Code". Give the "time space tradeoff" of them. (5%) (Hint: Time: A < B < C, Space: C > B > A) Ans: Frequently executed code in native for speed, infrequently executed code interpreted for space. ← Slower Faster → HLL VM Code JITed Code Native Code ← Smaller Larger → C. Java / Dalvik Virtual Machine: 7. Which one below checks the accessibility of the method during the lookup according to Java Virtual Machine specification? (2%) <a> invokeinterface <b> invokevirtual Ans: <b> 8. Consider the following bytecode listing by disassembling a Java method, please write down its original Java source form: (5%) 0: iconst_2 1: iload_1 2: iload_2 3: iadd 4: imul 5: istore_3 6: iload_3 7: ireturn Ans: int calc(int a, int b){return (a+b)*2;} where "calc" can be any valid method name. 9. Write the equivalent Dalvik bytecode of the following Java bytecode: (3%) iload iload iadd istore Ans: add-int d, s0, s1 10. Compare the design of constant pool between Dalvik and Java virtual machine briefly. (5%) Ans: Dalvik: single constant pool; JVM has multiple constant pools. 11. Zygote is a VM process that starts at system boot time. Please describe its techniques used to speed up Android runtime briefly. (5%) Ans: Zygote forks itself and create new processes with preloaded Dalvik VM instances. copy-on-write D. Java / Dalvik Compilation: 12. Please write down the content in the stack, corresponding to the following calculation in a stack-based virtual machine: b^2 - 4 * a * c. Note that you have to draw the stack content after each execution step. (5%) 13. What are the differences between tracing JIT and method-based JIT? (5%) 14. Please describe the execution flow of a tracing JIT VM. (5%) 15. What is devirtualization and what problem is it designed to solve? (5%) 16. Android's Dalvik JIT uses SSA. Furthermore, Android's DX and LLVM use SSA too. What does SSA stand for? (2%) [hint: SSA is an intermediate representation that facilitates certain code optimizations.] 17. How to convert ordinary code into SSA: Rewrite the following code into SSA form. (7%) x = 5; x = x-3; x < 3 ? / \ y = x*2; y = x-3; w = y; / \ / w = x-y; z = x+y; 18. Explain how SSA form simplifies some compiler analysis. For example, the original program may look like: y = 1; y = 2; x = y; And the corresponding SSA form is: y1 = 1; y2 = 2; x1 = y2; (5%) E. Open Questions: 19. You are developing a huge Android application (e.g. Omlet). However, you have observed that the application needs a long time to start up (longer than 5 seconds sometimes). You can assume that we have used the best algorithm in the application, thus rewriting the application will not reduce the start up time. Besides, we have already enabled the aggressive optimization during the compilation. Please give some guess to explain the long startup time and give a solution. You are required to justify your guess and your solution. (6%) 20. (3%) [送分题] Final Project has been announced late last week. As today (April 21) is the deadline for the Homework #3, now you should start on Final project. To receive score for this 送分题, you need to do 2 things: a. Go to the class website (csie.ntu.edu.tw/~android) to see the final project list. NOW, write down your choice among the proposed project list (You make 1 choice, and can have a backup choice below). Or write down a proposal for your own project here. b. Before this coming Friday's 5pm, go to the class website to sign up. PS: Highlight of Final Project announcement (Also on csie.ntu.edu.tw/~android): ‧ Getting started: Form a group of 2 ~ 4 students now and sign up the project. ‧ Checkpoint 1 in class (10% of your Final Project score), May 5: You report your survey of the problem. The survey should be data-driven and include detailed design of your approach. ‧ Checkpoint 2 in class (20% of your Final Project score), May 26: Your prototype for review. ‧ Checkpoint 3 in class (70% of your Final Project score), June 16: Demo of your project code --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.231.80.207 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1436961907.A.698.html