CS 343

Introduction

0.1 Why concurrency

• Processor speed has slowed (stopped)
• Use transistors from Moore’s law for parallelism to increase speed
  • Every 18 months, double number of transistors
• But concurrent programming is still necessary to utilize parallel hardware
  • Very few devices run on single cores
• Some success in implicitly discovering concurrency in sequential programs
  • For a certain class of problems, can convert existing sequential programs into concurrent programs
• Alternately, programmer explicitly thinks about and specifies concurrency
  • Implicit and explicit approaches are complementary
  • Limitations of the implicit approach mandate the explicit approach

0.2 Why C++

• C++ is a dominant programming language
  • Based on C (large programmer- and code-base)
  • as efficient as C in most situations
  • Low-level features, eg. direct memory access, needed for
    • Systems programming
    • Memory management
    • Embedded / real-time
  • High-level features, eg. exception handling, objects, polymorphism, STL, etc.
  • Allows direct interaction with UNIX/Windows

0.3 Concurrency in C++

• C++ originally had no concurrency
  • C++11 only has simple concurrency
• Many different concurrency approahces for C++ have been introduced, with only varying degrees of adoption
• No de factor approach that dominates C++ concurrency programming
  • C has two but incompatible, pthreads and Win32
• C++’s simple concurrency limits its future in parallel computing
• Cannot be safely added to ANY language view library code

0.4 High-Level Concurrnecy

• In theory, and high-level concurrency approach can be used and adapted to C++. Some are better than others
  • C++ is class-based. Need to find a model that matches the models/architecture of your language
• We want a single consistent high-level powerful concurrency mechanism, but what should it look like?
• …

0.5 mC++

Advanced control flow C++

• Integrated advanced control flow tightly packed into C++
  • Leverage class features
  • Threads are light-weight: M:N thread model versus 1:1
• Use mutex objects to contain mutual exclusion and synchronization

0.6 Outline

…

1 Advanced Control Flow (Review)

Basic and advanced control structures allow virtually any control flow

• Still, need more than ifs and whiles
  • eg. do-while, always at least once
    • whiles check at the top, and run through.
    • do-whiles run through, and checks at the bottom
    • What about the middle?

Multi-exit loop

for (;;) {
	// { priming }
	if (...) break;
}

• Can add loop index and take it out freely (as opposed to swap between whiles and fors)

1.1 Static multi-level exit

• Exit multiple control structures wher exit points are known at compile time
• Labelled exit (break/continue) provides this capability

mC++ / Java

L1: {
	// decs
	L2: switch (...) {
		L3: for (...) {
			...
			break L1; // exit block
			...
			break L2; // exit switch
			...
			break L3; // exit loop
		}
	}
}

1.2 Dynamic Memory Allocation

To avoid mark deductions, do not perform dynamic allocation unless necessary

• Dynamic allocation is bad for concurrent programming
• Sometimes, it’s equally bad for sequential programming
• Stacks are more efficient for various reasons than heap allocation
  • Also, does not require explicit storage-management when working with stack

Fundamentally, when a variable’s storage must outlive the block in which it’s allocated, then it must be allocated on the heap

• Exceptions
  • Unknown amount of data (eg. reading from a stream)
    • Vectors heavily utilize the heap (in order to grow larger, needs to allocate heap space)
    • So, be careful of the structures you’re using
  • …
  • …

2 Dynamic Multi-level Exit

• Routine activation (call/invocation) introduces complex control flow.
• Among routines, control flow is controlled by call/return mechanism.
  • Routine h calls g calls f
  • Cannot return from f to h, terminating g
• Modularization
  • Any contiguous code block can be factored into a (helper) routine and called from anywhere in the program (modulo scoping rules)
• Modularization fails when factoring exits, eg. multi-level exits
  • Labels only have routine scope
    • Be wary when moving labels and code (with variables) into a separate routine
    • This is a downstream consequence when switching a style of control flow

How would/could we fix this problem?

• Fundamentally, routines can have multiple outcomes
  • routine call returns normally, ie. statement after the call
  • exceptional returns, ie. control transfers to statements not after the call
    • eg. could not compute width or height, throw exception

[Notes 6]

• Fortran example
• Generalization of multi-exit loops and multi-level exits
• This Pattern addresses a few things
  • Algorithms can have multiple outcomes
  • Separating outcomes makes it easy to read and maintain a program
• Pattern does not handle case of multiple levels of nested modularization
  • …

[Notes 7]

• Dynamic mutli-level exit extend call/return semantics to transfer in the reverse direction to normal routine calls, called a non-local transfer
• We can keep references of labels, and these are determined during run-time, hence dynamic exits

Non-local transfers

• Mechanism behind this is a label variable containing the tuple
  • Pointer to a block activation on the stack
  • Transfer point within the block
• goto L, in f, is a two-step operation
  • Direct control flow to the specified activation on the stack
  • Then go to the transfer point (label) within the routine
• Therefore, a label value is not statically/lexically determined
  • Recursion in g ==> unknown distance from f and h on stack
  • What if L is set during the recursion of h?
• Transfer between goto and label value causes termination of stack block
• …

2.1 Traditional Approaches

• Return code
  • returns value indicating normal or exceptional execution
  • eg. printf() returns number of bytes transmitted, or a neg. val
• Status flag
  • Set shared (global) var indicating normal or exceptional execution
  • the val remains as long as it is not overwritten
  • eg. errno var in UNIX
    • Anytime a library routine is called, it will have a return code, put into errno
• Fix-up routines
  • a global and/or local routine called for an exceptional event to fix-up and return a corrective result so a computation can continue
  • eg. C++ has a global routine-pointer new_handler called when new fails
