Jun Zheng Posts

CSCB63 Data Structure Design and Analysis - Fibonacci Heaps

Basic introduction to fibonacci heaps and some comparson with regular heaps.

CSCC69 Operating Systems - Threads

Overview

Threads are basically mini-processes within a process. However they share the same address space.

Creating threads are much faster than creating processes, in some systems, this can be 10x to 100x faster.

Think of threads as JS event loops, basically it.

Classic Thread Model

The classic thread model basically have all threads with their own stack and own PC.

Everything else is shared. The software library will take care of scheduling.

POSIX Thread Standard

Some useful calls:

  • pthread_create: New thread
  • pthread_exit: Quite the calling thread
  • pthread_join: Wait for a thread to exit
  • pthread_yield: Give up CPU for another thread
  • pthread_attr_init: Create a thread attribute structure
  • pthread_attr_destroy: Remove a thread’s attribute structure

User Space Thread Implementation

If implemented in user space, then the library have to take care of scheduling and switching. However if hardware do support store/load registers, this operation can be done very quickly, which is much faster than trapping to kernel.

And since everything is local, no context switch is needed, no kernel calls, it is very fast. Each process can also have its own scheduling algorithm.

Drawbacks

Thread cannot make blocking kernel calls, since that will halt all threads. Sometimes library will wrap the actual system call, but it is not really that nice to do.

Another issue is page fault. Which will be discussed in memory management (basically blocking the process because it needs to read instructions from disk).

In user space thread implementations, there is no clock interrupts. So a thread must give up the CPU before another thread can be run.

Kernel Space Thread Implementation

CSCC69 Operating Systems - Processes

Overview

Processes allows computers to do multiple things at once.

In multiprogramming system, CPU switches from process to process very quickly, make it seem that it is running them concurrently. This is usually called pseudoparallelism, in contrast to real-parallelism with multiprocessor.

In any given instant, only one process is running on one CPU.

Context Switch: a context switch is the process of storing the state of a process or of a thread so that it can be restored and resumed later.

Drawbacks

  • Programs cannot have assumption of timing. Say if you know 1 loop takes 0.01 millisec, you loop 1000 times to get 10 millisec. However, while in the loop, OS might already switched to another process.

Program vs Process

An analogy:

  • Recepe: Program
  • Ingredients: Input Data
  • Process: Reading the recepe, getting ingredients and baking the cake.

Now the guy’s son runs into room and says he has been stung by a bee. The guy records where he was in the recipe, gets first aid book and following that. After first aid has been done, he goes back to cooking. This is basically how OS switches processes.

In real OS this is called scheduling. And if a programming is running twice, it is two processes.

Process Creation

There are 4 principal events that cause processes to be created:

  • System initialization
  • Execution of a process creation system call by a running process
  • A user request to create a new process
  • Initiation of a batch job

There are 2 main types: foreground and background (daemons).

Technically, for all these cases, a new process is created by an existing process. In UNIX, only fork can be used to create new processes. After fork, the child may change its memory image using execve. Reason is so we can redirect IO before execve.

Parent and child have different address space. However they may share text.

Process Termination

There are 4 ways for a process to terminate.

  • Normal exit
  • Error exit
  • Fatal error
  • Killed by another process

Process Hierarchies

In UNIX, a process and all of its children form a process group. When a user sends a signal from the keyboard, all members are notified.

In UNIX, all processes belong to a single tree, which init at the root. Processes cannot change parent (unless parent is killed by some reason).

Process States

There are 3 main states:

  • Running: Actually using the CPU
  • Ready: Can run, but temp stopped for another process to run
  • Blocked: Cannot run until some external event happens

In UNIX, a process is automatically blocked if trying to read from an empty pipe.

Process Implementation

People use process table (PCB) to implement processes. Usually a table includes:

  • State
  • Memory allocation
  • Open files
  • Scheduling info
  • Registers
  • etc.

Interrupt Vector

Usually located at the bottom of the memory, when an interrupt happens, the hardware pushes process info onto stack, and jumps to interrupt vector. Then the interrupt procedure runs.

All interrupts start by saving registers, this is usually done in assembly since C cannot access these information. Then the access is handed over to interrupt handler (stack is also reset).

