CS131: Programming Languages
DIS 1D Week 5 Winter 2022
Office Hours:
Copyright By PowCoder代写 加微信 powcoder
Tuesday 8-9pm, Friday 9:30-10:30am Zoom Link on CCLE (Same as discussion)
Discussion Section: 1D, Fridays 2:00 – 3:50pm
• Java Introduction • Homework 3
Java Introduction
• General-purpose, object-oriented language
• One of the most popular programming languages
• Code compiled into bytecode and runs on a virtual machine – What are the pros and cons of this?
• PopularIDEsincludeEclipse,IntellijIDEA
– We don’t require usage of IDE, you can use any text editor for your homework
• HelloWorld.java
• Compliing
Hello world in Java
public class HelloWorld {
public static void main(String[] args) {
System.out.println(“Hello, world”);
– javac HelloWorld.java
– Generates “HelloWorld.class”, containing bytecode
– java HelloWorld
– Note: use class name, not file name
Files in java
• MyClass.java = Code for MyClass
• MyClass.class = Bytecode for MyClass (Compiled from Myclass.java)
• Foo.jar = Java Archive File; ZIP archive
– Often used to package whole compiled application with resources, configuration, etc
– Also used to package source files in Homework 3 – Creating a jar file: jar cf xyz.jar [LIST OF FILES] – Extracting a jar file: jar xf xyz.jar
Java Virtual Machine (JVM)
• Runs bytecode generated by a Java compiler
• Provides separation of code and operating system
• JVM provides garbage collection, just-in- time compilation (JIT), …
• Multiple implementations
– Reference implementation (OpenJDK) provided by Oracle
Java Bytecode
• Acompromisebetweencompiledandinterpretedcode – Platform independence of interpreted code
– Better performance than interpreted code
Key OOP Features in Java
• Abstraction
• Encapsulation
– Binding data with code that manipulates it – Access modifiers: public/protected/private
• Inheratance
– An object may acquire some/all property of another object
• Polymorphism
– One method can have multiple implementations, usage decided at runtime
class Shape { Color color;
Rectangle Square
Inheritance
Object Shape
class Circle extends Shape { float radius;
void draw() {…} }
Inheritance
class Shape {
void draw() { /* do nothing */ } }
class Rectangle extends Shape {
void draw() { /* draw a rectangle */ } }
class Circle extends Shape {
void draw() { /* draw a circle */ } }
class Triangle extends Shape {
void draw() { /* draw a triangle */ } }
Triangle a = new Triangle(); a.draw(); /* draws a triangle */
Shape b = a;
b.draw(); /* draws a triangle */
b = new Circle();
b.draw(); /* draws a circle */
Multiple Inheritance
• Unlike C++, java does not allow multiple inheritance. Why?
UniversityMember
• Defines what a class must be able to do, not how to do it
• Can’t be instantiated, should only be implemented by classes • One class can implement multiple interfaces
interface Vehicle {
public void increaseSpeed(); public void decreaseSpeed(); public void turnLeft();
public void turnRight();
class Car implements Vehicle { public void increaseSpeed() {
/* Press Accelerate Pedal */ }
public void decreaseSpeed() {
/* Press Break Pedal */ }
/* other implementations */ }
Abstract Classes
• Combination of a class and an interface
• Classes can only extend only one abstract or normal class
abstract class Shape { abstract void draw(); void setColor(Color c) {
/* set color */ }
Threads in Java
Creating Threads
public class MyRunnable implements Runnable { public void run() {
System.out.println(“MyRunnable – START “); // Do some heavy processing here System.out.println(“MyRunnable – END “);
// In your main method:
Thread t1 = new Thread(new MyRunnable()); Thread t2 = new Thread(new MyRunnable()); t1.start(); // Start executing thread 1 t2.start(); // Start executing thread 2 t1.join(); // Wait for thread 1 to finish t2.join(); // Wait for thread 2 to finish
Java Memory Model
• Defines how threads interact through memory
Java Memory Model
• “As-if-serial” semantics used within one thread
– Compiler can change your code in any way as long as the result of execution is the same
– e.g. In the following code, x and y are both initially 0
System.out.format(“%d %d\n”, x, y);
System.out.format(“%d %d\n”, x, y); y = 1;
System.out.format(“%d %d\n”, x, y);
– Java may freely reorder the assignment on the left, but not on the right. • With multiple threads things can get more complicated
Problem with concurrency: Data Race • What can happen if we run these two threads simultaneously?
counter += 1;
counter += 1;
Problem with concurrency: Data Race • What can happen if we run these two threads simultaneously?
counter += 1;
counter += 1;
tmp1 = counter; tmp1 = tmp1 + 1; counter = tmp1;
tmp2 = counter; tmp2 = tmp2 + 1; counter = tmp1;
Synchronized keyword • Each object has one lock
• Exclusive access
– Only one thread can enter any synchronized method in one object at once.
• Happens-before relationship
– Everything that one thread did while in a synchroized block will be visible to the next thread entering a synchroized block
• Athreadcancallanyothersynchroizedmethodswhileitholdsthe lock
Synchronized keyword
public class SynchronizedCounter { private int c = 0;
public synchronized void increment() {
public synchronized void decrement() {
public synchronized int value() {
return c; }
Synchronized keyword
• Synchronized can also be used with smaller blocks of code • Avoid blocking others when it’s not necessary
public class SynchronizedCounter { private int c = 0;
public void incrementAndWork() { // … computation here …. synchronized(this) {
// … computation here …. }
Synchronized keyword • Synchronized block can use any object as the lock
public class MyClass {
private int c1 = 0;
private int c2 = 0;
private Object lock1 = new Object(); private Object lock2 = new Object(); public void inc1() {
synchronized(lock1) {
public void inc2() {
synchronized(lock2) {
• Guarantees that other threads will see the changes immediately – Volatile access can not be reordered relative to other reads/writes
– In effect, it is kind of “memory barrier”
• Example:
done = true;
while (!done) {} System.out.println(x)
– In fact, the printed x may not always be 5.
– If done is defined as volatile, then the printed x should be 5.
java.util.concurrent.atomic
• Atomic package provides data types with atomic operations
• Atomic = Other threads do not see intermidiate states, only final state
• For example, AtomicInteger can be used to perform cnt++ as an atomic operation:
AtomicInteger cnt = new AtomicInteger(5); cnt.incrementAndGet();
Homework 3
Homework 3
• Deadline: Feb. 7 (next Monday) 11:55pm
• Topic: “Multithreaded gzip compression”
– In other words “pigz in Java”
– No need to implement the actual compression algorithm yourselves, but to make the existing compression multithreaded
– You can leverage the ideas of an existing implementation called MessAdmin (github), listed on the homework page
GZip Compression in Java
• How to implement a simple “gzip” equivalent in Java
– Take input from stdin, writes output to stdout. Equivalent to “gzip -c -”
import java.io.IOException;
import java.util.zip.GZIPOutputStream;
public class SimpleGZip {
public static void main(String[] args) throws IOException {
GZIPOutputStream gzout = new GZIPOutputStream(System.out); System.in.transferTo(gzout);
gzout.close();
• Your task: implement a multi-threaded “GZIPOutputStream”
Background: gzip compression
• gzip: a stream compression format based on DEFLATE
– Both input and output are binary streams
– Common usage: e.g. file compression (.tar.gz extension)
– Format: RFC1952 (on the right) A gzip file can have one or more “member” shown on the right
– Java implements related algorithms in java.util.zip package
Header extensions
Compressed Data
Tail (checksum + size)
Parallel gzip compression
• Abasicimplementationofgzipprocessthefilelinearly
• Ideastoparallelizecompression(withPthreads)
– Break the files into P partitions, with each thread processing one partition. The compressed partitions are concatenated back
– Pigz’s approach: divide input into fixed size blocks (128kB), and have P threads busily processing a block
– What’s the difference? Why do we prefer the latter in the homework setting?
Other Pigz Details • From pigz’s manual page:
– Checksum: “The individual check value for each chunk is also calculated in parallel… A combined check value is calculated from the individual check values.” (note: not implemented in MessAdmin)
– Dictionary: “The input blocks, while compressed independently, have the last 32K of the previous block loaded as a preset dictionary to preserve the compression effectiveness…”
Setting Up the Java Environment
• Make sure you are using the correct version of Java on SEASnet
• If you are getting “openjdk 1.8” (Java 8) on SEASnet – Add “export PATH=/usr/local/cs/bin:$PATH” in your ~/.profile
• You may also try installing the environment on your own machine – https://www.graalvm.org
– You need the GraalVM and Native Image tool.
Using native-image
• In this homework, you’ll need to test and compare four programs – gzip and pigz in Linux
– Your Pigzj, on JVM and native version (compiled with native-image)
• The native-image tool from GraalVM allows people to compile Java programs to native binaries
– To use it, first compile Java code to class files as usual;
– Then use “native-image ClassName” to compile the java program, and you will get an executable named “classname”
– It can be quite slow on SEASnet, use it when you are sure your java program is functioning correctly with JVM.
Compression library of Java
• The package java.utils.zip in standard java runtime contains implementations of algorithms relevant to this homework
– The official API documentation is here
– For the compression, you will likely use the java.utils.zip.Deflater class,
which allows you to specify the input and dictionary
– We provided hint code (single-threaded) for the logic you will be using. At “Week 5” in BruinLearn”
– java.utils.zip.CRC32 can be used for CRC32 checksum (but you can’t emulate the exact behavior of pigz with it)
Hint Code: MessAdmin
• Githublink:https://github.com/MessAdmin/MessAdmin-Core
– Relevant code: clime.messadmin.utils.compress.{gzip,impl} packages
– The final implementation will need a class similar to PGZIPOutputStream
– You can learn the idea and technique used there, especially the following
• The Compressor class, which uses ThreadPoolExecutor for multithreaded compression execution
• The style of passing tasks among threads • You can also try to design your own style.
Homework requirements • The main program should be named “Pigzj”
– Optionally takes argument “-p processes” to specifiy the threads used, default to the number of processors on the system
– Input taken from stdin, output goes to stdout, no need for file operation
• Other requirements (see the homework page for a complete list) – Correctness: your compressed file should be understood by gzip/pigz
– For full credit, output should only contain a single member
– Ideally, the output should be byte-for-byte identical with pigz output
– Give proper error messages for certain cases
Homework submission
• Submit a single jar file, which contains
– All the source files (.java). Do not add compiled class files!
– A report, containing performance measurement and analysis. Plain text file under 50kB
• Compare the runtime of gzip, pigz and your Pigzj (JVM/GraalVM native) with different settings
• Try to use “strace” and see if the result can explain your findings • …
• Detail on the webpage
Questions?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com