• Techniques are often combined
  • eg. we should probably check if printf() returns a neg. val, which indicates an error
  • We don’t explicitly do this… ever
    • However, errno will be populated with 27
    • `perror(“printf:”);
      • Looks up errno==27 in its table and prints a message accordingly
  • Finally, can abort() if printf() fails
  • This means every library routine call should introduce a minimum of 3 additional lines
    • Who the fuck does this?
• Intermediate approach of return union, which mimics normal return type
• Return union combines result and return code, and checks code on result access
• ALL routines must return an appropriate union

[Notes 9]

• malloc, for instance, returns a storage, or a “no” message
  • ie. a union of the right and wrong outcome
  • Rust automatically dereferences and checks if malloc fails
    • Forces the check to be done, even if not explicitly performed
  • In Rust, it is literally a union: a struct that contains multiple values
    • eg. Result<void *, NoStorage>

Drawbacks

• Checking return code or status flag is optional
  • can be delayed or omitted, ie. passive vs. active
• Return code mixes exceptional and normal values
  • enlarges type or value range; normal/exceptional type/values should be independent
  • What if we can print negative characters? Then how can we find a value that could also be a return code?
  • If a routine uses all the positives and negatives, how can we steal one of those values to indicate an alternative result?
• Under no circumstance should a library routine abort the program
  • Should pass errors up so that someone else can make the decision as to what to do
  • The error should be passed up multiple levels (eg. A -> C, then back to A?)
• errno could have been changed many times since the error occurred *…
• Local fix-up routines increase the number of parameters
  • Increase cost of each call
  • Must be passed through multiple levels, enlarging parameter lists even when the fix-up routine is not used

…

2.2 Exception Handling (Model)

• Dynamic multi-level exit allows complex forms of transfers among routines
  • Exceptions aren’t “errors”
  • They’re a good way of moving away
  • Exceptions are alternate outcomes, though usually ancillary
  • Exceptional event is an event that is (usually) known to exist
    • Usually occurs with low frequency
    • eg. Division by zero, I/O failures, EOF
• Very difficult to simulate EHM using simpler control structures
• Exceptions are supposed to make certain programming tasks easier, like robust programs
• Robustness results because exceptions are active vs. passive; forcing programs to react immediately when an exceptional event occurs
• An EHM is not a panacea, and is only as good as the programmer using it

2.3 Execution Environment

• An OOP concurrent environment requires a more complex EHM than a non-object-oriented sequential environment
• Sometimes, need to walk through the stack frame and execute all destructores
  • Finally clauses are always executed
    • _Finally in mC++
• …

2.4 Terminology

…

2.5 Static/Dynamic Call/Return

• Static: can deduce exactly what will happen
• Dynamic: when code is being executed, things and executions may change
  • Calls may return statically or dynamically

2.6 Static Propogation (Sequel)

• Case 1) static call, static return
• Sequel
  • Routine with no return value
    • Sequel name is looked up lexically at the call site
    • Though, control returns to the end of the block in which the sequel is declared
      • Doesn’t go back to executing call, so no return values
  • Can change breaks into sequels
• Without sequels, it’s impossible to modularize with static exits
  • Thus, propagation is along the lexical structure
• Adheres to the termination model, as the stack is unwound
• Sequel handles termination for a non-recoverable event (simple execution handling)

{
	sequel StackOverflow(...) {...} // handler
	class stack {
		void push(int i) {
			if (...) StackOverFlow(...); // 2nd outcome
		} // 1st outcome
		...
	}

	stack s;
	...
	s.push(3); // overflow?
}

• The second outcome is basically a simple exception. When it occurs, execution jumps outside of the sequel block
  • Problem, doesn’t work for separate compilation
    • Want to pull stack out into stack.cc?
      • What happens to StackOverflow? Where is the sequel?
      • The sequel has to be seen statically to know where it must jump to after execution
    • This is the same issue with routines’ scope issue
  • Only works for monolithic programs
  • Fails for modular (library) code as the static context of the module and user code are disjoint
• Advantage of the sequel is the handler is statically known (like static multi-level exit), and can be as efficient as a direct transfer

2.7 Dynamic Propagation

Case 3) dynamic call, static return

• Termination
• Also called dynamic multi-level exit
• Advantage
  • Dynamic propagation works for separately-compiled programs
• Disadvantage
  • Handler is not statically known
  • Without dynamic handler selection, the same action and context for that action is executed for every exceptional change in control flow

2.7.1 Termination

• Control transfers from the start of propagation to a handler –> dynamic raise (call)
• When handler returns, it performs a static return –> stack is unwound (like sequel)
• There are 3 basic termination forms for non-recoverable operation
  • non-local, terminate, retry
    • non-local transfer provides general machanism for block transfer on call stack, but has goto problem

Terminate provides limited mechanism for block transfer on the call stack (like labelled break)

• Catches are similar to sequel. They both have static returns, and jump to the end of the block (next line after block)

Retry is a combination of termination with special handler semantics

• ie. restart the guarded block handling the exception
• Pretend EOF is an exception of type Eof
  • Not supposed to get out of retry until contract is fulfilled
  • Can have alternative ideas than catch clauses
• With just a normal catch clause and a few extra lines, can simulate retries very easily
  • Don’t need an extra construct, so C++, Java, etc. don’t have it
• …

Case 4) dynamic call, dynamic return

Resumption

• provides a limited mechanism to generate new blocks on the call stack
• control transfers from the start of propagation to a handler –> dynamic raise (call)
• when handler returns, it is a dynamic return –> stack is not unwound (like routines)
• Using _CatchResume clauses and _Resume raises, when the closing brace is reached in the _CatchResume, execution is returned to the _Resume call, not the next line after the handler
  • O(n) search, which we don’t get from an O(1) return call
  • Normally, we’d have to pass a fixups around

2.9 Exceptional Control-Flow

Shits bonkers, yo

3.0 Coroutines

A coroutine is a routine that can also be suspended at some point and resumed from that point when control returns

• A calls B, B calls C, C goes back to B
  • That sounds like routine calls to me
    • Yes! But, C doesn’t terminate… (?)
• The state of a coroutine consists of
  • An execution location, starting at the beginning of the coroutine and remembered at each suspend
  • An execution state, holding the data created by the code the coroutine is executing
    • Each coroutine has its own stack, containing its local vars and those of any routines it calls
  • An execution status, active, inactive, or terminated
    • Changes as control resumes and suspends in a coroutine

• Not a normal routine because coroutine creates a new stack, and starts running there

• Coroutines handle the class of problems that need to retain state between calls
  • eg. plugins, device drivers, finite-state machines
• Coroutines exectue asyncly with other coroutines, hence no concurrency among coroutines
  • Coroutines are the precursor to concurrent tasks, and introduce the complex concept of suspending and resuming on separate stacks

When you create a routine, you don’t declare whether its recursive or sequential.

• Semi-coroutines and full-coroutines are different types, non-declarative
  • Semi-coroutines act asymmetrically, like non-recursive routines, by implicitly reactivating the coroutine that previously activated it
  • Full-coroutines …

3.1 Semi-Coroutine

3.1.1 Fibonacci Sequence

• Direct method is simple enough
• Create a routine called fibonacci()
  • Problem, after every fibonacci call, we’d lose data regarding the already-computed values
  • We needed to introduce global fn1 and fn2 variables to retain state
  • Also, fibonacci has three different states
    • if n==0, n==1, or n>1
      • Which state? They return different things
• Classes are fun, but still don’t get the job done too well
  • We can create a Fibonacci class, and encapsulate our global variables
  • Also, can now have multiple instances, so create fn1 and fn2
    • next() generates the next Fibonacci number for the given instance
  • Still has flag variables

Using coroutines

_Coroutine Fibonacci {
	int fn;
	void main() {
		int fn1, fn2; // retained between resumes
		fn=0;
		fn1=fn;
		suspend()
		fn=1;
		fn2=fn1;
		fn1=fn;
		suspend()

		for (;;) {
			fn = fn1+fn2;
			fn2=fn1;
			fn1=fn;
			suspend()
		}
	}

	public:
	int next() {
		resume(); // only resume (which increments our fib number) when necessarily
		return fn;
	}
}

int main() {
	Fibonacci f1, f2;
	for (int i=0; i<=10; i+= 1) {
		cout << f1.next() << " " << f2.next() << endl;
	}
}

• No explicit execution state!
• _Coroutine type wraps coroutine and provides all class properties
• Distinguished member main (coroutine main) can be suspended and resumed
• No parameters or return value (supplied by public members and communication vars)
• main can be called (even recursively), but is normally private/protected
  • This is so that outsiders cannot fuck around with your coroutine
  • Outsiders can only interact with your coroutine in the ways you provide

Coroutines do context switches

• On resume, will context-switch over to the coroutine stack
• On suspend, will context-switch over to the main stack, or whoever called the coroutine
• For example above, the frame for next() goes on the main stack
  • Doesn’t context switch until later. Sometimes, we don’t even need to resume/suspend, so it’s not a great idea to automatically context-switch
  • Even being on the main stack, it can still access variables from the coroutine(s) stack
  • Uses this variable to execute magic
• By using separate stacks, coroutines get the power that they do
• First resume starts main on new stack (cocall)
  • Subsequent resumes reactivate last suspend
  • suspend reactivates last resume
• Object becomes a coroutine on first resume
  • Coroutine becomes an object when main ends
• Routine frame at the top of the stack knows where to activate execution
  • suspend/resume are protected members to prevent external calls
    • So other people can’t diddle with your coroutine’s execution
    • Only protected when inheritance is needed
• Coroutine main does not have to return before a coroutine object is deleted
• When deleted, a coroutine’s stack is always unwound and any destructors executed
  • Why?

3.1.2 Format Output (Example)

• Unstructured input: abcedfghijklmnopqrstuvwxyzabcedfghijklmnopqrstuvwxyz
• Structed output

abcd efgh ijkl mnop qrst
uvwx yzab cdef ghij klmn
opqr stuv wxyz

• Blocks of 4 letters, separated by 2 spaces, grouped into lines of 5 blocks
• Traditionally, we’d use loops directly
  • [Notes 30]
  • If we try to modularize this code, we need to maintain variables for number of blocks and size of blocks
    • Need to remember how many characters are in current block

• …

• Coroutine trick
  • resume in the constructor
  • Normally, first time a public member is called, it will resume, which is the cocall and makes the stack
  • However, sometimes, we don’t want the user to make the first resume
    • This allows the programmer to make the cocall. This allows priming, putting the execution in the right position so that the first user resume makes sense
    • Sure, why not. I don’t ask questions

A1 Hint(s)

Don’t need to do money as a coroutine

• Easiest way to write a coroutine is to pretend you’re a freshman
  • Just write the code straight up and get it working
  • Then change it into a coroutine
• Much like formatter, our A1Q3 coroutine takes some input values and determines if the input is valid

3.1.3 Correct Coroutine Usage

• Eliminate computation or flag variables retaining information about execution state
• We had our good version of the Fibonacci coroutine
  • However, consider the example using a switch statement
    • In this case, an explicit flag var controls execution state
    • Original program structure is lost in the switch

3.1.4 Coroutine Construction

• Fastest way to write a simple coroutine? Write it out directly, with some inputs and output, and take that code and put it in a coroutine, subject to change
  • Works well enough for simple coroutines
  • Put processing code into coroutine main
  • Converting reads if program is consuming or writes if program is producing to suspend
    • Fibonacci consumes nothing and produces Fibonacci numbers –> converts writes (cout) to suspends
    • Formatter consumes chars and only indirectly produces output (as side-effect) –> convert reads (cin) to suspends

4.0 mC++ Exception Handling Model

• In A1Q3, need to throw an exception from one coroutine to another coroutine
• mC++ exceptions are generated from a specific kind of type, which can be thrown and/or resumed
  • All exception types are grouped into a hierarchy
  • mC++ provides a set of predefined exception-types covering exceptional runtime and I/O events
• mC++ restricts raising to a specific exception type
• Supports two forms of raising, throwing, and resuming
• Supports two kinds of handlers, termination, and resumption, which match with the kind of raise
• Supports propagation of nonlocal and concurrent exceptions
  • Cross-stack exceptions

4.1 Exception Type

• C++ allows any type to be used as an exception type. mC++ restricts exception types to those defined by _Event

_Event exception-type-name {
	...
};

• An exception type has all the properties of a class
  • As well, every exception type must have a public default and copy constructor
• An exception is the same as a class-object with respect to creation and destruction

_Event D { ... };
D d;
_Resume d;
D *dp = new D;
_Resume *dp;
delete dp;
_Throw D();

• Note, C++ throw doesn’t have all the special features that _Throw does

4.2 Inherited Members

Each exception type inherits the following members from uBaseEvent

…

4.3 Raising

…

• Can use _Throw, or maybe event throw, but the former provides additional funtionality

4.4 Handler

• mC++ has two kinds of handlers, termination and resumption. They match with the kind of raise

Termination

• The mC++ termination handler is the catch clause of a try block, same as C++

Resumption

• A resumption handler is often a corrective action for a failing operation
• Unlike normal routine calls, the call to a resumption handler is dynamically bound rather than statically bound
  • mC++ extends the try block to include resumption handlers
  • Resumption handler is enoted by a _CatchResume clause at the end of a try block

try {
	...
}
_CatchResume(E1 &) { ... }
// more _CatchResume clauses
_CatchResume(...) { ... }
catch(E2 &) { ... }
// more catch clauses
catch(...) { ... }

• Any number of resumption handlers can be associated with a try block
• All _CatchResume handlers much precede any catch handlers
  • The former is dynamic, the latter is catch
  • The former goes back to the raise, while the latter continues afterwards
• Like catch(...), _CatchResume(...) must appear at the end of the list of the resumption handlers
• Resumption handler cannot perform a break, continue, or return

…

Something about unwinding stack

…

4.5 Nonlocal Exceptions

• Nonlocal exceptions are exceptions raised by a source execution at a faulting execution
• Nonlocal exceptions are possible because each coroutine (execution) has its own stack
  • Nonlocal has to throw something at someone that has a stack

…

Problems with not using coroutines?

Device driver example
> Flow becomes linearized without coroutines. There is a very specific order of execution and it usually involves a method beginning and ending
> This can lead to inefficient code and over-complication, because we're forced to comply with the structure and flow of a regular method

CS349, 2017-05-01

INTRODUCTION

User interface: place where a person expresses intention to an artifact, and the artifact presents feedback to the person.

• the term artifact can apply to any object, so things have hammers have “user interfaces” too…

Interactive System Architecture

• [user] expresses –> [artifact] translates –> [artifact] presents –> [user] perceives

Model-View-Controller (MVC)

1. [user] expresses intention
2. [artifact] translates in the Controller, changes data in the Model, and notifies the View to update and present new visuals
3. [user] perceives

Example

• graphical temperature control
  • [user] expresses intention (e.g. mouse movements, mouse events)
  • [artifact] Controller translates mouse events
  • [artifact] changes Model data (sets max=30, temp=18, min=10)
  • [artifact] Model notifies View (draws widget with new data, and presents it to the user)

Interface vs. Interaction

• Interface
  • external presentation to user
    • controls (what the user can manipulate/use to communicate an intent)
    • visual, physical, auditory (what program uses to communicate its response)
• Interaction
  • used to connote behaviour: user must invoke to perform a task and the corresponding responses
    • interaction is action and dialog(ue)
    • unfolds over time

Why is interaction design difficult?

• Variability in users and tasks
  • varying levels of expertise among users
  • often, a range of tasks will be performed using the same tool. How can we anticipate all the possible use cases and scenarios?
• No single “right way” to design an interface: can always be improved
• Pushing technology forward requires us to rethink interaction (innovate according to new expectations)

Why study interaction?

• Well-designed interfaces empower users to do things they couldn’t otherwise do
  • movie production/editing, image editing, desktop publishing, …
• Interaction is key to enabling new technologies
  • multi-touch and gestures
  • voice interfaces
  • touch screens for tablets/notebooks

This course will focus on the interaction and development of user-interfaces, not the user experience. User-centered design is covered in CS449

• how to design, implement, and evaluate user interfaces
  • provide foundational knowledge for building highly interactive, usable desktop, web, and mobile applications
  • illustrate underlying architecture of modern GUI toolkits
  • explore strategies applicable across a range of interface problems
  • explore essential design tools, techniques, and processes
• ways to understand users
  • the physical and cognitive abilities of users
  • visual design principles

See L1 Slides for info about assignments and the assignment assessment (skill tree)…

CS349, 2017-05-03

…

CS349, 2017-05-05

CS349, 2017-05-08

Design Principles

The goals of “good design”

• What kind of devices do we want to make?
• Useful vs. usable

Example: A remote control

• Jakob Nielsen (UI Researcher) says he only uses 33% of the buttons on a remote control with regularity
• The others only cause confusion and clutter
• Obscure labels

As time goes by, devices (like remote controls) reach higher capabilities than humans

• Usefulness: meeting specific needs & supporting real tasks; the quality of being practically useful
  • If there’s a high functionality (e.g. lots of items in a menu), usefulness may be high
• Useability: the effectiveness, efficiency, and satisfation with which users can achieve tasks in a particular environment with a product
  • If the interface is poor and tasks aren’t easily done, then useability is low while usefulness may (or may not) be high.

In solutioning, we strive to achieve the optimal balance between the two.

Example: Refrigerator temperature control

Two controls: one for fridge and one for freezer. This implies that there are two systems/valves (or sources). However, these controls simply adjust the cold air flow coming from a single source, split into two.

• This is somewhat un-useable, due to a lack of transparency

What can we learn?

• Help form correct mental models (fridges, doors, phones)
• Provide explicit controls for high-use functions
• Appearances should reflect or suggest usage
  • e.g. push plates when doors are push to open, and pull handles when doors are pull to open
• Low-use functions shouldn’t have the same level of suport as high-use functions
  • e.g. volume buttons on a remote are much more often used than the “setting” button
• Give feedback of operations in progress
  • Helps improve transparency

Mental Models

Three models of a system

• Developer’s model
  • How the programmer believe the system should be used
• System model
  • The system itself
• User’s (mental) model
  • How the user of a system believes the system should be used

The goal is to have these three images align as closely as possible. Mental models drive how users interact with a system

Model of Interaction

The basic idea is simple. To get something done, you have to start with some notion of what is wanted — the goal that is to be achieved. Then you have to do something to the world, that is, take action to move yourself or manipulate someone or something. Finally, you check to see that your goal was made.

Four things to consider

• the goal
• what is done in the world
• the world itself
• the check of the world

The action itself has two major aspects:

• Doing something: Execution
  • What we want to do to the system
• Checking something: Evaluation
  • Comparing: what happened vs. our goal

CS349, 2017-05-10

UI Design Principles, cont’d

Design principles serve to

• reduce gulf of execution and gulf of evaluation
• create and reinforce a more correct mental model for the user

Aspects of design principles

1. Perceived affordances
2. Mapping
   • Physical actions of input device mapped to a UI instrument
   • Instrument’s actions mapped to an object of interest
     • Degree of integration
       • ration of DOF of device to on-screen actions
     • Degree of compatibility
       • similarity in action and effect
   • Some things work well in the physical world, but not in virtual world
   • The relationship between two things: control movement and the effect it has in the world. Three types of mapping:
     • Layout
       • Burners on a stove and control dials should have the same arrangement
       • Radio buttons (single choice) should clearly map to a single section
     • Behaviour
       • Turning a car steering wheel in a certain direction should move the car in that direction
     • Meanings (conventions)
       • Emergency buttons are red
       • Up/clockwise means “more”
   • Components often mimic physical controls and follow the same conventions and mappings
3. Consistency
   • Designing interfaces to have similar operations and use similar elements for achieving similar tasks
   • Follows rules, such as using the same name operation to select all objects
     • e.g. hovering over an object, and left-clicking to select
     • e.g. right-click to bring up a context-menu w/ actions
4. Constraints
   • Guide by preventing certain actions while enabling/encouraging others
   • Example: Norman’s Lego Motorcycle
     • Physical: Lego blocks only fit one way
     • Semantic: Based on meaning. E.g. windshield protects driver, so it should go in front of the seat
     • Cultural: Red “means” brake
     • Logical: The last piece goes in the last remaining spot
   • Example: “Settings” on slide 48
     • Physical: You can only slide the slider so far left or right, bounded by 0% and 100%
     • Semantic: Folder icons indicate that files can be placed inside
     • Cultural: The dropdown icon indicates the color selection can be expanded
     • Logical: Naming of folders map to specific organization(s)
   • There isn’t a single set of cultural constraints. Certain places expect a RTL display. It’s important to understand the audience when dealing with cultural constraints.
5. Visibility
   • …
6. Feedback
   • Can happen at different levels
     • Widgets (like a button): do they articulate
       • that they are enabled or disabled?
       • that they have focus?
       • its current stateÉ
   • Does feedback communicate affordances?
   • When the user acts, does something happen on screen?
   • Is the user able to perceive new state of system model once the action is complete?
   • Examples of poor feedback:
     • Creating symbolic links in Linux
     • Online video buffering
   • Examples of good feedback:
     • Search and replace in Sublime Text
7. Metaphor
   • Set of unifying concepts in a GUI used to simplify interaction
   • Done by borrowing concepts from one domain (the source, or vehicle) and applying them to another (the target, or tenor)
   • Scale can vary from system, to application, to UI feature
   • Examples
     • Desktop metaphor in windowing systems
       • Microsoft Bob: metaphor gone too far. Does the desktop need to reflect your bedroom, or your workspace?
     • Assembly-line metaphor for a new car configurator
     • Shopping-cart metaphor for online shopping
     • Cassette tape player for music player
     • Stacked transparencies metaphor for layers in a graphics editor
     • Recycling bin metaphor for deleting files
   • Given an idea for a metaphor, analyze the contrasting features of source and target domain
   • Analyze relationship between features
     • too many features from base domain results in conceptual baggage
     • Too few features leads to confusion, poor mapping, poor metaphor
   • Experience to see if people can use metaphors to derive expectations of behaviours

CS349, 2017-05-12

Visual Design

You need to present the elements of your interface to the user. User needs to know

• What can I do in this interface?
• Where is the thing I’m looking for?
• What is expected of me?
• What is related to what?

The program wants to impose as little thinking as possible on the user. Allow them to concentrate on the task, not the interface

1. Highest level design goals
   • Make supported actions clear
   • Create desired relationships and avoid undesired relationships
2. Create a presentation that…
   • Has an attractive look
   • Is easy to understand at a galance
   • Has a distinctive, recognizable look.
3. Avoid a presentation that…
   • Is cluttered/hard to organize
   • Is hard to perceive clearly
   • Contains excessive idiosyncrasy
   • Makes the user stop to think about avoiding errors

Design with the human brain’s conscious and unconscious capabailities in mind

1. Keep things simple
   • people have limited cognitive processing power
2. Leverage pre-attentive processes
   • make design seem intuitive, obvious, and focused

Pre-attentive processes

• Happen at a lower level than conscious thought
• Do a huge amount of work out of sight, and gives your conscious mind the results

Simplicity

In anything at all, perfection is finally attained not when there is no longer anything to add, but when there is no longer anything to take away.

Antoine de Saint Exupery

• Present the minimum amount of information to achieve maximum effect
• Simplicity leads to quickly recognized and understood functionality
  • Less information means less process time
  • Can produce correct mental models more effectively/quickly
• Simplicity also aids recall
  • Less to remember. Easier to retain critical information

To achieve simplicity, reduce, reduce, and reduce.

Organization and Structure

Gestalt Principles

• Structure doesn’t occur naturally. It must be explicitly created and designed
• People will find order, even if none was intended
  • Don’t just throw elements into a UI
• Need to explicity create the structure
  • Consciously consider what placement and arrangement communicates to the user
• Gestalt principles can help with this. Theories of visual perception that describe how people tend to organize visual elements into groups or unified wholes
• Clues about how the brain groups raw visual output

Proximity

Individual elements are associated more strongly with nearby elements than those further away * e.g. spacing stars more closely vertically gives the impression of columns. Closer horizontally gives the impression of rows.

Similarity

Elements associate more strongly when they share basic visual characteristics, such as

• shape
• size
• colour
• texture
• orientation

Good continuation

Our visual system is biased to perceive continuous forms rather than disconnected segments

• Elements arranged in a straight line or smooth curve are perceived as being more related than elements not on the line or curve.
• See slides 22-24

Grouping v. Ambiguity

…

Closure

We tend to see a complete figure even when parts of the information is missing. We tend to perceive a set of individual elements as a single, recognizable pattern, rather than multiple individual elements.

• Generally, we can fill in the gaps.
  • e.g. Positive/negative designs
  • e.g. Cascading windows: even without a distinct border on each window, we can usually recognize the borders of a window based on the content in the window

Figure/Ground

Our mind separates the visual field into the figure and the ground

• Figure is the visual element that is interpreted as being the object of interest
• Ground is the area on which it rests (and everythign else)

Law of Pragnanz

We tend to interpret ambiguous images as simple and complete, versus complex and incomplete

• Ambiguous images: those that can be interpreted in more than one way
• Images recalled from memory are simplified
• Design
  • Minimize the number of elements
  • Symmetrical composition is perceived as simpler

Uniform connectedness

Elements connected to one another by uniform visual properties are perceived to be more related than elements that are not connected

Two typical strategies

1. connecting lines
2. common regions

Alignment

Not necessarily a Gestalt principle, but it is a powerful organizing tool

• Some in the design community include it, but it doesn’t appear in the original lierature
  • for exams, it is

CS349, 2017-05-15

Visual Design, cont’d

Pleasing Layouts

Gestalt principles applied to user-interface layouts

• Lots in common with graphic design
• Four principles

1. Proximity

Items relating to each other should be grouped close together. When several items are in close proximity to each other, they become one visual unit … This helps organize information and reduces clutter

Williams, p. 14

1. Alignment

Nothing should be placed on the page arbitrarily. Every element should have some visual connection with another element on the page. This creates a clean, sophisticated, fresh look.

Williams, p. 14

• Examples, edge alignment and center alignment

1. Repetition

Repeat visual elements … throughout the piece. You can repeat colour, shape, texture, spatial relationships, line thicknesses, sizes, etc. This helps develop the organization and strengthens the unity.

Williams, p. 14

1. Contrast

The idea behind contrast is to avoid elements on the page that are mearly similar. If the elements (type, colour, size, line thickness, shape, space, etc) are not the same, then make them very different. Contrast is often the most important visual attraction on the page.

Williams, p. 14

Applying Concepts

Common Mistakes

• Haphazard layout (no explicit design)
• Aligning labels, not controls
• Bounding boxes create clutter and compete for attention

Testing it out

• Show it to someone else
  • Don’t ask if they like it, ask why.
  • Try to get first impressions
    • First impressions define whether or not the interface is good. You can’t afford to rely on people “warming up” to your designs
• Use the squint test
  • Mimics early portion of visual recognition system

Impact

• Good visual design can reduce human processing time
• Tullis redesigned lodging information screens (1984)
  • 5.5s v. 3.2s average search times

Summary

• Strive for simplicity
• The Gestalt principles provide insights into the pre-attentive processes in the brain
• Use the principles to struture a visual design by…
  • grouping visual information into higher-level units
  • establishing relationships between related eleemnts
• Don’t leave visual design up to chance
  • Think about your design
  • Test it out

CS349, 2017-05-17

Design

A Design Process: User-Centered Design

To make things usable and useful, you need to understand the people who use your software

The philosophy

• Ask real people what they need
• Ask people what problems they have with current solution
• Think about the people who will use your software
• Test your ideas with people

Developers are not people

Some History

Refined at Apple, with the Mac user-interface

Process

• User studies: bring in users, provide mockups, assess
• Implementation: iterate based on (agile) feedback
  • Fix problems, update solutions, etc
• Usability studies: more users, more video, more analysis

Problems

• Time: adds 1-2 years to the development cycle
• Changes: no “cutoff” for changes!

Solutions

• Manage through iteration (Agile process)

Principles

1. Understand the user’s needs
   • Build a product that meets real needs rather than building it because it can be built
2. Design the UI first
   • Design the UI first, and then design the architecture to support the UI
3. Iterate
   • You won’t create the best UI design on the first tr
   • A great design requires attention
4. Use it yourself
   • You’ll find obvious problems that can be fixed while it’s still easy to fix
     • If the development process goes too far, there are too many dependencies. It becomes difficult to make certain changes based on a lack of isolation
5. Observe others using it
   • It’s critical to observe other people using your UI in a realistic way very early in the development cycle

We will not focus much on the “Design the Architecture”, “Choose a set of scenarios”, “Implement the Scenarios” sections.

A) Understand the user

1. Observe existing solutions
   • As well as what’s wrong with them
2. List scenarios
   • Literally all the things your users want/need to do
   • Scenarios
     • are stories of people undertaking activities with technology
     • they are a natural way to think
       • easy to understand (for devs and users)
       • contain sequencing data(?)
     • must be refined/elaborated with appropriate detail
       • exactly what the user does
       • how UI changes in response
     • have pitfalls:
       • typically crowds out the exceptional use-cases and users
       • often fail to catch “oughts”
       • cannot be formalized (this is also a strength)
     • have variations
     • should be retained
       • written v. memorized v. generated on demand
3. List functions required by scenarios and prioritize functions
   • Some functions will be required by several scenarios
   • Prioritize
     • Critical, Important, or Nice to have
4. List functions by frequency and commonality
   • Frequent use by many
     • Visible, few clicks away
   • Frequent use by few
     • Suggested, few clicks
   • Occasional by many
     • Suggested, more clicks
   • Occasional by few
     • Hidden, more clicks away

B) Design the UI

• Identify/design widgets (components) and widget types to support prioritized functionality
  • e.g. text fields, buttons, etc
• Balance functionality with well-understood widget types
  • i.e. customized control v. familiar controls
• Assign attributes
  • Model
    • what data does it need
  • Affordances
    • what can you do with it?
  • Presentation
    • how does it appear in the UI?

Component Distribution

• Temporal distribution
  • When components appear, the flow from one interface to another
• Spacing distribution
  • Where components appear on an individual interface section
  • Use visual design & Gestalt principles

Design the flow of the UI. Which screens lead to which, etc

Storyboards

• Quick way to sketch out sequences and schematics
  • could form the basis of a paper prototype
• Typically linked to a scenario

Macro and Micro Structure

• Interaction Sequences
  • macro-structure, convey the big picture of system interaction
  • e.g. Phone Book – Add New Entry –> Edit Entry – Submit –> Match to Existing Entry
  • uses labeled boxes and arrows, but sometimes a more extensive visual vocabulary may be helpful
• Interface Schematics
  • micro-structure, convey essentials and functionality at individual steps of interaction

Need both to describe a user interface

Visual Vocabulary

• A standard set of graphical symbols and notation to describe something
• Qualities of a good UI design visual vocabulary
  • Whiteboard-compatible
  • Tool-indepedent
  • Small and self-contained
• The UML tends to be too formal (too “high ceremony”)
• Jesse James Garret’s visual vocabulary
  • Good, but web-centric
• Find a consisten visual vocabulary that works for you

Interface Schematics

• Includes enough detail so that someone could begin designing and implementing system logic
  • visual arrangement of content/information
  • functionality of interface (widgets, forms, data)
  • navigational and content elements ordered to convey structure and meaning
  • indicates the relative significance of all elements
• Interface schematics are not the same as
  • graphic design mockup
  • paper prototypes
• See notes for examples on interface schematics

For a list of wireframe drawing tools and image editing software, see course notes [29]

CS349, 2017-05-19

PROTOTYPING

• Iteration and refinement
• Might take successive versions to “get it right”

Process

• User studies
  • bring in users, provide mockups, assess
• Implementation
  • iterate based on feedback
• Usability studies
  • more users, video, analysis

A limited representation of a design that allows people to interact with it and explore its suitability

• Goal: Maximum Feedback, Minimum Effort

Examples

• paper sketches/collage with “human computer processor”
• slide show or video simulating the use of a system
• physical model (wood, cardboard, etc.)
• software or hardware with limited functionality

Prototype Objectives

Build “working” prototype from design work

• Aid in discussions with stakeholders
• Help communication of ideas among team members
• For user evaluation
• For technical/layout testing and fine-tuning

What to Prototype?

Difficult, controversial, and critical areas

Possible aspects to test

1. Concepts and terminology
2. Nagivation, task flow
3. Mental models
4. Documentation, help
5. Layout, colours, fonts, graphic elements, “brand”
6. Custom widgets
7. Performance metrics
8. Technical feasibility
9. Usefulness

Fidelity

Faithfulness of prototype appearance and performance to final product

• Low
  • prototype doesn’t look much like the final product. Operation may be simulated and slower
• High
  • prototype looks and operates like the real product

Paper Prototyping

Usability Testing where representative users perform realistic tasks by interacting with a paper version of the interface that is manipulated by a person playing computer, who doesn’t explain how the interface is intended to work.

Snyder, 2003, p. 4

Wizard of Oz Technique

Evaluate unimplemented technology by using a human to simulate the response of a system

• Much easier to do this technique than implement complex features

Paper Prototyping Image Quality

1. Rendering: How good should it look?
   • Good enough to elicit feedback about critical/risky design issues
2. Creation speed is of the essence
3. Modifications: When?
   • While user is present
   • Get immediate feedback. Make changes without losing users’ context
   • Consider allowing the user to make changes
4. Coding effort in paper prototyping is always zero
5. No code to write or rewrite until design is stabilized

Interactive Prototyping

Example

Tools

1. Figma
2. Axure RP
3. Sketch
4. inVision
5. UXPin

Summary

Usability and usefulness are important properties that don’t just happen. User Centered Design is a process:

• Understand the user needs
• Design the UI first
• Iterate on design
• Use it yourself
• Observe others using it

CS349, 2017-05-23

WINDOWING SYSTEMS

Windowing functions Base Window System v. Window Manager

GUI Characteristics

• GUI architectures share common characteristics
  • support output to a graphical display
    • display text/high-resolution graphics
  • Handle user input from multiple devices
    • minimally, keyboard (text) and a positional input device (mouse)
  • Provide an interface to display/manipulate content
    • Most modern GUIs use a desktop metaphor
      • windows contain data and can be manipulated (resized, moved, overlap, etc)
    • Common GUI elements: scrollbars, buttons, etc
• A windowing system provides input, output, and window management capabilities to the operating system
  • Before windowing systems, systems typically ran a single application, which dominated the screen (DOS, BIOS, etc)
  • With windowing systems, programs can run simultaneously, each with their own separate window. Windows may exist side-by-side, or overlap. Input is directed to the focused/correct window by the windowing system

Base Window System (BWS)

• Lowest level abstraction for windowing system
  • routines for creating, destroying, and managing windows
• Routes mouse and keyboard input to correct window
  • only one window has focus to receive input
• Ensures only one application changing frame buffer (video memory) at a time
  • one reason single-threaded/non-thread-safe GUI architectures are popular
• The BWS provides each program with a window, and manages access to that window
  • the BWS provides a drawing canvas abstraction
  • The application is shielded from details of frame buffer, visibility of the window, and all other application windows
  • each window has own coordinate system
    • BWS transforms between global (screen) and local (window) coordinate systems
    • Each window does not need to worry where it is on screen. Its top-left is (0,0)
  • BWS provides graphics routines to the program for drawing

Window Manager

• Provides conceptually different functionality
  • layered on top of BWS
  • provides interactive components for windows (menus, close box, resize capabilities)
  • creates the look and feel of each window
• Application “owns” the contents of the window, but the window manager owns the application itself

Application Window v. Application “Canvas”

• The window manager owns the window (including its controls)
  • the close, minimize, fullscreen buttons
  • the application title
  • the window frame
• the application owns the canvas

Types of Window Managers

1. Tiling Window Manager
   • paints all windows by placing them side-by-side or above and below each other
   • There is no window overlap
2. Stacking Window Manager
   • Allows windows to overlap by drawing background windows first, then drawing the foreground windows on top of them
3. Compositing Window Manager
   • Lets all windows be drawn separately, and then puts them all together and draws them all using 2D or 3D techniques
   • More complex, but provides extra functionality
     • e.g. cascading visuals when alt-tabbing
     • e.g. partial transparency of windows

BWS v. Window Managers

1. Unixes and Linuxes
   • separate the BWS and window manager
     • separation of BWS from WM:
       • enables many alternative looks and feels for the windowing system
       • one of the keys to X11’s lasting power: can innovate by changing the WM layer
       • resiliency, since BWS and WM are separate processes
   • BWS: X Window System
   • Stacking WM: Fluxbox, Openbox, Window Maker, etc
   • Compositing WM; Compiz, KWin, etc
2. Windows Vista, 7, 8, 10 and MacOS combine the BWS and WM. Or, at least, doesn’t distinguish between the two
   • Windows; Desktop Window Manager (BWS & Compositing WM)
   • MacOS; Quartz Compositor (BWS & Compositing WM)
   • Trade-offs in approaches?
     • Look and feel
     • Window management possibilities
     • Input possibilities

Conceptually, on both platforms, there is a separation of canvas (assigned to application) and window decoration/OS overlay handled by window manager

• Lines between do blur when combined, however
• e.g. Windows fast access menu-bar in the window frame

X Windows (X11) System

• Base windowing system, separate from the operating system
  • not a window manager
  • does not specify the style of user interface
• What does it do?
  • A protocol to create windows, handle input, draw graphics
  • A standard for low-level graphical output and user input

Design Criteria

1. Implementable on a variety of displays
2. Applications must be device independent
3. Must be network transparent
4. Support multiple, concurrent application displays
5. Support many different applications
6. Support output to overlapping windows (even when partially obscured)
7. Support a hierarchy of resizable windows (an application can use many windows at once)
8. High performance, high-quality text, 2-D graphics, imaging
9. System should be extensible

Displays, Screens, Windows

• In X, a display may have multiple screens
• A display may have multiple windows
• A window may cross multiple screens

X Client-Server Architecture [27]

…

Structure of a Typical X Program

1. Perform client initialization
2. Connect to the X server
3. Perform X related init
4. Event loop
   • get next event from the X server
   • handle the event
     • if the event was a quit message, exit
     • do any client-related work
   • send drawing requests to the X server
5. Close down the connection to the X server
6. Perform client cleanup

Xlib, an X Windows Library, is provided [s31]. Note that X is relatively complex.

Contrast: Opening a Window in Java

import javax.swing.\*;

public class TestWindow extends JFrame {
    public TextWindow() {
        this.setTitle(...)
        this.setDefaultCloseOperation(JFrame.EXIT\_ON\_CLOSE);
    }
    public static void main(String args[]) {
        TestWindow myWindow = new TestWindow();
        myWindow.setSize(400,300);
        myWindow.setVisible(true);
    }
}

Recap: X Windows Design

• Much of XWindows architecture was influenced by its time period
  • larger server machines and low-cost client displays because computation was expensive
• As computation got cheaper, certain aspects of program behaviour could be assumed
  • …

Appendix: Running X11 sample code [35]. Not covered in lectures/exams

CS349, 2017-05-24

MODERN GUI SYSTEMS

…

JAVA GUI PROGRAMMING

A quick-start guide to building Swing applications

The Java Platform

Everything Is A Class

• Classes, objects are core language constructs
• Object-oriented features
  • polymorphism, encapsulation, inheritance
• Static and member variables and methods
• Resembles C++
  • Differences
    • no pointers
    • no type ambiguity
    • no destructor
    • single inheritance model

JDK [L7_S14]

Classes and Packages [S8_S16]

Class Hierarchy

• Implicit class hierarchy
  • All classes in Java are derived from the Object class
    • clone(), toString(), finalize()
  • Classes you write will inherit this basic behaviour

Initiating Objects

• Primitive types are allocated on the stack, passed by value
• Objects are allocated on the heap, passed by reference
  • technically, the value of address passed on the stack, but this behaves like pass-by-reference
  • practically, this means you don’t need to worry about pointer semantics in parameter passing
    • Bicycle my_bike = new Bicycle();
    • Bicycle kids_bike = my_bike
      • both refer to the same memory on the heap

Composition: Inner Classes

class ShadowTest {
    public int x = 0;

    class FirstLevel {
        public int x = 1;

        void method(int x) {
            print("ShadowTest.this.x="+ShadowTest.this.x);
            // 0
            print(x); // watch the scope
            // 23
        }
    }

    public static void main(String... args) {
        ShadowTest st = new ShadowTest();
        ShadowTest.FirstLevel f = st.new FirstLevel();
        f.method(23);
    }
}

Inheritance & Subtype Polymorphism

Increase code reusability by allowing a class to inherit some of its behaviour from a base class (“is-a” relationship)

• In Java, this is done by using the keyword extend
• Abstract classes can be extended. Their abstract methods must be implemented by the inheriting class, less the inheriting class is also abstract

Java only supports single inheritance

• In practice, this simplifies the language
  • the “Diamond Problem”
    • class D inherits from B and C
    • classes B and C inherit from class A
    • D inherits A twice?
• It’s very common in Java to derive an existing class and override behaviour
• All classes have Object as their ultimate base class (implicit)

Interfaces

An interface represents a set of methods that must be implemented by a class (a contract or blueprint). Somewhat similar to pure abstract classes/methods

• Cannot be instantiated
• Class implementing the interface must implement all methods in the interface
• Uses implements keyword

In Java,

• extend a class to derive functionality from it
• implement an interface when you want to enforce a specific API

BUILDING USER INTERFACES

• Swing components
• Creating a window
• Adding Swing components

Java UI Toolkits

1. AWT (1995)
   • “Heavyweight” with platform-specific widgets
   • AWT applications were limited to common-functionality that existed on all platforms
2. Swing (1997)
   • “Lightweight”, full widget implementation
   • Commonly used and deployed cross-platform
3. Standard Window Toolkit (SWT, ~2000)
4. Java FX (~2010)
   • Cleaner and richer than Swing
   • Intended for rich desktop+mobile applications
   • Still seeking market space

Building a Swing UI

1. Create a top-level application window using a Swing container
   • JFrame or JDialog
2. Add Swing components to this window
   • typically, you create a smaller container (like JPanel) and add components to the panel
     • this makes dynamic layouts easier
3. Register for events
   • add listeners, like keyboard presses and mouse moves/clicks
   • implement actual behaviour for event callbacks
4. Make components update and paint themselves based on events

Creating a Window

import javax.swing.\*;

public class BasicForm1 {
    public static void main(String[] args) {
        // create a window
        JFrame frame = new JFrame("Layout Demo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // create a panel and add components
        // all Swing components are types of JComponent
        JPanel panel = new JPanel();
        JButton b = new JButton("OK");
        panel.add(button);
        frame.add(panel);

        frame.setResizable(false);
        frame.setSize(200,200);

        frame.setVisible(true);
    }
}

Open a Window [L8_S36]

Add a Component [L8_S37]

CS349, 2017-05-26

BASIC GUI DRAWING

Local Coordinates

• Any modern OS manages multiple windows
• Base Window System manages
  • where the window is located
  • whether it is covered by another window, etc
  • enables drawing using local coordinate system for the window

Conceptual Drawing Models

1. Pixel
   • SetPixel(x,y,colour)
   • DrawImage(x,y,w,h,img)
2. Stroke
3. Region

…

DRAWING IN JAVA

• Overriding painComponent()
• Graphics object

Graphics and Painting

• Applications consist of a JFrame (window), containing one or more Swing components
• We often define a top-level canvas (container)
  • this can hold other components
    • text fields, buttons, scrollbars, etc
  • we can also draw directly on the canvas
• Each component has a paintComponent() method, which describes how it paints itself
  • You can override this method, and draw primitive objects using the java.awt.Graphics object (basically, the Graphics Context)
  • This is a common technique for defining drawables in Java
• see L9_S21,22 for some code

EVENTS

• User interface architectures need to be able to accept input from real-world devices, and map them to actions within a system
  • support the transformation of input into commands
  • we want a general, reusable architecture that supports multiple devices

Event-Driven Programming

Event-driven programming is a paradigm in which the flow of the program is determined by events such as user actions (mouse clicks, key presses), sensor outputs, or messages from other programs/threads.

Wikipedia

• An event is a message to notify an application that something happened
  • e.g key press, key release, mouse move, mouse click, focus gained, focus lost, timer done, etc.

Role of the BWS, WM

1. Collect event information
2. Put relevant information in a known structure
3. Order the events by time
4. Decide which application and window should ge the event
5. Deliver the event

Role of the Programmer

1. Indicate what events you are interested in to the BWS/WM, to ensure that events are delivered
2. Write code
   • register to receive events
   • receive and interpret those types of events
   • update program content based on event
   • redraw the display (provide feedback) to communicate to the user what had changed
3. In modern languages, the process of registering for events and handling events is simplified
   • Java: Listener model
   • C#: Delegate model
   • Javascript: Something else

Event Dispatch

Event Capture, processing, and dispatch

• The event dispatch stage includes
  • Event dispatch
    • getting events to the correct widget
  • Event handling
    • running code for an event
  • Notify view and windowing system
    • MVC, and view notification
• The Event loop is the primary mechanism for event dispatch within an application
  • the event loop can be managed by application (XLib) or the toolkit (JVM)
  • the event loop iterates through all events in the event queue, and pushes them in order to the appropriate application
  • the application needs to determine which component should process the event
  • widget are often the final target of events dispatched from the event loop
• Once delivered to a widget, it still needs to interpret what any of the input means in the proper context and react appropriately

Widget Layout

• In complex applications, widgets are often laid out in a hierarchy
  • We call this hierarchy an interactor tree
  • Container classes and low-level components are nested together
  • Dispatching an event to the correct widget (that can handle the event) means traversing this tree

Lightweight v. Heavyweight Widgets [L10_S17]

Heavyweight widgets

• Widget toolkit wraps native-OS widgets
• BWS/OS provides a hierarchical “windowing” system for all widgets across all applications, and treats a widget essentially as a window
• This allows the BWS to dispatch events to a specific widget (and not just the top-level window)
• nested X Windows, Java’s AWT, standard HTML form widgets, Windows MFC

Lightweight widgets

• The widget toolkit draws its own widgets and is responsible for mapping incoming events to widgets
• BWS/OS provides a top-level window only, and can only dispatch to the window (NOT the widget)
• Java Swing, JQuery UI, Windows WPF

Positional Dispatch

• Send input to the widget under the mouse cursor
• The front-most widget under the cursor should receive the event

Widgets can overlap, so how do we determine the appropriate target widget?

Bottom-up positional dispatch

• Event is first routed to leaf node widget in the interactor tree corresponding to location of mouse cursor
• Leaf node has first opportunity to act on that event
• The leaf node widget can either
  • process the event itself
  • pass the event to its parent (who can process it and/or send it to its parent)
    • Why would a widget pass an event to its parent?
    • e.g. a palette of colour swatches may implement the colours as buttons. But palette needs to track the currently selected colour. This is easier if the palette deals with the events, rather than the button

Top-down positional dispatch

• Event is routed to widget in the highest-level node in the interactor tree that contains the mouse cursor
  • can process the event itself
  • can pass it on to a child component
• Key idea is that the highest-level node has the first chance at acting on the event
  • can create policies enforced by the parent
    • e.g. stopping events if all children are disabled
  • supports relatively easy logging of events for later replay

Limitations

Positional dispatch can lead to odd behaviour

• Example, we normally send keystrokes to scrollbar if the mouse is over the scrollbar
  • What if the mouse-drag starts in a scrollbar, but moves outside of it as it drags? Do we continue sending the events to the scrollbar? To the adjacent widget instead?
  • What if the mouse-press event occurs over one button but the release is over another widget? Does each widget get one of the events?
• SOmetimes, position isn’t enough. Also need to keep track of focus

Focus Dispatch

…

Accelerator Key Dispatch

…

Toolkit Summary

• BWS and widgets cooperate to dispatch events
  • heavyweight
    • BWS has visibility into all widgets in the application
    • BWS can dispatch top-down or bottom-up
  • lightweight
    • BWS can dispatch top-down only
    • toolkit dispatches to the widget
      • in Java, the JVM manages the dispatch

Dispatch Summary

• Mouse-down events are almost always positional
  • dispatched to widget under cursor (top-down or bottom-up)
• Other mouse and keyboard events go to widget in focus
• Positional and focus dispatch work together

CS349, 2017-05-29

Event Handling

How to manage event-code binding

• Switch Statement Binding
• Inheritance Binding
• Event Interfaces & Listeners
• Delegate Binding

After dispatch to a widget, how do we bind an event to code?

Event-to-Code Binding

How do we design our GUI architecture to enable application logic to interpret events once they’ve arrived at the widget?

• Design Goals
  • Easy to understand (clear connection between each event and code that will execute)
  • Easy to implement (binding paradigm or API)
  • Easy to debug
  • Good performance

Event Loop and Switch Statement Binding (X11)

All application events are consumed in one event loop (not by the widgets themselves)

• Outer switch statement selects window and inner switch selects code to handle the event
• Used in Xlib, Apple System 7, and, until recently, Blender

WindowProc Binding (MS Windows)

• Each window registers a WindowProc function (Window Procedure) which is called each time an event is dispatched
• The WindowProc uses a switch statement to identify each event that it needs to handle
  • there are hundreds of standard events

Inheritance Binding

Java Event Handling

Java simplifies much of event handling

• Events are transmitted to onscreen objects without programming intervention
• The event loop is hidden and managed by the JVM
• To handle events, tell onscreen objects what you’re interested in and what to do when the event fires.

Inheritance Binding (Java 1.0, OSX)

Event is dispatched to an Object-Oriented Widget

• These widgets inherit from a base widget class with all event handling methods defined a priori
  • onMousePress, onMouseMove, onKeyPress, etc
• The widget overrides methods for events it wishes to handle
  • each method handles multiple related events

Inheritance Problems

1. Each widget handles its own events, or the widget container has to check what widget the event is meant for
2. Multiple event types are processed thru each event method
   • complex and error-prone
   • another switch statement
3. No filtering of events
   • performance issues (esp. with frequent events)
4. Does not scale well. How do we add new events?
   • e.g. penButtonPress, touchGesture
5. Muddies separation between GUI and application logic
   • event handling application code is in the inherited widget
   • Use inheritance for extending class functionality, not for binding events

Event Interfaces & Listeners

Rather than a subclass widget, define an interface for event handling

• Here, an interface refers to a set of functions or method signatures for handling specific types of events
  • e.g. in Java, can define an interface for handling mouse events
• Can then create a class that implements that interface by implementing methods for handling these mouse events
• Widget object implements event “listener” interfaces
  • e.g. MouseListener, MouseMotionListener, KeyListener, etc
• When event is dispatched to widget, the relevant listener method is called

Improvements

1. Each event type assigned to an event method
2. Events are filtered
   • only sent to object which implements interface
3. Easy to scale to new events

Problems

1. Each widget handles its own events, or widget container has to check what widget the event is meant for
2. Muddies separation between GUI and application logic
   • event handling application code is in inherited widget

Listener Object Binding

…

MouseListener Implementation [L10_S48]

...

Listener Adapter Pattern

• Many listener interfaces have only a single method
  • e.g. ActionListener only has actionPerformed()
• Other listener interfaces have several methods
  • Typically, only interested in a few of them, not all
  • This leads to lots of boilerplate code with no-op methods
• Each listener w/ multiple methods has an adapter class with no-op methods
  • Simply extend the adapter, overriding only the methods of interest

Delegate Binding

Interface architecture can be a bit heavyweight

• Can instead have something closer to a simple function callback
• Delegates in Microsoft’s .NET are like a C/C++ funciton pointer for methods. However, they are
  • Object-oriented
  • Completely type-checked
  • More secure
  • Support multicasting (able to point to more than one method)
• Using delegates is a way to broadcast and subscribe to events

Using Delegates

1. Declare a delegate using a method signature
2. Declare a delegate object
3. Instantiate the delegate with a method
4. Invoke the delegate

Multicasting

• Instantiate more than one method for a delegate object

  handler = MyMethod1 + MyMethod2;
  handler += MyMethod3;
  

• Invoke the delegate, calling all methods

  handler("Hello");
  

• Remove method from a delegate object

  handler -= MyMethod1;
  

• How about

  handler = MyMethod4;
  

Event Handling in Java [L10_S65]

…

CS349, 2017-05-31

ANIMATIONS

A simulation of movement created by displaying a series of pictures, or frames

• Animation: drawing frames at a consistent rate
• Goals
  • Move things around on the screen
  • Repaint 24-60 times per second
  • Make sure events are handled on a timely basis
  • Don’t use more CPU than necessary
  • Easily understood code

Cats Eyes X style

public void eventLoop() throws InterruptedException {
    while (true) {
        if (this.myEventQueue.hasEvents()) {
            this.handleEvent(this.myEventQueue.nextEvent());
        }
    }
    this.handleAnimation();
    this.paintComponent(this.getGraphics());
    Thread.sleep(1000/this.FPS);
}

Why do the eyes move slower than the mouse?

• There is one event per pixel moved. We update the frames 30 times per second, but there’s too many events to process!
  • solution could be to separate the event handling speed and the frame handling
    • let the thread sleep only when there are no events to process(?)

Screen Flicker During Drawing

• Suppose you are animating two balls on the display in a game.
• As the balls get closer, you notice that one seems to flicker.
  • If you paint balls sequentially, then you might clear a rectangle of the first ball’s position, paint the first ball in the new position, then clear rect for the second ball and paint the second ball.
  • Ball 1 has a bite taken out of it or maybe even vanishes until next update

Flickering: when an intermediate image is on the display

• Need to ensure that only complete images are drawn
• Solution
  • Create an off-screen image buffer
  • Draw to the buffer
  • Copy the buffer to the screen as quickly as possible (between refreshes)
• In X, this is a manual process
• In most other situations, it is done for you

Double Buffering [L11_S12]

Java Code: Double Buffering

• Modern toolkits often have double-buffering built-in
  • e.g. in Java Swing, it is built into the JComponent class (which is a base class for all/most drawable components, so they inherit this functionality)

public boolean isDoubleBuffered() public void setDoubleBuffered(boolean o)

• Double-buffering is enabled by default!
  • if set in top-level container, all subcomponents will be doubled buffered, regardless of individual settings

Java: Animation Using a Timer in Java

class ColouredX extends JComponent {
    ...
    private Point ballPos = new Point(100, 0);
    private final int FPS = 40;
    private Timer timer;

    public ColouredX() {
        this.addMouseListener(...);
        this.timer = new Timer(1000/FPS, new ActionListener() {
            @Override public void actionPerformed(ActionEvent e) {
                ballPos.y += 2; repaint();
            }
        });
        this.timer.start();
    }

    /* Paint ball in new location */
    public void paintComponent(Graphics g) {
        ...
        g2.setColor(Color.ORANGE);
        g2.fillOval(this.ballPos.x, this.ballPos.y, 30, 30);
    }

Note

• If you adjust your frames per second, be careful you may also be adjusting the number of updates for second.
  • If you start updating more frequently, your object will move faster, since you’re using less time to translate the same distance
• Assignment 2 involves improving animations

Model-View-Controller

Observations

• When one view changes, other(s) often need to change as well.
  • Ideally, we want a single representation of the underlying data, and multiple views of that data
• The user interface code probably changes more and faster than the underlying application
  • many recent changes in MS Office were to UI code
  • Excel’s underlying functions and data structures are probably very similar to Visicalc, the original spreadsheet
• How do we design software to support these observations?

Possible Design: Tight Coupling

Cell\[\]\[\] cells;
    \+ void setCell(...)
    \+ Object getCell(...)
    \- void paintGraph(...)
    \- void paintTable(...)
    \- void paint(...)

• Issues with bundling everything together
  • What if we want to display data from a different type of source?
    • e.g. Database
  • What if we want to add new ways to view the data?
• Primary problem
  • Tight coupling of data and presentation prevents easy modification and extension

CS349, 2017-06-02

Observer Design Pattern

MVC is an instance of the Observer design pattern

• Provides a well-defined mechanism that allows objects to communicate without knowing each other’s specific types
  • promotes loose coupling
• Related to
  • “publish-subscribe” pattern
  • listeners
  • delegates in C#

…

CS349, 2017-06-05

Widgets

A generic name for parts of an interface that have their own behaviour

• e.g. buttons, progress bars, sliders, etc
• Widgets are also called components or controls
  • they control their own appearance
  • they receive and interpret their own events
• Are often put into libraries (toolkits) or reuse
  • Software bundled with a window manager, operating system, development language, hardware platform
  • The toolkit defines a set of GUI components for programmers
    • Programmers access these GUI components via an API

Heavyweight

…

Lightweight

…

Widget Toolkit Design Goals

1. Complete
   • Complete set of widgets and functionality
   • Goal: GUI designers have everything they need
2. Consistent
   • User: Look and Feel is consistent across components
   • Developer: Consistent usage paradigms
3. Customizable
   • Developer can reasonably extend functionality to meet particular needs of application

Meeting these requirements encourages reuse

Completeness

The Macintosh 7 had a button, slider, pull-down menu, checkbox, radio button, text entry fields, and a file I/O widget.

• Java Swing has many, many more.
  • SwingSet Demo
    • shows lots of different widgets with lots of variations
    • can easily view source code
      • to run, download examples, and run $ ant SwingSet2

Consistency

Facilitate learning by

• Using a common look and feel
  • Look: consistent visual appearance
  • Feel: consistent and expected behaviour
• Using widgets appropriately

Consistency helps users anticipate how the interface will react, and promotes easier discoverability of features

• For example, users familiar with Windows Vista will/can recognize features of the Vista platform.
• This is not very transferable to Java Swing, because Swing isn’t very recognizable in general.
• Moreover, people expect widgets to behave in certain ways
  • When we want to “Confirm” authentication, for example, we expect to left-click an Ok or Agree button, not right-click some obscure widget.
    • User should not guess

Customizable

How do we customize widget behaviour and appearance?

1. Properties
   • e.g. change colour, font, orientation, text formatter, …
2. Factor our behaviour (Pluggable behaviour)
   • Responding to an action: ActionListener
   • Swing’s UIManager for changing look and feel
   • JTable example

More on customizability later

Widgets as Input Devices

…

CS349, 2017-06-07

LAYOUTS

Two-Inteface Layout Tasks

1. Designing a spatial layout of widgets in a container
2. Adjusting the spatial layout when container is resized
   • Both can be done by hand (ie. graphic design)
   • or automatically (ie. with algorithms)

Spatial layout is one component of visual design

• It should use/maintain Gestalt principles
• It should use/maintain grouping, hierarchy, relationships, balance to achieve organization and structure

Dynamic Layout

• If a window is resized, we want to maximum use of available space for displaying widgets
• Hoeever, we want to do this such that the window maintains consistency with spatial layout
  • and preserves visual quality of spatial layout
• Need to dynamically modify the layout
  • reallocate space for widgets
  • adjust location and size of widgets
  • perhaps even change visibility, look, and/or feel of widgets

Moreover, widgets should be flexible to adjust for different screen sizes

Layout Managers

• A layout manager provies a layout algorithm to size and position its children widgets
  • Swing’s package provides a number of them
    • Grid, Box, Border, Flow, GridBag, etc…
• A widget can set the most appropriate layout strategy
  • container.setLayout(new GridLayout(2,3))
• Layout Managers are most useful for container widgets like JPanel or JScrollPane

BorderLayout

• Places components in up to five areas
  • top, bottom, left, right, center

BoxLayout

• Puts components in a single row or column

CardLayout

• Lets you implement an area that contains different components at different times

FlowLayout

• Simply layous out components in a single row, starting a new row if its container is not sufficiently wide

GridBagLayout

• Flexible layout manager
• Aligns components by placing them within a grid of cells
  • Allows components to span more than one cell

GridLayout

• Simply makes components equal in size and displays them in the requested number of rows and columns

GroupLayout

• Developed for use by GUI builder tools, but can be used manually
• Works with the horizontal and vertical layouts separately
• Layout is defined for each dimension independently

SpringLayout

• Flexible layout manager designed for use by GUI builders
• Lets you specify precise relationships between the edgers of components under its control
  • Struts
    • static in size
    • Struts between edges will remain the same when the screen size is changed
  • Springs
    • adjustable in size
    • Springs allow distances to change/adjust to screen size changes

CustomLayout

Can implement own layout manager…

Layout Design Patterns

Composite Pattern [L14_S13]

• Specifies that a group of objects are to be treated in the same way as a single instance of an object
• The intent of a composite is to “compose” objects into tree structures to represent part-whole hierarchies.
  • implementing the composite pattern allows clients to treat individual objects and compositions uniformly

Strategy Design Pattern [L14_S15]

• Factors out an algorithm into separate objects, allowing a client to dynamically switch algorithms
  • eg. Java Comparator “strategy” for a collection “context”
  • eg. Switching a game’s move selection algorithm from “easy” to “hard”
  • eg. Text formatter for textboxes

FixedLayout

• Widgets have a fixed size and fixed position
• In Java, achieved by setting LayoutManager to null
• Where/when is this practical?
  • …
• How can it break down even when windows aren’t resized?
  • Adding new elements means updating the other elements, which were placed manually
  • Changing locales for text may cause the given widget size(s) to be too small

Intrinsic Size Layout [L14_S19]

• A bottom-up approach where top-level widget’s size is completely dependent on its contained widgets
  • A bit of a stronger variant to width:auto; height:auto;
• Single pass algorithm
  • query each child widget for its preferred size
  • adjust the parent widget to perfectly contain each item
• BoxLayout and FlowLayout use this strategy

Variable Instrinsic Size Layout [L14_S20]

…

Struts and Springs Layout [L14_S21]

Tips and Strategies

• Break up UI recursively with panels that contain panels
• Cluster components into panels based on layout needs
• Provide a layout manager for each panel
• Consider making each panel into a view (see MVC lecture…)
  • reduces coupling between parts of program

Custom Layout Managers

• Sometimes, we want a more specific, non-standard layout that cannot be achieved by the default layout managers

public interface LayoutManager {
    void addLayoutComponent(String name, Component comp);
    void removeLayoutComponent(...)
    ... 
}

• We can build our own layout to achieve our desired effects

XML

• Many programming languages use XML to create UIs (Android esp.)
  • enables better separation of the appearance and application code
  • UI descriptions are external to your application code, which means that you can modify or adapt it without having to modify your source doe and recompile
  • declaring the layout in XML makes it easier to visualize the structure of your UI, so it’s easier to debug problems
• Potential issues
  • Android context needs to be considered (config doesn’t change(?))
  • Many XML-based layouts use absolute positioning, relative positioning, etc.
  • A lot of burder on programmer to maintain

CS349, 2017-06-14

AFFINE TRANSFORMATIONS

We can think of widgets as shape models

• Consists of an array of points {P1, P2, ..., Pn}
• Has properties describing how to draw it
• eg. Button
  • Points (0,0), (10,0), (5,0), (10,5)
  • Properties
    • text=OK
    • border_width=1
    • border_colour=blue

The Interactor Tree

Describes the hierachy of widgets

• Widget location is always specified in terms of parent’s coordinate system (ie. relative/local coordinates)
  • need to do some math before painting
  • performing hit test requires taking parent location into consideration

We will use affine transformations with an interactor tree to…

• Manipulate and transform widgets (shape models)
• Tell widgets how to draw themselves on-screen, relative to their parent
• Determine if a mouse-click intersects one of these widgets in the interactor tree

How to create multiple instances of a shape?

• Rotation + Scaling + Translation

Translate

Add a scalar to each of the components (each point of the shape)

x' = x + t(x)
y' = y + t(y)

Uniform Scaling

Multiply each component (each point) by the same scalar

x' = x * s
y' = y * s

Non-uniform Scaling

Multiple each component (each point) by a different scalar

x' = x * s(x)
y' = y * s(y)

Rotation

Each component is some function of x, y, THETA

x' = f(x,y,THETA) = xcos(THETA) - ysin(THETA)
y' = f(x,y,THETA) = xsin(THETA) + ycos(THETA)

Benefits

• Allows reuse of objects in scenes
  • Can create multiple instances by translating model of object and re-rendering
• Allows specification of object in its own coordinate system
  • Don’t need to define object in terms of its screen location or orientation
• Simplifies remapping of models after a change
  • eg. Animation

Examples

Combining Transformations [L16_S11]

We want to paint the house 2x its size, up the 30 degree slanted hill

• Strategy
  • scale
    • x=2x; y=2y;
  • rotate
    • x=2(xcos(30) - ysin(30)); y=2(xsin(30) + ycos(30));
  • translate
    • x=...+8; y=...+4;
• If we rotated after translation, our rotation would move the house as well as rotate it, which is not what we want

Combining Transformations [L16_S16]

• Strategy
  • Need to rotate bubble (45 degrees) about its center
    • need to translate in a way that the center of the shape is at the origin
    • translate after
  • Need to scale the size of person
    • 2X
  • Need to translate person
    • 40px, 0px
  • Need to translate bubble
    • 60px, 30px

MATRIX REPRESENTATION

Linear Algebra

• (s) Scalar
  • a single value (usually a real number)
• (v) Vector
  • A representation of an ordered list of numbers
  • Matrix
    • a vector arranged in rows and columns
  • Row/Column vector
    • a matrix with just one dimension
• (P) Point
  • A fixed location in spcae (represents a position)

Legal Operations

• vector + vector: v1 + v2 = v3
• vector multiplied by scalar: v1 x s1 = v4
• point minus point = P1 - P2 = v5
• point + vector: P2 + v5 = P1
• 2 ways to “multiply” vector by vector
  • dot product: v1 * v2 = s2
  • cross product: v1 * v2 = v6

Goal

Represent each 2D transformation with a matrix

• This is a succinct way of expressing a single transformation that can be used to transform all of the points in our shape model

| a b |
| c d |

Multiply matrix by a column vector => apply transformation to a point

x' = ax + by
y' = cx + dy

| x' | = | a b || x |
| y' |   | c d || y |

Matrix notation also supports combining transformations by multiplication

• ie. transformations are associative
• We can multiply transformation matrices together
  • This single matrix can then be used to transform many points
  • Can be sent to a GPU to speed up the process

Improvements

…

Examination

• Will need to be comfortable with matrix multiplication
  • given a series of transformation matricies, what is the final transformation matrix?
  • given a final transformation matrix, what were the operations?

Notes

• Matrices are associative
  • A(BC) = (AB)C
• Matrices are not commutative
  • AB != BC

CS349, 2017-06-16

Affine Transformations in Java

Useful Graphics2D Methods

• AffineTransform getTransform(), void setTransform(AffineTransform Tx)
  • returns/sets a copy of the current Transform in the Graphics2D context
• void rotate(double theta), void rotate(double theta, double x, double y)
  • concatenates the current Graphics@D transformation with a rotation transform
• void scale(double sx, double sy)
• void translate(double tx, double ty)

AffineTransform handles all matrix manipulations

• A bit more control than Graphics2D

Static Methods

• static AffineTransform getRotateInstance(double theta)
• static AffineTransform getRotateInstance(double theta, double anchorx, double anchory)
• static AffineTransform getScaleInstance(double sx, double sy)
• static AffineTransform getTranslateInstance(double tx, double ty)

Concatenation Methods

• void rotate(double theta), void rotate(double theta, double anchorx, double anchory)
• void scale(…)
• void translate(…)
• void concatenate(AffineTransform Tx)

Other Methods

• AffineTransform createInvers()
• void transform(Point2D[] ptSrc, int srcOff, …)

Slides worth noting

• L17_S42; RotateTriangle.java
• …

Scene Graphs

• A mechanism for drawing a series of connected components
  • each part has a transform matrix
  • each part draws its children relative to itself
    • (torso)
      • head
      • right upper arm
        • right lower arm
          • right hand
      • left upper arm
        • …
      • right upper leg
        • …
      • left upper leg
        • …
• An interactor tree is a type of scene graph
• Each component has an affine transformation matrix, and a paint routine
  • Matrix describes the components location relative to its parent
    • ie. what translations should be performed on it
    • The pain routine concatenates the parents affine transformation matrix with the components matrix and then paints using the resulting matrix
    • eg. M1: translate (10,10)
      • M2: translate (5,5)
        • this (5,5) is relative to M1
        • and, supposedly, M1 is relative to its parent as well

As we navigate the interactor tree, we combine successive matrices to reflect the way each component is positioned relative to its parent.

Each component should…

1. paint itself
   • using its affine transformation matrix
2. for each of its children
   • save current affine transformation
   • calculate a new transform matrix using the current (parent) transform matrix and the location of the child
     • eg. curr * child_translation_transformation
   • tell child to paint themselves using their new affine transform matrix
   • return the original affine transformation matrix

Inside Tests

We also need to transform any coordinates in events as the events are passed down the interactor tree

• This allows us to translate between global and local (or relative) coordinate systems

For example, a mouse event in the window’s coordinates will need its coordinates translated to a child component’s local (relative) location prior to passing it down

• Affine transformations can be used for this, as well

Mouse and shape model must use the same coordinate system. Either

• Transform mouse to model coordinates
  • suppose we zoomed in… our model coordinates are still the same, but when we click, the window coordinates are no longer in a 1:1 scale with the model’s coordinates
    • if we click (2,2), it may be within a triangle in 2X zoom, but not in 1X zoom
    • to verify if the triangle was actually clicked… need to compare with original coordinates of the triangle
      • if we scale the triangle by 2X (to zoom), we need to 1/2 the mouse coordinates…
      • we need to apply the inverse transformation to the mouse coordinates
• or Transform model to mouse coordinates
  • alternatively, we can transform the triangle’s coordinates (by a scale, perhaps), and check if the mouse click falls within it…

CS341, 2017-06-19

Undo/Redo

Direct Manipulation Principles

Recall

User should be able to explore without (severe) consequences

• Reversibility of (almost) all actions helps achieve this

Benefits of Undo

• Undo lets you recover from errors
  • Input errors (human) and interpretation errors (computer)
  • Allows the user to work quickly (without fear)
    • small mistakes can be undone
• Undo enables exploratory learning
  • Users mainly learn by trying manipulations of visual objects rather than by reading extensive manuals
  • try things you don’t know the consequence of
  • try alternative solutions
  • removes fear and commitment to decisions
• Undo lets you evaluate modifications
  • fast do-undo-redo cycle to evaluate last change to document (and see the changes visually)

Checkpointing

• A manual undo method
  • you can save the current state so you can rollback later
  • eg. a video game
  • eg. source code version control

Undo Design Choices

• In any undo-redo implementation, we need to consider the following design choices
  • Undoable actions
    • What can’t be/isn’t undone
    • Not all actions need to be (manually) undo-able
      • eg. if you move a character to the right, you don’t “undo” it, you just move back to the left
  • UI State Restoration
    • What part of the UI is restored after undo?
  • Granularity
    • How much should be undone at a time?
  • Scope
    • Is undo/redo global in scope, local, or someplace in between?
    • eg. if several documents are open, undos should be limited to the focused document
• No single answer, but we have guidelines (above)

Undoable Actions

• Some actions may be omitted from undo
  • eg. change to selection (just reselect another)
  • eg. window resizing
  • eg. scrollbar positioning
• Some actions are destructive and not easily undone
  • eg. quitting a program with unsaved data or emptying trash
• Some actions cannot be undone
  • eg. printing a document

Suggestions

• All changes to document (ie. the model) should be undoable
• Changes to the view, or the document’s interface state, should only be undoable if they are extremely tedious or require significant effort
• Ask for confirmation before performing a destructive action which cannot easily be undone
  • eg. confirm when emptying trash

UI State After Undo

• What is the user interface state after an undo or redo?
  • eg. highlight text, delete, undo
    • is the text highlighted?
  • eg. select file icon, delete, undo
    • is file icon highlighted?

Suggestions

• User interface state should be meaningful after undo/redo action is performed
  • change selection to object(s) changed as a result of undo/redo
  • scroll to show selection, if necessary
  • give focus to the control that is hosting the changed state
• Why? These provide additional undo feedback
  • Show the user something happened

Granularity

• What defines one undoable “chunk”?
  • chunk is the conceptual change from one document state to another state

Examples

• MS Word
  • string delimited by any other command
    • bold, mouse click, autocorrect, etc…
• Sublime
  • token delimited by whitespace
    • a chunk is the entire whitespace-delimited word. When we undo, we remove the chunk, not each individual character

Example: Draw a Line

• MouseDown to start line
• MouseDrag to define line path
• MouseUp to end line
• MouseDown + MouseDrag + MouseUp = 1 conceptual chunk to “draw line”
  • “undo” should probably undo the entire line, not just a small delta in the mouse position during MouseDrags

Suggestions

• Ignore intermediate states when under continuous interactive control
  • eg. resizing or moving an object
    • ignore the individual pixels during the drag
• Chunk all changes resulting from an interface event
  • eg. find and replace all
    • undo will have to undo the entire thing, not just one instance of the word changed
• Delimit based on discrete input breaks
  • eg. words or sentences in text
  • eg. pauses in typing

Scope

• Is undo/redo global, local, or someplace in between?
• …

Implementation

Forward v. Reverse Undo

1. Forward Undo
   • save coplete baseline document state at some past point
   • save change records to transform baseline document into current document state
   • to undo last action, apply all the change records except the last one to the baseline document
2. Reverse Undo
   • save complete current document state
   • save reverse change records to return to previous state
   • to undo last action, apply last reverse change record

Implementation

Both these options require “change records.” We have multiple ways of implementing these as well

1. Memento pattern
   • save snapshots of each document state
   • could be complete state or difference from “last” state
   • forward or reverse both just load a new document
2. Command pattern
   • …

Undo Command Pattern

…

Java Undo

javax.swing.undo.*

• UndoManager keeps track of undo/redo command stacks
• UndoableEdit interface is the command to execute (redo) or un-execute (undo)
• Usually put UndoManager in Model for document context

import javax.swing.undo.*;
public class Model extends Observable {
    private int value = 0;
    private UndoManager undoManager;
    ...

    public void setValue(int v) {
        // create undoable edit
        UndoableEdit ue = new AbstractUndoableEdit() {
            final int old = value;
            final int new = v;
            
            public void redo() {
                value = newValue;
                notifyObservers();
            }

            public void undo() {
                value = oldValue;
                notifyObservers();
            }
        }

        this.undoManager.addEdit(ue); // add edit to manager
        this.value = v;
        notifyObservers();
    }
}

Triggering Undo or Redo

• Usually done with “undo” and “redo” menu items
  • with key Accelerators for CTRL-Z, CTRL-Y mapping

public void undo() {
    if (undoManager.canUndo())
        undoManager.undo();
}

public void redo() {
    if (undoManager.canRedo())
        undoManager.redo();
}

UndoDemo

• Model handles all undo actions
  • UndoManager resides in Model
  • setter save UndoableEdits (uses closure)
  • methods added for undo state: canRedo, canUndo
  • …

…

CS349, 2017-06-21

Cut, Paste, Drag-and-Drop

…

CS350, 2017-05-02

INTRODUCTION

What is an OS?

• Nowadays, we think about our phone (iOS, Android), Windows laptops, Mac OS, Linux Unity, …
• Operating systems these days (mostly) have GUIs, are crisp & clean
• Operating system ==> User experience
  • desktop environment
  • shell
  • interaction
  • not what is happening underneath (today, at least)

An operating system is more than the Desktop or Shell Three views

• Applcation view
  • What services does the OS provide?
• System View
  • What problems does the OS solve?
• Implementation View
  • How is the OS build? (our focus)

I. Application View

The OS provides an execution environment for running programs

• The execution environment provides a program with the processor time and memory space that it needs to run.
  • creates the environment in which the program will run. Sets the PC counter to start running it
• The execution environment provides interfaces through which a program can use networks, storage, I/O devices, and other system hardware components.
  • Interfaces provide a simplified, abstract view of hardware to application programs
• The execution environment isolates running programs from one another and prevents undesireable interactions among them

Operating Systems were simpler back then… for the simple reason that there wasn’t much to do back then. The user would play one game at a time.

• These days, Chrome itself probably has 14 tabs…
• NES cartridges were self-bootable. The game didn’t need an operating system to run

Drawbacks: consider the Atari 2600

• No operating system, hence no APIs for the device
  • this means every game needed to handle the sound, controls, etc. They needed to build the drivers themselves whenever they wanted to build a game
    • this is probably why it didn’t have many games. Or, games didn’t work properly

II. System View

The OS manages the hardware resources of a computer system

• Resources include processors, memory, disks and other storage devices, network interfaces, I/O devices like keyboards, etc …
• CPU power and memory are limited, but must be distributed/allocated among running programs. The OS controls the sharing of resources.
  • makes sure no program takes more than it should
• The OS iteself uses resources, which it must share with application programs

III. Implementation View of an OS

The OS is a concurrent, real-time program

• Concurrency arises naturally in an OS when it supports concurrent applications, and because it must interact directly with the hardware
• Hardware interactions also impose timing constraints
  • OS needs some kind of library to share these resources
    • a printer, for example, can only print one item at a time. We need some software means to ensure current jobs aren’t interrupted

What an OS does…

• Virtualizes and abstracts resources
  • don’t want the program to interact with the graphics card directly. As such, the operating system needs an interface to allow interation (abstracted)
    • don’t want to set the frames and update displays yourself. The OS provides functions in the form of draw(..) to abstract this
• Creates execution environments for applications
• Provides persistence: manages data that exists after shutdown

The OS and the Kernel…

• used to be called the Master Control Proram (MCP)
• kernel
  • the operating system kernel is the part that responds to system calls, interrupts, and exceptions
• operating system
  • includes the kernel, and may include other related programs that provide services for applications
    • utility programs (like scans)
    • command interpreters (like shells)
    • programming libraries (like C libraries, drivers, APIs)
  • started out as just I/O libraries. These were common, and made sense to make them reuseable.
  • then came batch scripts
  • …
  • multi-programming: the CPU was idle when memory operations took a while. Naturally, it made sense to figure out how to use the CPU during this downtime.
  • eventually, concurrency, etc …

OS Abstractions

The execution environment provided by the OS inclues a variety of abstract entities that can be manipulated by a running program.

• files and file systems
  • abstract view of secondary storage
• address spaces
  • abstract view of primary memory. Extension: virtual memory
• processes and threads
  • abstract view of program execution
• sockets and pipes
  • abstract view of network or other message channels. The user doesn’t have to worry about passing bytes and some such.

Course Topics

1. Introduction
2. Threads & Concurrency
3. Synchronization
   • protect data that is being used by different threads
4. Processes and the Kernel
5. Virtual memory
6. Scheduling
   • make sure programs are distributed the necessary resources in an optimal way
7. Devices and Device Management
   • harddrives, SSDs, etc
8. File systems
9. Interprocess Communication and Networking

Notes for future reference

Try not to use printf(…). GDB

CS350, 2017-05-04

THREADS AND CONCURRENCY

Threads provide a way for programmers to express concurrency in a program

Note:

• Scheduling can encounter different delays, so don’t expect threads to go in any particular order
• printf forces threads to run in a particular order, thus hiding different problems that can occur in scheduling

OS/161 Threaded Concurrency Examples

• A thread can create new threads using thread_fork
• New threads start execution in a function specified as a parameter to thread_fork
• The original thread which called thread_fork and the new thread proceed concurrently, as two simultaneous sequential threads of execution
• All threads share access to the program’s global variables and heap
  • Threads can communicate with each other throw global variables/flags. This lets you control the flow by halting a certain thread until a flag is set to true
  • Threads do not share stacks (more info later)
• Each thread’s function activations are private to that thread

Prototype for thread_fork

int thread_fork(
    const char *name, // name of new thread, used for debugging
    struct proc *proc, // NULL for now to make this thread part of the existing program
    void (* func) // entry point: new thread's function
        (void *, unsigned long),
    void *data1, // function's first param
    unsigned long data2 // function's second param
);

• See kern/include/thread.h
• terminate the calling thread using void thread_exit(void);
  • not relevant for OS/161, but other libraries’ thread_exit returns a status code to the parent. Can just return
• voluntarily yield exectuion using void thread_yield(void);
  • thread_yield enabled co-operative concurrency. Programs that didn’t call thread_yield didn’t have concurrency, because only that thread would be running

Why Threads?

1. Parallelism exposed by threads enables parallel execution if the underlying hardware supports it
   • programs can run faster
2. Parallelism exposed by threads enables better processor utilization
   • if one thread has to block, another may be able to run

The Stack

When using multiple threads, need to pay attention to the stack frame of each operation

If I have multiple threads in the same program, they’re going to share an address space. They don’t get their own copy of the data. Their stack, however, is going to be unique

• the local variable values for each thread is particular to that thread
  • we can’t do this without unique stacks
  • Question: why not just use the entire stack for every thread?
    • how to keep track with each thread’s specific frames?
    • The idea of a stack is to be able to push and pop without having to worry about order. If all the threads’ frames are interleaved, we can’t do that.
• conceptually, each thread executes sequentially using its private register contents and stack
• Each thread also keeps its own copy of the program counter
• Each thread has its own stack pointer (for obvious reasons)
• When we start running a new thread, we need to save the old thread’s state(s)

Debugging OS/161

Need to connect OS/161 to compiler. NEED 2 CONNECTION INSTANCES TO SEE THE DEBUG

• sys161 -w
  • -w : wait for a connection with debugger before proceeding
  • The debugger connection will be init’d in another terminal instance
• cs350-gdb kernel-ASST0
  • initialize debugger connection using assignment 0
  • dir ../os161-1.99/kern/compile/ASST0 into (gdb)
• need to set some breakpoints first
• note: see stack: enter bt into (gdb). This will show the backtrace
• note: see values of variables at a breakpoint: enter print curthread into (gdb) to show the value of curthread. It may initially show the pointer address of curthread, but you can use pointer arithmetic to get the actual value. Example: print *curthread

CS350, 2017-05-09

Some History

EXEC I 1962 - UNIVAC 1107

• A batch processor with multiprogramming
  • Automatically loads the next job upon completion of another
  • Do not wait (i.e. let CPU idle) for I/O to complete. Save A’s state, start running B’s I/O
  • 288 KB of memory

Implementing Concurrent Threads

Options

1. Multiple processors, multiple cores, hardware multithreading per core
   • P processors, C cores per processor, M multithreading degree(s) per core
     • ==> P*C*M threads can execute simultaneously
   • From an operating systems perspective, option 1 is boring.
2. Timesharing
   • Multiple threads take turns on the same hardware
   • Rapidly switch from thread to thread so that all can make progress

In practice, both techniques can be/are combined

Notes

• Threads don’t always terminate.
  • e.g. repeating a movie over and over will cause these threads to keep running. Theoretically this will hijack your processing power
  • Through timesharing, other threads can have an opportunity to run

Timesharing and Context Switches

When timesharing, the switch from one thread to another is called a context switch What happens during a context switch?

• Decide which thread will run next (scheduling)
• Save register contents of current thread
• Load register contents of next thread

Thread context must be saved/restored carefully, since thread execution continuously changes the context

• Sometimes, threads have higher priority. Naturally, there should be some way to determine which thread(s) require more processing time.
  • OS/161 is round robin (no priority)

Context Switch on the MIPS

Saving registers of old thread

/* See kern/arch/mips/thread/switch.S */

switchframe_switch:
    ; a0: address of switchframe pointer of old thread
    ; a1: address of switchframe pointer of new thread

    ; Allocate stack spac efor saving 10 registers
    addi sp, sp, -40
    sw ra, 36(sp)
    sw gp, 32(sp)
    sw s8, 28(sp)
    sw s6, 00(sp)
    sw s5, 00(sp)
    sw s4, 00(sp)
    sw s3, 00(sp)
    sw s2, 00(sp)
    sw s1, 00(sp)
    sw s0, 00(sp) ; these are the callee-save registers

Loading registers of new thread

; Let the new stack pointer from the new thread

lw sp, 0(a1)
nop ; delay slot for load

; Now, restore registers
lw ...
lw ...
.
.
.
nop ; delay slot for load

j ra ; return. There is a delay slot after jumps
addi sp, sp, 40 ; in delay slot
.end swithframe_switch

What Causes Context Switches?

1. running thread calls thread_yield
   • the current thread is voluntarily giving up the CPU and letting another thread go
2. running thread calls thread_exit
   • the current thread is gone and deleted from the system. Thus, need a new thread to run
3. running thread blocks, via a call to wchan_sleep
   • more on this later …
   • e.g. hardware like printers require an innate delay/sleep between print processes. If a thread goes to sleep while waiting for resources, we can switch to another thread to run
4. running thread is preempted
   • the current thread involuntarily stop running

…

Preemption

• WIthout preemption, a running thread could potentially run forever, without yielding/blocking/exiting
  • the OS can’t just stop it for no reason
  • This is done using hardware interrupts (like key-presses)
• Preemption means forcing a running thread to stop running, so that another thread can have a chance
• When an interrupt occurs, the hardware automatically transfers control to a fixed location in memory
  • When an interrupt is received, the CPU keeps the address of a trap frame. The CPU will immediately execute the code at the trap frame. This code will save the context of the thread that is to be interrupted
  • Since we’re interrupting, the thread could have been executing anything. Thus, we have to save everything (not just callee-save registers).
    • e.g. registers like hi or lo
• At that memory location, the thread library places a procedure called an interrupt handler
• The interrupt handler normally:
  1. create a trap frame to record thread context at the time of the interrupt
  2. determines which device caused the interrupt and performs device-specific processing
  3. …
  4. Interprets how long the thread had been operating. If this time exceeds the quantum, the OS will call thread_yield and force a context switch

OS/161 Thread Stack After an Intercept [19]

1. Add a trap frame
2. Interrupt handling

Preemptive Scheduling

• A preemptive scheduler imposes a limit, called the scheduling quantum on how long a thread can run before being preempted
  • If the thread exits or finishes before this time limit, everything is good
  • Every x units of time, the CPU fires an interrupt. This is a shorter cycle than the quantum.
    • This is how the CPU keeps track of how long threads have been running. This is also how the CPU determines a thread is complete
  • Suppose a thread exits 2ms into a 20ms cycle. We need to select a new thread, which will run for 38ms.
• The quantum is an upper bound on the amount of time that a thread can run. It may block or yield before its quantum has expired
• Periodic timer interrupts allow running time to be tracked.
• If a thread has run too long, the timer interrupt handler preempts the thread by calling thread_yield
• The preempted thread changes state from running to ready, and is placed on the ready queue

OS/161 Thread Stack After Preemption

• The thread is running happily. Then, there is an interrupt. So, we immediately call the trap frame.
• Then, we let the interrupt handler (some specific handler depending on when/why the thread was interrupted) do its business.
• The thread is yielded, and then the CPU switches to a new thread.
• There needs to be a balance between the quantum and how much work is actually done in a thread. We don’t want to interrupt a thread so often that hardly any work gets done.
  • This will be especially bad if the interrupt handling and thread switching does more work than the thread itself.

CS350, 2017-05-11

Prof Email: lanortha@uwaterloo.ca

twothreads problem

• Suppose there are two threads in a system
• Round robin scheduling
• Scheduling quantum: Q ms
• Single processor

for i from 1 to N do
    compute for C ms
    sleep for S ms
end

Note: To solve these thread problems, try to envision the flow.

1. First, assume that C < S and C < Q. Suppose both threads start at time t=0. At what time will both threads be finished?
   • Draw the cycle

      XXXYYYY|XXXYYYY| ... |XXXYYYY|
      XXXY|YYYXXXY| ... |   XXXY|YYY
     

     • Here, we have (C+S)N + S, with S extra ms at the end
2. Second, assume that S < C < quantum
   • Again, the quantum has no effect

      XXXXXX|YYYZZZ|XXXXXX|YYYZZZ| ... |YYY   |
         |XXXXXX|YYYZZZ|XXXXXX| ... |XXXXXX|YYY
     

   • X = computer, Y = sleep, Z = extra wait
     • Here, we have 2NC + S

Two-Thread Example (P1) [slide 27]

…

Synchronization

Key concepts

Critical sections, mutual exclusion, test-and-set, spinlocks, blocking and blocking locks, semaphores, condition variables, deadlocks

We use multi-threading to actually have threads work together to achieve some goal. Since all threads share the address space and global data (everything but the stack), we need to make sure these threads don’t fuck up the shared varialbes by using it at the wrong time.

• Suppose int x = 0;
  • How do we have multiple threads reading and writing the same variable at the same time? What will happen?
    • What if thread2 uses x while it is in the middle of being changed?
    • How can we know thread2 is using the right x value?
• If one thread calls add() on a x and another calls sub() on x at the same time, we couldn’t possily know what the result will be.
• To analyze this, we need to understand what operations like x++ and x-- actually do
  • In MIPS, when we do x++, we have at least 3 operations. Load the value. Update it. Save the value
    • This can be interrupted at any point by another thread using x
• Critical Section Examples [slides 5,6,7]
  • We have no control over where, exactly, thread1’s MIPs operation is interrupted.
  • We know our context switches saves the register values without problem.
  • Sometimes, thread2’s operations are pointless because thread1 hadn’t had a chance to save its computed value yet
  • Note that no two operations can use the same address at the same time. Inevitably, one thread’s operation will run before the other.

When the result depends on the exact order in which our methods are called, we have a race condition

• Not really what we want. When we do add() and sub() we know exactly what the result should be. However, we can’t ever be sure.

Solution Force certain sections of the code to execute in a particular order. By doing this, we avoid having multiple threads trying to read/write to the same variable at the same time.

Volatile

If a variable is volatile, the compiler will be forced to load and store the value on every use.

• Recall in assembly optimization, sometimes we take a shortcut and avoid calling lw and sw when we don’t really need to.
  • Sometimes we store commonly used variables in a register
  • Other times, we might realize that we call lw even though we did that from another operation

Another Critical Section Example [slide 9]

1. list *lp has one item
2. T1 and T2 call list_remove_front
3. Suppose T1 sees that lp is not empty. It reaches element=lp->first but doesn’t call it (yet).
4. We have a context switch to T2
5. T2 finishes list_remove_front. It sets num_in_list to 0, and sets list->first=NULL.
6. T1 starts running again. But now, list->front is NULL. Segmentation fault

• If two threads call list_remove_front, one of them should remove the front, and the other should not crash. It should just do nothing.
• This is not the only race condition (not even close)

More Critical Section Example [slide 10]

We are appending to the end of the list.

1. Suppose our list is empty
2. T1 and T2 call list_append
3. T1 sets element->item = new_item (== 1) and the assertion succeeds.
4. T1 checks is_empty(lp), which is true, but doesn’t run the condition block (yet)
5. T2 runs. It sets element-> = new_item (== 2)
6. T2 adds the new element and increments lp->num_in_list
7. T1 runs, again. However, it’s inside the is_empty(lp) block. After T2, lp is not empty.
8. T1 sets lp->first = element. This element was created by T1.
9. Problem: T2 created an element using malloc, but it was overwritten by T1.
   • This is a memory leak
   • Moreover, it’s like T2 didn’t do anything to the array

Note: when using dynamic array in assignments, pay attention to this

Mutual Exclusion

To prevent race conditions, we can enforce mutual exclusion on critical sections in the code

• One, and only one thread is in these critical section(s) at a time
  • example: only one person in a bathroom stall at a time. The stall is a critical section
    • If you’re the one that locked the bathroom stall door, you should be the only one that can unlock the door.
    • If someone else can unlock the door from the outside, we still have a race condition
• How do we have a locking door around our critical section?
  • Simplest version: a global variable lock=true. If it’s false, we can’t use the section
    • Before we use the critical section, we Acquire(&lock)
    • After, we Release(&lock)

Example

bool v, lock=false;

Acquire(bool *lock) {
    while(*lock) {}; // keep trying while someone else has the lock 
    // finally false, the door opens

    *lock=true;
}

• Does this work? No. Why? Look ahead to how we can fix it

CS350, 2017-05-16

cont’d from last class

We try to avoid race conditions. To do this, we need some sort of synchronization.

To protect critical sections, we use locks. Previously, we stated that C code doesn’t work for building Acquire.

• If lock is initially available, and two threads try to acquire it
  • T1 starts, reaches the while(*lock) line, and exits the loop
  • We have a context switch
  • T2 starts, and exits the while(*lock) loop. It sees *lock=true and finishes
  • T1 resumes, and sets *lock=true and enters the critical section
• Can we fix this with C code? Doesn’t look like it
• We need a hardware-level function. An atomic instruction that cannot be broken into smaller piece
  • Means we will not have an interupting between the test (loop) and set (=true) operations.
  • x86 has an instruction called xchg $src, addr
    • puts the src/value of $src into $addr
    • the old value of $addr will be put into $src

xchg(value, addr) {
    old = *addr;
    *addr = value;
    return old;
}

• xchg is, effectively, an atomic test and set. If the lock is not available (i.e. lock==false), it will set it to true and return false (and exit loop). If the lock is not available, xchg returns true and keeps spinning
  • see slide 18 to see in-line assembly in C
  • this course will not ask you to do it…

Acquire using xchg

Acquire(bool *lock) {
    while(xchg(true, lock));
}

SPARC

Side note, SPARC was the first 64-bit architecture. SPARC 64 SLFX has 34 cores and was released last year.

• 32 cores are for general purpose
• 2 of them are reserved for utility and the operating system
  • This means you can have a very responsive operating system
• Its atomic instruction is called cas

compareAndSwap(addr, expectedValue, newValue) {
    old = *addr;
    if (old == expectedValue) // has the value changed since I last checked?
        *addr = newValue;
    return old;
}

• suppose *addr=15, expectedValue=12, newValue=3
  • *addr != expectedValue, so no change and return 15
  • For our purpose, suppose expectedValue=false. This is the only case when we should change the lock

Acquire using cas

Acquire(bool *lock) {
    while(cas(lock, false, true));
}

Spinlocks in OS/161

In our lock implementation, we shouldn’t be accessing the assembly (for our assignment)

Spinlocks spin on the CPU until our desired state is reached and a lock can be acquired

• This seems like an obvious issue. spinlocks are using the CPU to do nothing important. There’s no workaround, they have to do this to achieve what they do. Still, we can improve it.
• OS/161 spinlocks are implemented already
  • see semaphore implementation
  • there is an init, acquire, and release function provided

Using Load-Linked / Store-Conditional [18]

MIPS does not have an atomic instruction. It uses two instructions to achieve what we want.

• x is the old value in the addr sd
• y=1 (want to set lock and acquire it, if possible)
• if (x == value in sd)
  • If values are the same, we will set *sd=y and then set y=success
  • Else, y=failure
• There are 3 outcomes for this code
  • Load-linked is going to get the old value of the lock.
  • If no code has changed the value of the lock, and the lock is true. Then x == value in sd, is true and we return success.
  • If no code has changed the value of the lock, and the lock is false, we’ll take the lock and return success.
    • Hence, we need to check if y==failure. If true, return 1 and tell the while loop to keep spinning
      • Something else is using the lock
    • If y=failure, we don’t return 0. The lock could be false and didn’t change!
      • Here, return x which is the value at the lock before we took it.
        • If the lock was true and we took it, we’ll return x=true=1.
        • If the lock was false, and we took it, we’ll return x=false=0 and we stop spinning
        • Double check this part

Ideally, if a lock is still spinning, we want it to sleep (not hog to CPU) A lock, in this case, is just called a lock.

• Inside of lock_acquire, if we are unsuccessful, the lock is blocked and goes to sleep
  • For various reasons, a thread might need to wait for something
    • Wait for a lock to be released by another thread
    • Wait for data from a slow(er) device
    • Wait for input from a keyboard
    • Wait for busy device to become idle (like a printer)
  • When writing computationally heavy code, and we don’t call yield, our CPU can begin to overheat.
    • It would help to send threads on vacation. The developer can put blocks in code to put threads to sleep to let the CPU cool down
  • When a thread blocks, it stops running.
    • The scheduler chooses a new thread to run
    • A context switch occurs: from the blocking thread to the new thread
    • The blocking thread is queued

Wait Channels in OS/161

We do not have a master “blocked queue”. All the threads that are sleeping are waiting for something different, as mentioned above.

We will create a wait channel for every single thing a thread could be waiting on. If we have a lock (resource), it will have a wait channel.

• Wait Channels are just queues. When we call sleep, we put the thread onto the queue.
  • wchan_sleep(..): currThread goes to sleep and puts it onto the wait channel specified
  • Thread goes to “blocked”
• We can wake one, or all of the threads
  • wchan_wakeone/all(..): currThread goes to ready and master queue(?)
• We also have wchan_lock(..)
  • prevents operations on wait channel wc
  • …

CS350, 2017-05-18

Running a lock test: `synchtest.c`

* $ sys161 kernel-ASST1 "sy2;q"
    - also `uw1`

SEMAPHORES

Consider a room. It has 73 seats (resources). Suppose students are threads. When they come in the room, they look for empty seats and sit down. If no available seat, then the thread must wait.

A semaphore helps keep track of which resources are available. Similar to a lock, but instead of a held/unheld, it keeps a counter of the # of resources available

• A semaphore is a synchronization primitive that can be used to enforce mutual exclusion requirements.
• Can be used to solve other kinds of synchronization problems
• A semaphore is an object that has an integer value, and that supports two operations
  • P: if the semaphore value > 0, decrement the value. Otherwise, wait until the value is greater than 0 and then decrement it
    • take a resource
    • “P the semaphore”: __p__assering: passing
    • if the semaphore value is 0, block(?)
  • V: increment the value of the semaphore
    • return a resource
      • “V the semaphore”: __v__rijigave: release
  • By definition, operations P and V are atomic
• Not necessarily about a critical section, but rather protecting a resource
  • Note, semaphores don’t care who returns a resource
• Binary semaphore
  • initial_value = 1, only one resource available
  • effectively a lock
    • except someone else can V the semaphore (no ownership)
• Counting semaphore
  • initial_value >= 0
  • can start at 0, waiting for another thread to release resources

Producer/Consumer Synchronization with Bounded Buffer

• Suppose we have threads (producers) that add items to a buffer and threads (consumers) that remove items from the buffer
  • Subaru production plant in Indianapolis (producer). Creates cars and puts it in the parking lot (the buffer)
  • What if the parking lot (buffer) is full?
  • What if a consumer all the way from Vancouver comes to Indianapolis to pick up cars?
• Suppose we want to ensure that consumers do not consume if the buffer is empty. Instead they must wait until the buffer has something in it
  • If the parking lot is empty, don’t send a truck from Vancouver to pick up items from the buffer
• Similarly, suppose the buffer has a finite capacity (N), and we need to ensure that producers must wait if the buffer is full
  • Subaru plant should not build more cars if their parking lot is already full

This requires synchronization between consumers and producers

• Semaphores can provide the necessary sync.
  • note, semaphores do not have a “get” function to check # of available resources
• Need 2 semaphores for 2 different types of resources
  • consumer’s resources are “non-empty spots”
  • producer’s resources are “empty spots”

struct semaphore *Items, *Spaces
Items = sem_create(...) // initially 0
Spaces = sem_create(...) // initially N

Producer's pseudo-code:
    P(Spaces)
    Add items to buffer
    V(Items)

Consumer's pseudo-code:
    P(Items)
    Remove items to buffer
    V(Items)

Problem

• Buffer is a global shared variable
  • Semaphore does not offer mutual exclusion when used in the way above. Above, it just keeps track of the items available
  • Can have multiple producers adding to the buffer at the same time
    • Need to protect the “add items” in a critical section

A barrier semaphore

• Semaphore whose initial value is 0. P the semaphore however many times for # of threads forked, and each thread will V the semaphore when it’s done
  • This forces the parent thread to wait until all threads are completed

CONDITION VARIABLES

Another synchronization primitive

• Each condition variable is intended to work together with a lock
  • use lock to access a critical section
  • but, inside the section, need to wait for a condition variable to be true
    • are we just going to spin until some variable, say, x=5? This costs CPU bandwidth
    • the thread that may set x=5 will/might need to make the update using the same lock you’re currently occupying
• Condition variables are only used from within the critical section that is protected by the lock
• Say we have a bottle of beer
  • if beer in mug, drink
  • if no beer, hand is still on the mug, but while you’re holding onto the beer, the bartender can’t fill it up
    • if no beer, take hand off cup (release lock) and let bartender take cup (acquire lock)
    • bartender fills it, releases lock, gives beer back, wakes you up, you acquire lock again
• Three operations are possible on a condition variable
  • If we’re in a critical section, and we realize a variable is not the way we want it, we call cv_wait
    • it relinquishes your hold on the critical section, and thread goes to sleep
    • lock is released as well
    • Once the thread is unblocked, it reacquires the lock
  • Once a variable has been updated, call cv_signal to wake one thread waiting on this condition variable
  • cv_broadcast is similar, but unblocks all threads that are blocked on the condition variable

Using Condition Variables

Condition variables get t heir name because they allow threads to wait for arbitrary conditions to become true inside of a critical section

• Normally, each condition variable corresponds to a particular condition that is of interest to an application
  • for example, in the bounded buffer producer/consumer problem. Two conditions are
    • count > 0 // there are items in the buffer
    • count < N // there is free space in the buffer
  • when a condition is not true, a thread can wait on the corresponding condition variable until it becomes true
  • when a thread detects that a condition is true, it uses signal or broadcast to notify any threads that may be waiting
• Note that signalling (or broadcasting) to a condition variable that has no waiters has no effect. Signals do not accumulate

int volatile count = 0
struct lock *mutex; // for mutual exclusion
struct cv *notfull, *notempty // condition variables

Produce(itemType item) {
    lock_acquire(mutex);
    while (count == N) {
        cv_wait(notfull, mutex); // wait until buffer is not full
    }
    add item to buffer // list_append()
    count++
    cv_signal(notempty, mutex)
    lock_release(mutex)
}

itemType Consume() {
    lock_acquire(mutex)
    while (count == 0) {
        cv_wait(notempty, mutex) // wait until buffer is not empty
    }
    remove item // list_remove_front()
    count--
    cv_signal(notfull, mutex) // signal other threads that need notfull=true
    lock_release(mutex)
    return(item)
}

Waiting on Condition Variables

• When a blocked thread is unblocked (by signal or broadcast), it reacquires the lock before returning from the wait call
• A thread is in the critical section when it calls wait, and it will be in the critical section when wait returns
  • However, in between the call and the return, when the caller is blocked, th caller is out of the critical section, and the other thread may enter
• In particular, the thread that calls signal (or broadcast) to wake up the waiting thread will itself be in the critical section when it signals.
  • the waiting thread will have to wait (at least) until the signaller releases the lock before it can unblock and return from the wait call

If you are a thread that is to make the condition true, you need a lock to protect your access to the shared variable

• at the point you call cv_signal, you want to guarentee the condition is still true. That some fucker hasn’t changed it between then and now
• must be the owner of the lock to signal or broadcast

cv_wait(cv *cv, lock *lock)
    wchan_lock(cv->wc)
    // cv needs own wait channel. Need to keep track of threads waiting on this condition
    lock_release(lock) // release hold on critical section
    // someone else needs access to the critical section to make it true
    wchan_sleep(cv->wc)
    --> on a signal or broadcast, code resumes here
    lock_acquire(lock)
    // we're working with the critical section again, need to acquire lock

Monitors

Next most similar thing to condition variables

• MESA
  • The condition variables that we described in our notes
  • Inside cv_signal, check if_owner_of_lock, wchan_wakeone(cv->wchan)
• HOARE
  • Inside cv_signal, instead of waking up the thread and let you release the lock, and then let another thread reacquire the lock…
  • Signal thread and then you block. The other thread starts running again

CS350, 2017-05-25

Condition variable test: synchtest.c, line 61, sy3

Incrementing # of CPUs

• don’t exceed 32 CPUs. Use 8 or 16
• By increasing the # of CPUs, you increase the probability of encountering sycnhronization issues

Assignment 1 hints

Traffic light: synchronize cars going through an intersection, and ensure no accidents

• Solve sync problem using locks and control variables
• Cars can go N->S, E->W, and make L/R turns
  • When you come up to an intersection, theres >1 car going through at once. Instead of just letting one car through N->S, we want cars going S->N to also go through

Hints

• Best solutions? 4 CVs and 1 Lock
• Also possible to use 3 CVs and 1 Lock
  • Consider the rules
    • If a car is going N->S, what are the other possible cases of cars going through the intersection? Definitely not E->W or W->S
• Don’t worry about fairness
  • If first solution works, fuck it. Move on
  • If not, …
    • Real traffic lights work in a few different ways. Some lights operate on timers, regardless of the number of cars waiting at the light. Don’t use timers, but check out an alternate approach
    • Suppose cars are going N->S. If no cars are going E->W, no point switching light. If a car shows up and is waiting for the light to switch
      • Could wait for the intersection empty, then switch
      • Or recognize a waiting car, and let at most N more cars, then switch
        • Set a “pressure plate” to check number of cars going thru
      • cv_broadcast wakes up every thread
        • if you wake up 5 threads but then need to sleep 95 others because you woke 100, is that worth?
• Common approach: 1 CV for each direction of origin
  • There are other possible reasons for each CV…
• There is a dynamic array implementation in array.h
• Don’t worry about # of lanes. If cars go N->S at the same time, they’ll call entry() at slightly different times anyways.
• See Piazza about # of iterations and tests to test with
• Don’t do extra work

Deadlocks

The programmer is responsible for discovering and handling race conditions, and figuring our which synchronization primitives are needed.

• Suppose there are two threads and two locks, lockA, lockB, both initially unlocked
• Suppose the following sequence of events occur
  • Thread 1 acquires lockA
  • Thread 2 acquires lockB
  • Thread 1 tries to acquire lockB
  • Thread 2 tries to acquire lockA

Problem(s)

1. (1) gets lockA
2. (2) gets lockB
3. (1) tries to get lockB, goes to sleep waiting for lockB
4. (2) tries to get lockA, goes to sleep waiting for lockA
5. This code is permanently stuck, because only (2) can release lockB, but is asleep. Only (1) can release lockA, but is asleep.

Two Techniques for Deadlock Prevention

No Hold and Wait

• Prevent threads from requesting resources if it currently has a resource(s) allocated to it.
• A thread may hold several resources, but to do so it must make a single request for all of them
• Suppose we have multiple resources: critical section, modem, and printer
  • If we have a lock on printer, but cannot acquire a lock on the modem, we must release the lock on printer
  • With that said, we need a new method of acquiring locks: try_acquire
    • returns true if you get the lock
    • returns false if you do not get the lock
      • don’t block
    • must acquire all resources in one call, together

acquire(res0); // regular acquire: you either wait on the first resource, or get it. We don't own any other resources at the moment

while(I don't get all resources) {
    try_acquire(each resource we want)
    if false
        release all held

    // spin in loop trying to acquire **all** resources until we get them
}

This thread is spinning instead of blocking

• It avoids deadlock, but introduces busy waiting. The loop hogs CPU until all resources are acquired
  • quite simple to implement, and is popular

Resource Ordering

Assign a number/order to resource types, and require that each thread acquire resources in increasing resource type order

• A thread may make no requests for resources of type <= i if it is holding resources of type i.
• Just ensure we are acquiring locks in same increasing order

Summary

…

CS350, 2017-05-30

Processes and System Calls

What is a process?

• An environment in which an application program runs
• A process includes virtualized resources that its program can use
  • one (or more) threads
  • virtual memory, used for the program’s code and data
  • other resources
    • e.g. file and socket descriptors
• From now, programs have one thread
• A process itself is >1 thread
• Processes are created and managed by the kernel
• Each program’s process isolates it from other programs in other processes
  • address space for every program is unique
  • programs/processes cannot talk to each other in direct manners

System Calls

• System calls are the interface between processes and the kernel
• A process uses system calls to request OS services
• Service examples
  • create, destroy, manage processes
    • fork, execv, waitpid, getpid
  • create, destroy, read, write files
  • …

System Call Software Stack [L4_S4]

The application makes a call to the Syscall Library (API), which makes a system call to the kernel

• don’t want user application to communicate with the kernel directly. The application and Syscall library are unprivileged code
• the kernel is privileged code
  • these are states we put the CPU in. The application is not permitted to communicate with the hardware, like shutting down the computer.
  • Why separate user code from the kernel?
    • Instead of using a nice abstracted library to access the kernel, then developers will try to interface with the hardware better than the kernel
    • So, different applications will have a bunch of different drivers. One of the goals of the kernel is to abstract itself/the hardware for user applications
    • Moreover, different hardware needs different drivers.
    • Additionally, errors like segmentation faults (which means you’re writing to memory outside your address space) would not fire, and you’d end up overwriting memory you do not own.

Kernel Privilege

• The kernel runs at a higher level of execution privilege than application code
  • privilege levels are implemented by the CPU
• The kernel’s higher privilege level allows it to do things that the CPU prevents less-privileged applications/programs from doing
  • e.g. application programs cannot modify the page tables that the kernel uses to implement process virtual memories
  • e.g. application programs cannot halt the CPU
  • Something needs to be able to manage these hardware-level settings, processes, data, etc.
• These restrictions allow the kernel to keep processes isolated from one another—and from the kernel

Application programs cannot directly call kernel functions or access kernel data structures.

How System Calls Work (Part 1)

• Isolating Application/Syscall Library from Kernel
  • benefits
    • can patch the kernel without affection user applications
  • so how do we do things like save files, which requires privileges?

There are only two things that make kernel code run

• Interrupts
  • interrupts are generated by devices
  • an interrupt means a device (hardware) needs attention
• Exceptions
  • exceptions are caused by instruction execution
  • an exception means that a running program need attention
  • e.g. calling an assembly instruction that doesn’t exist
  • e.g. dividing by 0
  • if we want to save a file, we will use exceptions

Interrupts Revisited

• An interrupt causes the ardware to transfer control to a fixed location in memory, where an interrupt handler is located.
  • the trap frame saves the complete context of the registers, and calls an interrupt handler from the kernel to figure out which interrupt was fired and how to deal with it
  • the trap frame must also switch the CPU from user-mode to kernel-mode (privileged-mode)
  • when restoring the context of the thread later, need to change from kernel-mode to user-mode
    • this is how the kernel gets its execution privilege

Exceptions

• Condition that occur during the execution of a program instruction
  • e.g. arithmetic overflows, illegal instructions, page faults
• Detected by the CPU during instruction execution
• CPU handles exceptions like it handles interrupts
  • control is transferred to a fixed location (trap frame), where an exception handler is located
  • processor is switched to privileged execution mode
• Exception handler is part of the kernel

MIPS Exception Types [L4_S9]

Note that OS/161 treats exceptions and interrupts the same way.

• EX_IRQ == 0 is a type of exception that represetns a hardware interrupt.
• When we want our application to make a kernel call, we fire a system call
  • we need to raise an exception of a “system type”
    • EX_SYS
      • indicates user application wants the kernel to do something

While inside trap frame, need to know what type of exception it was to figure out what to do

• One of the Exception Types will go into a register
• The trap frame will call the appropriate handler/dispatcher after reading the exception type

How System Calls Work (Part 2)

1. To perform a system call, the application program needs to raise an exception to make the kernel execute
   • on the MIPs, EX_SYS is the system call exception
2. To cause the exception on the MIPS, the application executes a special purpose instruction: syscall
   • other processor instruction sets include similar instructions
     • e.g. syscall on x86
3. Kernel’s exception handler checks the exception code (set by the CPU when the exception is raised) to distinguish system call exceptions from other types of exceptions

System Call Software Stack (Updated) [L4_S11/S12]

1. Application makes call to Syscall wrapper library
2. Syscall Library raises an exception. The exception type is set in a register. The library function performs syscall instruction
3. The Kernel handles the exception, and returns the value(s) (in a register, perhaps)
   • creates trap frame to save application program state
   • determines that this is a syscall exception
   • determines which syscall is being requested
   • does the work for the requested system call
   • restores the application program state from the trap frame
   • returns from the exception
4. The Syscall Library function finishes and returns from its call
5. application continues excecution

li $v0, 1 ; load the system call code
; this code is predetermined
li $a0 ... $a3 ; load the system call params

syscall ; raises exception EX_SYS

Which System Call?

There are many different system calls, but only one syscall exception. How does the kernel know which system call the application is requesting?

• kern/include/kern
  • application binary interface (ABI)
  • syscall.h
    • contains type codes for different system calls
• the kernel defines a code for each system call it understands
• the kernel expects the application to place a code in a specified location before executing the syscall instruction
  • for OS/161 on MIPS, the code goes in register $v0
• the kernel’s exception handler checks this code to determine which system call has been requested
• the codes and code location are part of the kernel ABI

Some OS/161 System Call Codes [L4_S14]

System Call Parameters

…

User and Kernel Stacks

• Every OS/161 process thread has two stacks, although it only uses one at a time
  • if it only had 1 stack?
    • suppose we’re executing code, and reach an exception
    • there’s no stack for the kernel code to execute
      • We don’t want the kernel to expose its data to the user application by putting its data on the user application stack
• User Stack
  • used while application code is executing
  • this stack is located in the application’s virtual memory
  • it holds activation records for application functions
  • the kernel creates this stack when it sets up the virtual address memory for the process
• Kernel Stack
  • used while the thread is executing kernel code, after an exception or interrupt
  • this stack is a kernel structure
  • in OS/161, the t_stack field of the thread structure points to this stack
  • this stack also holds activation records for kernel functions
  • this stack also holds trap frames and switch frames
    • kernel creates them, so it holds them
    • once the exception/interrupt is handled, trap frame restores thread context. It also reverts to the user stack. Then it reverts the CPU to user-privilege

Exception Handling in OS/161

• First to run is careful assembly code that…
  • saves the application stack pointer
  • switches the stack pointer to point to the thread’s kernel stack
  • carefully saves application state and the address of the instruction that was interrupted in a trap frame on the thread’s kernel stack

Implementing System Calls and Debugging

kern/arch/mips/syscall.c

• add syscall type handling here
• tf->tf_epc += 4
  • when receiving syscall, program counter will not advance. So, need to manually increment to jump over the syscall to avoid re-executing it

Debugging

• continue using -w flag
• set directory
• target the unix
• trace through the system call
  • put a breakpoint at the line where you call something like SYS_open
  • backtracing will show the stack contains only kernel function activations
  • …

CS350, 2017-06-01

Multiprocessing

Recall we have a quantum. When it expires, we have a pre-emption, and thus a context switch.

• The kernel just sees threads. If we have two (single-threaded) processes, we’ll have timer interrupts
  • This interrupt will cause a switch to kernel mode
  • Will check how long the thread’s been running
    • Not long enough? Go back to Process A
  • Keep checking until it exceeds the quantum
• The kernel looks at the ready pool of threads and chooses another thread to run
  • In this example, Process B starts running
  • When Process B exceeds the quantum, Process A starts running again

Animation Notes

• Process 1 is running its application. It maintains its application stack frames.
  • close(1)
    • executes like normal, adds a stack frame
  • Makes a syscall: li a0,1 ; li v0,49 ; syscall
    • Starts running common_exception function
      • switches from user mode to privileged mode, and switches to the thread’s kernel stack
      • saves processor state (registers, etc) into a trap frame
      • Now, need to deal with the exception
    • mips_trap(…)
      • Check whether this is an exception, interrupt, or system call
    • syscall(…)
      • Checks the code of the interrupt
      • Turn off interrupts for a little bit. If the exception code is not an interrupt, we turn interrupts back on immediately
        • When a hardware device fires an interrupt, it will keep firing until the CPU acknowledges it has been handled
    • sys_close(…)
• While kernel is trying to execute sys_close(...)
  • Pre-emption continues even if we are executing kernel code
  • When transferring control to mips_exception, don’t need to switch to privilege-mode, nor switch to kernel stack, because we’ve already done that
  • mips_trap()
  • …
  • thread_yield()
  • thread_switch()
  • switch frame
• Process 2: suppose it had some stuff in its kernel stack already (it was executing before)
  • It executes the code (pops the stack), goes through the trap frame, etc
  • Switch from kernel-mode to user-mode

Suppose the interrupt never happened. We continue off from the first sys_close(...)

• Handle the sys_close(…)
  • increment PC by 4, etc
• Return from syscall(...)
• Return from mips_trap(...)
• We’re back the trap frame
  • Need to jump back to thread’s application code
  • rfe returns the CPU to unprivileged mode

System Calls for Process Management

• fork creates a new process
  • does not createa new blank process, but rather an identical clone to the process that called fork
    • user stack is the same
    • values in registers are the same
    • address spaces are the same
  • difference is that when forking, the new process does have a new id number
  • fork returns in both the parent and the child. Their program counter is pointing to the same instruction
  • also, return value of fork is different
    • parent returns process id of new process that was created as a result of calling fork
    • child returns 0
• execv changes the program that process runs
• _exit destroys a process. It is called manually
  • terminates the process that calls it
  • process may supply an exit status code when it exits
    • the kernel keeps this return value for future use
• waitpid synchronizes processes to run in a particular order
  • lets a process wait for another to terminate, and retrieve its exit status code (from _exit)
  • makes sense. Sometimes we want to wait for another process to terminate before proceeding
  • waitpid is equivalent to watching a child
    • when a child dies, the parent will want to know why it died
    • it will block the process until the child dies, and provides the exit status
• getpid for attribute management

Some Code: fork, _exit, getpid, and waitpid

main() {
    rc=fork(); // returns 0 to child, pid to parent
    if (rc==0) { // child executes this code
        my_pid = getpid();
        x = child_code();
        _exit(x);
    } else { // parent executes this code
        child_pid = rc; // if we're in the parent code, rc is the child\_pid
        parent_pid = getpid();
        parent_code();
        p = waitpid(child\_pid, &child\_exit, 0);
        if (WIFEXITED(child_exit))
            printf("child exit status was %d\n", WEXITSTATS(child_exit));
    }
}

All fork does is create a clone of the existing process

• If we want to open a program from a shell, we can’t just fork the shell…
• In order to set what program the process should run, you need to use execv
  • When we call execv, we need to change the process’ address space. Clear out the stack, etc
  • Open the binary file
  • Create a new address space and new block of memory that is appropriate for the new program
    • With a new program, it starts executing at the entry point
  • id of the process does not change
  • user of the process does not change

Some code: execv

int main() {
    int rc=0;
    char *args[4]; // array of strings

    args[0] = (char *) "/testbin/argtest";
    args[1] = (char *) "first";
    args[2] = (char *) "second";
    args[3] = 0;

    rc = execv("/testbin/argtest", args);

    // if execv succeeds, the program that called it is killed
    // it does not return
    // the last thing execv does is jr'ing to the beginning of the execution of the new program
    printf("If you see this, execv failed\n");
    printf("rc = %d errno = %d\n", rc, errno);
    exit(0);
}

Assignment 2a/2b

• fork, waitpid, _exit in 2a
• execv in 2b

CS350, 2017-06-06

Assignment 2A Hints

System calls

• pid_t fork(void)
  • create a copy of the current process. Return 0 for child process, and the PID of the child process for the parent
  • many of the marks for 2A
  • create new process that is an identical clone of the process
  • When the two processes keep running, they can fork into different directions depending on the returned value (whether they’re a child or parent)
• pid_t waitpid(pid_t pid, int *status, int options)
  • Waits for the process specified by pid. Status stores an encoding of the exit status and the exit code
  • Returns the PID of the process on success, or -1 on error (it can also return 0 if the option WNOHANG is specified and process PID…)
• pid_t getpid(void)
  • returns the PID of the current process
  • does not need to be implemented right away
• …

fork

1. A process is really just a data structure that holds some information about the program running/to be run
   • Use proc_create_runprogram(...) to create the process structure
     • set up the VFS (file system) and console
     • found in kern/proc/proc.c
   • Don’t forget to check for errors
     • e.g. what happens if proc_create_runprogram returns NULL?
       • Not enough memory, other issues with memory, etc
       • At every stage, we must check for an error. If we receive an error, need to return an error code
         • These error codes can be found in kern/include/errno.h
2. Create a new process structure for child process
   • empty to start with
   • Child process must be identical to the parent process
   • as_copy() creates a new address space, and copies the pages from the old address space to the new one
3. Create and copy address space (and data) from parent to child
   • Address space is not associated with the new process yet
     • look at curproc_setas to figure out how to give a process an address space
       • don’t need to manually malloc and copy over
       • found in kern/proc/proc.c
       • note, you’re not setting the address space of the current process, but rather the child process. See the implementation to see how to do update the address space of a different process
       • again, when encountering any error, need to return an error code
   • related functions can be found in include/addrspace.h
4. Attach the newly created address space to the child process structure
   • set the pointers properly using the helper functions
5. Assign PID to child process and create the parent/child relationship
   • How we do this is up to us
   • PIDs should be unique (no two processes should have the same PID)
   • PIDs should be reuseable
     • When can we reuse a PID?
     • This is partially dependent on your implementation. We’ll talk more about this whn we look at _exit and waitpid
       • Also, in the future, need to create a parent-child relationship between two processes
         • maybe every parent keeps a list of its child processes (as pointers)
         • or a list of children PIDs which can be used as keys in a master table
     • Remember that you need to provide mutual exclusion for any global structure!
   • Need to look up a process in a process table later
     • Implementation of the table is up to us
6. Create thread for child process
   • need a safe way to pass the trapframe to the child thread
   • Now that we have a process, with an address space, with a PID, and a parent-child relationship, need to create a thread
   • thread_fork(...) has two params
     • the second takes a child process
     • entry point function? Take trap frame from parent and put it on the child thread kernel stack
       • pass it in some way from the parent into the child
       • if we look at the entry function prototype, it takes a void param. Can pass trapframe through there
       • if we pass pointer directly into the child, need to use synchronization
       • if we don’t want to use synchronization, need to copy trapframe onto heap and pass the heap pointer to child
     • user stack is already prepared. We’re setting up the kernel stack
       • When entry point for the new thread is running, will be in kernel mode
       • Copy data into a local variable and will be automatically in the kernel stack for the thread, because when the entry point starts running, it is running in kernel mode
     • using local trapframe variable, need to set register $a3 to be appropriate return values
     • also need to increment PC by 4
       • this is another local variable
     • Do not modify the trapframe until we attach it to the child process, so do it in the entry point function
7. Child thread needs to put the trapframe onto the stack and modify it so that it returns the current value (and executes the next instruction)
   • see above step
8. Call mips_usermode in the child’s thread to go back to user-space
   • the child has no way on its own to go back to user-privilege
   • mips_usermode fakes a return from a syscall. Will return the trapframe and switch to user-mode

OS/161 provides a large number of helper functions

waitpid

Block parent process until child has exited by calling _exit

• Need to be implemented at the same time as _exit
• See widefork.c test for usage of waitpid
  • WEXITSTATUS(...) is implemented for us, only need to implement waitpid
• waitpid can only be called on a child
  • first things to check is if the given PID one of my children
    • if not, return immediately with an error code (see errno.h, or 2A hint)

1. If waitpid is called before the child process exits, then the parent must wait/block
   • What should it block on? Semaphore? Condition variable in a process table?
   • Condition variable specific to the parent process?
   • To the child process?
   • Use a condition variable. When waidpid is called, call cv_wait on the child process, thus blocking until the child exits
2. If waitpid is called after the child process has exited, then the parent should immediately get the exit status and exit code
   • the child needs to leave some data as long as its parent is alive
     • cannot lose this information. Need to be saved somewhere
     • suppose your parent is dead
       • do not keep code around. No one will care about your rval anymore
     • suppose a parent dies after all its children
       • can delete the exit codes left behind by its children
       • only time we keep these exit codes is when the parent still exists
3. PID cleanup should not rely on waitpid
   • parent process is not guaranteed to call waitpid when it exits
4. Encoding exit status and exit code
   • exit code comes from _exit()
   • In this assignment, exit status should always be _WEXITED
     • take the integer parameter from exit() and combine them
       • use a helper function to do this combination

In _exit(), when a child process dies, it should wake up its parent…

Extras

• Implement the WNOHANG option
  • if child is still alive, return ECHILD instead of blocking
  • this helps the parent ping the child, checking if it’s still alive
• Add support for WAIT_ANY (-1 PID)
  • block until first child exits
  • return that child’s PID in the return value

getpid

• Returns the PID of the current process
• (see slides from Piazza)

_exit

• Causes the current process to exit
  • don’t worry about having multiple threads in a process
  • We don’t expose thread_fork as a system call. Therefore, user processes will only have one thread
• Exit code is passed to the parent process
• When a child terminates if my parent is waiting on me to exit
  • if yes, need to wake
    • once they wake up, they will return from the waitpid call, get my exit status code, and delete me
  • only need to store the exit code if my parent is alive

Common Problems

• Whe implementing fork, there tends to be a struggle with putting the trapframe on the kernel stack
  • easy to do, but easy to make a mistake w/ memory (typical C-pointer problems)
• Deadlock on waitpid and _exit
• Deadlock on PID table

Virtual Memory

Recall the form of the address space

0x0 | code | Data constants | Heap ---\> <--- Stack |

RAM

OS is going to find some free space in RAM and give it to my program. Suppose our RAM looks like the following

0x0 | | Minecraft | MATLAB | | 16gb

• Suppose Minecraft used the address space from 0x10005000 to 0x10008000
• And MATLAB used 0x10008000 to 0xFFD00000
• If our user program knows exactly where it lives in real memory
  • this is an issue, because by virtue of knowing where I live in memory, I know where other people live in memory
  • I could access other people’s memory using pointer arithmetic
  • It might be ok if Minecraft screws with MATLAB, but we’d have serious issues if Minecraft was touching our operating system’s memory
    • We use virtual memory to make programs think they’re the only program in existence

CS350, 2017-06-08

• When we use virtual memory addresses, we need to ensure our translations between physical memory and virtual memory addresses to be efficient (and correct)
• Moreover, we need a kernel that is efficient at distributing physical memory
• A virtual address space can be smaller than the physical address space

Virtual Addresses

• The kernel provides a separate, private virtual memory for each process
• The virtual memory of a process holds the code, data, and stack for the program that is running in that process
• If virtual addresses are V bits, the maximum size of a virtual memory is 2^v bytes
  • for MIPS, V=32
  • in our slides, V=16
• Running applications see only virtual addresses
  • program counter and stack pointer hold virtual addresses of the next instruction and stack
  • pointer to variables are virtual addresses
  • jumps/branches refer to virtual addresses
  • even our kernel will run on a virtual address space

Address Translation

• Each virtual memory is mapped to a different part of physical memory
  • if we want to execute an instruction, and we have its address, we need to find its actual address in physical memory
• Since virtual memory is not real, when a process tries to access (load or store) a virtual address, the virtual address is translated (mapped) to its corresponding physical address, and the load or store is performed in physical memory
• Address translation is performed in hardware, using information provided by the kernel
  • the Memory Management Unit (MMU) is a physical device, whose sole job is to take a virtual address and translate it into a physical address
  • the MMU cannot operate on its own
    • the OS needs to give some information. This info depends on the architecture and virtual memory implementation you have

Dynamic Relocation [vm_S7]

Suppose we have some physical memory

• 0x0 to 0x3ffff
• When we try to allocate memory for a new process, I will find a chunk of memory that fits the process, and I will claim it
  • I will also assign this chosen memory space for the process
  • perhaps PROCA will occupy 0x0 to 0x6fff
  • and PROB will occupy 0x6fff to …
• If a process only needs 2KB, that’s all we give it. We don’t necessarily allocate the limit/maximum memory a process could use
• Static relocation
  • We allocate memory as we go, for however much the process requires
  • Problems
    • Suppose PROC_C occupied 2KB
    • and PROC_E occupied 10KB
    • We free the two, but the two processes had separate locations (non-adjacent) in memory
      • We freed 12KB, but it is fragmented. A 12KB program will not be able to fit, though we’d like it to be able to
• Dynamic Relocation
  • When we encounter fragmentation, we just shift some processes’ physical address space
  • We keep track of the offset (from 0) and the limit of the process’s memory usage
    • We use offset and limit to do our translation

Address Translation for Dynamic Relocation

• CPU includes the MMU, with a relocation register and a limit register
  • relocation register holds the physical offset (R) for the running process’ virtual memory
  • limit register holds the size L (limit) of the running process’ virtual memory

if v >= L, then generate exception
else
    p = v + R

• recall, the virtual address begins at 0 and is limited
• The kernel maintains a separate R and L for each process, and changes the values in the MMU registers when there is a context switch between processes

Properties of Dynamic Relocation

• Each virtual address space corresonds to a contiguous range of physical addresses
  • OS is responsible for finding a contiguous walk of memory
  • If a process requires 2GB, we need 2GB of contiguous memory
    • What are the odds of finding 2GB of free memory?
    • Dynamic relocation lets us defragment our memory in order to find this contiguous walk of 2GB
      • Problem is that this defragmentation is rather slow
        • Have to move almost every other process’ address space
• While dynamic relocation is the easiest, and maybe fasted, it is susceptible to internal fragmentation
  • Solving this is difficult
  • Although it is efficient in how much data is required to implement, and how fast the translation occurs

Example: Process A [vm_S10]

Limit register:      0x0000 7000
Relocation register: 0x0002 4000

v = 0x102C  p = 0x0002 502C
v = 0x8800  p = exception
v = 0x0000  p = 0x0002 4000

Example: Process B [vm_S11]

Limit register:      0x0000 c000
Relocation register: 0x0001 3000

v = 0x102C  p = 0x0001 402C
v = 0x8800  p = 0x0001 B800
v = 0x0000  p = 0x0001 3000

• Note, theoretically, virtual memory addresses could be the same as physical memory addresses
  • The offset will have to be 0
  • However, since the OS/kernel resides at address 0 in physical memory, this shouldn’t happen

Problem with Dynamic Relocation

• As mentioned earlier, in order to find a contiguous range, we need to defragment some memory. Finding the memory to defragment is too much work

Potential Solution

• If we can’t find a contiguous piece of memory, why can’t we just find the different chunks of free memory and put them together?
  • This is tough to manage, but we do have a solution along these lines

Paging: Physical Memory

• Suppose we have 256KB total physical memory
• We pick some size, divide the entire physical memory in pieces of this size
  • Suppose we choose a physical page size of 4KB (4096 bytes)
  • We divide 256KB by 4KB, and so we have 64 frames/pages of memory

Note

• 4KB is 2^12
• 2^12 is 4096 bytes

• 4096 is 0x1000

• If I have a 4KB frame, I should have 4KB pages
• Each address space, now, will also be divide into some number of pages
• We won’t have external fragmentation here, but we will have some internal fragmentation
  • If you only need 1KB, you’re going to get 4KB anyways
• Suppose we need 28KB for a process
  • We traverse our physical memory and find (and use) the first 7 (x4 = 28KB) unoccupied pages
  • We can have pages across memory, and it need not be in order
  • This solves the external fragmentation because we look for pages, which is the same size of the frame. So, we never allocate for anything bigger or smaller that we need(?)
• With this implementation, we’ve mapped pages of virtual memory to frames of physical memory
  • These frames don’t have to be in RAM
  • Most OS’s only load pages of the address space in RAM that you are actively using
    • Your address space can have some pages in memory, other pages in other devices
      • this is called Demand Paging

Page Tables

• Knowing page number, you can figure out the address of the frame
• This table is created and maintained by the operating system
• Every process has own page table
• Size of the page table?
  • size = virtual memory size / page size
    • not how much memory, but rather how many entries

Address Translation in the MMU, Using Paging

• The MMU includes a page table base register which points to the page table for the current process
• How the MMU translates a virtual address
  • determine the page number and offset of virtual address
    • page number is the virtual address divided by the page size
    • offset is the virtual address modulo the page size
  • looks up the page’s entry (PTE) in the current process page table, using the page number
  • if the PTE is not valid, raise an exception
  • otherwise, combine the page’s frame number from the PTE with the offset to determine the physical address
    • physical address = (frame number * frame size) + offset

See vm_S17 for illustration of Address Translation

page # = v / page size

offset = v % page size
// modulo with hex??
// how many bits does my page # need?
// how many entries in our page table? If we have virtual memory that is
// 64KB, we have 16 pages (maximum)
// How many bits do I need to represent 16? 4 bits
// How many bits do I chop off for the modulo?

// how many bits for pg#? log(size(PTE));
// if PTE=16, then bits for pg#=4
// take virtual address and the highest order 4 bits are the pg#. The rest are the offset
// this is easier to apply to hex than actually modulo'ing hex

// assuming PTE lookup was valid
physical address = (frame # * frame size) + offset

• The OS for OS/161 determines the stack size for processes
  • Modern OS’s have more flexibility but OS/161 just uses this simplification

CS350, 2017-06-13

Midterm Coverage

Beginning of the course to slide 40 of virtual memory

Recall

1. p-bit addresses -> 2^p bytes
2. we divide physical memory into frames
3. and divide virtual memory into pages
4. page size == frame size

Questions

How many pages are there, or what is the size of the page table

• given an amount of virtual memory, how many pages fit into it?
  • v.mem size = 2^v bytes
  • pg. size = 2^m bytes

  • of pages = size of page table = # of page table entrys = 2^v / 2^m

  • of bits for pg. number = log(#PTES)

    • they’ll give us #PTEs as a power of 2
    • eg. #PTES = 2^14
    • then # of bits for pg. number = 14
  • we have pg. number to figure out which page of virtual memory the address sits in, and then we need an offset to determine where in physical memory this address is
    • pg. offset bits = log(page size)
      • eg. pg. size = 2^10, then pg. offset bits = 10
  • once we have page number, we use it to look up a page table entry
    • this will tell us the corresponding physical memory frame number
      • if valid bit is set, the frame is in use
  • once we have a frame number, we get physical address = frame# * frame_size + page_offset
    • (* frame_size ?)
      1. 4kb = 0x1000 = 2^12

Examples

Address Translation (Process B) [vm_s19]

phys. addr = 18 bits
v. addr = 16 bits

...

• if we had an address that began with 0xe…, our valid bit in the page table is 0
  • this means there’s no translation.
  • If the address cannot be translated, there is an exception

Other Information Found in PTEs

• PTEs may contain other fields, in addition to the frame_number and valid_bit
  • eg. read_only_bit
    • would handle cases where you try to write to the memory address
  • eg. bits to track page usage
    • reference (use) fit
      • has the process used this page recently?
    • dirty bit
      • have contents of this page been changed?
    • these bits are set by the MMU, and read by the kernel (more on this later)

How Large Are Page Tables?

A page table has one PTE for each page in virtual memory

• page table size = (number of pages) * (size of PTE)
• number of pages = (virtual memory size) / (page size)
• from this point on, page table size refers to the amount of space a page table occupies in memory
  • #PTEs * page size
• example
  • 64KB v.mem, 4kb pages, 32 bits per PTE
    • page table is 64 bytes
• page tables for larger virtual memories are larger

Problems

• page table with maybe a million entries, but our program is only a few kilobytes large
  • only a few PTEs will be used, out of millions available
• our page tables are really large, but mostly empty for most programs
  • not efficient
• good at preventing external fragmentation, but becomes deadweight lots of times
  • waste of space
    • whose space are we wasting? The kernel’s
    • every process has a page table

Summary: Roles of the Kernel and the MMU

Kernel

• manage MMU registers on addr. space switches (context switch from thread in one process to thread in a different process)
• create and manage page tables
  • creates page table when process is created
• manage (allocate/deallocate) physical memory
• handle exceptions raised by the MMU

MMU

• translate v.addr to phys.addr
• check for and raise exceptions when necessary
• the kernel must also notify the MMU to use new page tables
• must do at least one address translation
  • it must translate the PC address to a physical addr
    • add $r0, $r1, $r2
• lw $12, X($s3)
  • each loadword instruction requires at least one translation
• accessing memory is expensive
  • add, sub, add, add, mult, mflo, mfhi, add
  • for each of these assembly instructions, the MMU has to translate an address
    • the PC that points to them needs to be translated
    • probability that these sequential instructions live on the same page?
      • relatively high
      • spans at most two pages
        • why are we translating their addresses individually, each time?
  • if we have an array, our index values occupy sequential addresses
    • so, there’s a pretty good chance that most arrays we have will fit in a single page of memory
      • yet, our MMU will still translate the v.mem addr of each of these values
      • we want to reduce how often the MMU has to go to RAM (to find the page table) for page-to-frame mapping

Translation Lookaside Buffer (TLB)

• Caches our page-to-frame mappings
• When we have a v.addr, and we obtain a page number, we first check the cache instead of going to the page table which resides in RAM
  • much faster to access this than RAM

TLB Usage

What the MMU does to translate a virtual address on page p

if there is an entry (p, f) in the TLB, then
    return f
        ; TLB hit
else
    find p's frame number (f) from the page table
    add (p, f) to the TLB
        ; evict another entry is full
        ; to decide who to evict, can use a dirty bit
    return f
        ; TLB miss

• If the MMU cannot distinguish TLB entries from different address spaces, then the kernel must clear or invalidate the TLB on each context switch from one process to another
  • as_activate(...)
  • if we don’t clear, we will have page-to-frame mappings in our TLB for the incorrect process
• This is a hardware-managed TLB
  • the hardware goes to RAM and gets a new page-to-frame mapping after a TLB miss, etc
    • problem with hardware doing the work is that the hardware needs to know exactly what the page table entries look like
    • needs to know exactly what our page table implementation does
    • essentially, the hardware specifies, to the OS, how paging works
    • very fast, but restrictive from an OS

Software-Managed TLB

MIPS has a software-managed TLB, which translates a v.addr on page p like so

if there is an entry (p, f) in the TLB, then
    return f
        ; hit
else
    raise exception
        ; miss

• In case of a TLB miss, the kernel must
  • determine the frame number for p
  • add (p, f) to the TLB, evicting another entry is necessary
    • for q3, we randomly evict an entry
• After the miss is handled, the instruction that caused the exception is retried