After the handler is done, the control is back to assembly to load the registers again.

Overview of the basic procedures are listed below:

  • Hardware stacks basic program information
  • Hardware loads PC from IV.
  • Assembly saves registers
  • Assembly set up new stack.
  • Runs C interrupt service.
  • Scheduler decides which to run next.
  • C procedure returns to assembly code.
  • Assembly runs new process.

CSCB63 Data Structure Design and Analysis - Balanced Trees

Why balanced trees?

Binary tree: $O(n)$ for insert, delete and search.

CSCB63 Data Structure Design and Analysis - Complexity

Useful Manipulations

CSCC69 Operating Systems - Lecture 1

Operating System Boot Process

This is just a basic description of how a Pentium computer boots.

  • First the BIOS is loaded from motherboard RAM.
    • BIOS checks how much RAM is installed.
    • Other devices like keyboard / mouse are checked.
    • Then checks ISA and PCI busses.
  • BIOS then determines the boot device listed in CMOS memory.
    • Usually floppy -> CD -> HDD
  • The first sector of boot device is read and loaded
    • Examines the partition table at end of the boot sector, to determine which partition to use.
  • The boot loader is read from that partition.
    • Boot loader loads the OS

CSCB07 Software Design - Intro to Refactoring

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to refactoring.

CSCB07 Software Design - Decorator Pattern

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Decorator pattern.

CSCB07 Software Design - Pub/Sub Pattern

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Publish and Subscribe Pattern.

CSCB07 Software Design - Iterator and Builder Pattern

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Iterator and Builder design pattern.

CSCB07 Software Design - Unit Testing

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to JUnit.

CSCB07 Software Design - Polymorphism, Abstract Classes, Interfaces, Liskov, Singleton

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Polymorphism, Abstract Classes, Interfaces, Liskov, Singleton.

CSCB07 Software Design - More Java Memory Model

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

More topics on Java memory model.

CSCB07 Software Design - Software Development Process

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

CRC cards and how to properly develop software with a team.

How I Redesigned IFCAT

A good piece of code should look clean, concise and does what it is supposed to do.

I am not an expert in software engineering, but during my time contributing to IFCAT project, I did find some design flaws, and this is how I fixed them.

This post mainly serves as my personal reference in the future when I try to code Node.js systems. But also is a good read for anyone who is new to programming.

CSCB07 Software Design - Java Memory Model & CRC

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Java memory model and some CRC.

CSCB07 Software Design - Intro to Java

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Introduction to Java programming. This note assumes you are somewhat knows how to program, many obvious details are ignored.

CSCB07 Software Design - SVN

Course notes taken for CSCB07/CSC207 at UofT (Software Design).

Basic introduction to version control and how to use SVN.

CSCB36 Theory of Computation - Chapter 6 Predicate Logic

Notes taken for CSCB36 course at UofT, this post is for Chapter 6, Predicate Logic.

CSCB36 Theory of Computation - Chapter 5 Propositional Logic

Notes taken for CSCB36 course at UofT, this post is for Chapter 5, Propositional Logic.

CSCB36 Theory of Computation - Chapter 0

Notes taken for CSCB36 course at UofT, this post is for Chapter 0, mainly talks about sets and fundamental mathematical units.

MATA22 Linear Algebra - Diagonalization

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 5.2. For course MATA22 at UTSC.

CSCB09 Software Tools and Systems Programming - Advanced Topics

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Sockets

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Signals and Sockets

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Pipes / IPC

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Processes

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Misc IO

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Structs, Memory, Strings

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Intro to C

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Shell Programming

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

CSCB09 Software Tools and Systems Programming - Intro to UNIX

This article is mainly notes I have taken for CSCB09/CSC209 at UofT.

MATA22 Linear Algebra - Eigenvalues and Eigenvectors

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 5.1. For course MATA22 at UTSC.

MATA22 Linear Algebra - Determinants of a Square Matrix

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 4.2. For course MATA22 at UTSC.

MATA22 Linear Algebra - Determinants

This article is mainly notes I have taken from reading Linear Algebra (Addison-Wesley, 1995) section 4.1. For course MATA22 at UTSC.