課程名稱︰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