Operating Systems

\[B2U_w(\overrightarrow{x})-B2T_w(\overrightarrow{x})=x_{w-1}(2^{w-1}+2^{w-1})=x_{w-1}2^w\] \[B2U_w(\overrightarrow{x})=x_{w-1}2^w + B2T_w(\overrightarrow{x})\] Let \(\overrightarrow{x}=T2B_w(x)\) , Then: \[T2U_w(x)=B2U_w(T2B_w(x)) = x_{w-1}2^w + B2T_w(T2B_w(x)) = x_{w-1}2^w + x\]

\[B2S_w(\overrightarrow{x})\doteq(-1)^{x_{w-1}}\cdot(\dots)\]

\[d=\sum_{i=-n}^m10^i\times{d_i}\] Consider Fractional decimal \(12.34_{10}\) \[ 1\times{10^1} + 2\times{10^0} + 3\times{10^{-1}} + 4\times{10^{-2}}=12\frac{34}{100}\]

\[b=\sum_{i=-n}^m2^i\times{b_i}\] eg: \(101.11_2\) \[ 1\times{2^2} + 0\times{2^1} + 1\times{2^0} + 1\times{2^{-1}} + 1\times{2^{-2}} = 5\frac{3}{4}\]

s=1, k=8, n=23 yielding a 32-bit representation, Bias = 127

s=1, k=11, n=52, yielding a 64-bit representation, Bias = 1023

Condition: exp is not all zeros(0) & not all ones(255 for single, 2047 for double)

\(E = e - Bias\), e is the unsigned number, Hance, the range of \(E\) is

• \(-126\leq{E}\leq{+127}\) for single
• \(-1022\leq{E}\leq{+1023}\) for double

\(M=1+f\) where \(0\leq{f}<1\) having binary representation \(0.f_{n-1}...f_1f_0\) so that, M is in the range \(1\leq{M}<2\) This implied leading 1 is a trick for getting an additional bit of precision for free.

Condition: exp is all zeros

Serve two purposes:

• represent 0 (all bits are zero)
• represent numbers that are very close to 0.0

Condition: exp is all ones

• infinity

  s

  all 1

  0

• NaN

  s

  all 1

  \(\ne 0\)

8-bit floating-point format

1. complement the bits
2. increment by 1

Condition: \(x\neq 0\)

1. Split the bit vector into two parts.(the boundary is the rightmost 1)
2. Complement each bit on the left part.

\[(x << n) + (x << n-1) + \dots + (x << m)\] \[(x << n+1) - (x << m)\]

• eg: \(14\) can be rewrite as \((x<<4) - (x<<1)\) or \((x<<3) + (x<<2) + (x<<1)\)

Assuming additions and subtractions have comparable cost, then we have:

• \(n = m\) , use Form1.
• \(n = m+1\) , use either Form1 or Form2.
• \(n > m+1\) , use Form2.

\(x \div 2^k = x>>k\) where \(0 \le{k} < w\) and \(x\ge 0\)

\(x \div 2^k = x>>k\) where \(0\le{k} < w\) Follow the above, we'll find -7/2 yield -4 not -3, corrected by 'biasing' the value before shifting.

• \(x \div 2^k = (x+ 2^k - 1) >> k\) where \(x < 0\)

• ZeroExtend

  MOVZ S, R

  R← ZeroExtend(S)

  eg: movzbl, movzbw, movzwl, movzbq, movzwq

• SignExtend

  MOVS S, R

  R← SignExtend(S)

  eg: movsbw, movsbl, movswl, movsbq, movswq, movslq, cltq

  • cltq: %rax \(\leftarrow\) SignExtend(%eax)

pushq S

1. R[%rsp] \(\leftarrow\) R[%rsp] - 8
2. M[R[%rsp]] \(\leftarrow\) S

subq $8,%rsp // Decrement stack pointer
movq %rbp,(%rsp) //Store %rbp on stack

popq D

1. D \(\leftarrow\) M[R[%rsp]]
2. R[%rsp] \(\leftarrow\) R[%rsp + 8]

movq (%rsp),%rax //Read %rax from stack
addl $4,%esp  //Increment stack pointer

• Example: For t=a+b,

  CF	(unsigned)t < (unsigned)a	Unsigned Overflow
  ZF	(t == 0)	Zero
  SF	(t < 0)	Negative
  OF	(a<0 = b<0)&&(t<0 ! a<0)	Signed Overflow

These two instructions that set the condiction code without updating their destination.

• set directly

  Instruction	Synonym	Effect	Set condition
  sete D	setz	D <- ZF	Equal/zero
  setne D	setnz	D <- ~ZF	Not Equal/not zero
  sets D		D <- SF	Negative
  setns D		D <- ~SF	Nonnegative

• signed group

  setg D	setnle	D <- ~(SF^OF) & ~ZF	>
  setge D	setnl	D <- ~(SF^OF)	>=
  setl D	setnge	D <- SF^OF	<
  setle D	setnge	D <- (SF^OF) | ZF	<=

• unsigned group

  seta D	setnbe	D <- ~CF & ~ZF	>
  setae D	setnb	D <- ~CF	>=
  setb D	setnae	D <- CF	<
  setbe D	setna	D <- CF | ZF	<=

• jump

  Instruction	Synonym	Condition
  jmp Label	direct jump	1
  jmp *Operand	indirect jump	1
  je L	jz	ZF
  jne L	jnz	~ZF
  js L		SF
  jns L		~SF

• signed group

  jg L	jnle	~(SF^OF)&~ZF	>
  jge L	jnl	~(SF^OF)	>=
  jl L	jnge	SF^OF	<
  jle L	jng	(SF^OF)|ZF	<=

• unsigned group

  ja L	jnbe	~CF & ~ZF	>
  jae L	jnb	~CF	>=
  jb L	jnae	CF	<
  jbe L	jna	CF|ZF	<=

• General in C

  if (test-expr)
     then-statement
  else
     else-statement
  

• normal form with goto statement

      t = test-expr;
      if (t)
         goto true;
      else-statement
      goto done;
  true:
      then-statement
  done:
  

• assembly form

      t = test-expr;
      if (!t)
         goto false-label;
      then-statement
      goto done;
  false-label:
      else-statement
  done:
  

• when there is no else-statement.

      t = test-expr;
      if (!t)
         goto done;
      then-statement
  done:
  

v = test-expr ? then-expr : else-expr;

• standard form

      if (!test-expr)
  	goto false;
      v = then-expr;
      goto done;
  false:
      v = else-expr;
  done:
  

• more abstract form

  vt = then-expr;
  v = else-expr;
  t = test-expr;
  if (t) v = vt;
  

do
    body-statement
while (test-expr)

• goto version

  loop:
      body-statement
      t = test-expr;
      if (t)
         goto loop;
  done:
  

while (test-expr)
    body-statement

• goto version

  t = test-expr
  if (!t)
     goto done;
  loop:
     body-statement
     if (t)
        goto loop;
  done:
  

for (init-expr; test-expr; update-expr)
    body-statement

• Equivalent to while loop

  init-expr;
  while (test-expr)
      body-statement
      update-expr;
  

• goto vesion:

  init-expr;
  t = test-expr;
  if (!t)
     goto done;
  
  loop:
     body-statement
     update-expr;
     if (t)
        goto loop;
  done:
  

Compilers uses the jump table to achieve conditional jumping. Think of jump table as an array of function pointers.

switch (n) {
  case 100:
    ...;
    break;
  case 102:
    ...;
    break;
  case 103:
    ...;
    break;
  case 105:
    ...;
    break;
  default:
    break;
}

• impl

  loc_A:
    ...
  loc_B:
    ...
  ...
  
  static void *jt[5] = {
    &&loc_A, &&Loc_B, &&loc_C, &&loc_def, &&loc_D
  };
  unsigned long index = n-100;
  if (index > 4)
    goto loc_def;
  goto *it[index];
  
  

• jump table in asm

    .section .rodata
    .align 8 // Align address to multiple of 8
  .L4:
    .quad .L3 // case 100: loc_A
    .quad .L8 // case 101: default
    .quad .L5 // case 102: loc_B
    .quda .L6 // case 103: loc_C
    .quda .L7 // case 105: loc_D
    .quda .L8 // default
  

<before>%rip(PC counter): 0x400563, %rsp: 0x7fffffffe840

1. push a return address on the P's stack
2. set %rip to the start of Q

<after>%rip: 0x400540, %rsp: 0x7fffffffe838(-8bytes)

1. pop value from return address

<after>%rip: 0x400568, %rsp: 0x7fffffffe840

• use 0x8(%rsp) to access return value from callee.

Misprediction incurs a significant cost in performance

Instruction decoding logic takes the actual program instructions and converts them into a set of primitive operations

addq %rax, 8(%rdx)

yields multiple operations, separating the memory references from the arithmetic operations.

The EU receives operations from the instruction fetch unit. Operations are dispatched to a set of functional units that perform the actual operations.

The retirement unit keeps track of the ongoing processing and makes sure that it obeys the sequential semantics of the machine-level program.

• once the operations for the instruction have completed and any branch points

leading to this instruction are confirmed as having been correctly predicted, the instruction can be retired

• If some branch point leading to this instruction was mispredicted, the instruction

will be flushed, discarding any results that may have been computed.

the execution units can send results directly to each other.

• The most common mechanism for controlling the communication of operands

among the execution units is called register renaming

• Latency: the total time required to perform the operation
• Issue time: the minimum number of clock cycles between two successive operations of the same type

• Functional units with issue times of 1 cycle are said to be fully pipelined
• Thoughput: \(\frac{number\ of\ function\ unit}{issue\ time}\) cycles per operation

Branch prediction is only reliable for regular patterns.

Principles to avoid branch misprediction penalties

• Do not be overly concerned about predictable branches

• Write code suitable for implementation with conditional moves (depends on compiler, write and check asm)

  for (i = 0; i < N; ++i) {
    if (a < b)
      min = b; // not predictable, cost of misprediction penalties is high
  }
  
  for (i = 0; i < N; ++i) {
    min = a < b ? a : b; // CPE is steady
  }
  

Depends on the pipelining capability and the latency of the load unit.

The store operation can operate in a fully pipelined mode, beginning a new store on every cycle. Because the store operation does not affect any register values.

• interaction with load operation

The load operation will check the entries in the store buffer for matching addresses. If it finds a match, it retrieves the corresponding data entry as the result of the load operation.

When the load and store addresses match, these two operations can't be parallelized.

• d supercells
• w DRAM cells in each supercell
• A \(d\times w\) DRAM stores dw bits of information

• RAS: Row Access Strobe
• CAS: Column Access Strobe
• Use internal row buffer to cache

To retrieve a 64-bit doubleword at memory address A, the memory controller converts A to a supercell address (i, j ) and sends it to the memory module, which then broadcasts i and j to each DRAM. In response, each DRAM outputs the 8- bit contents of its (i, j ) supercell. Circuitry in the module collects these outputs and forms them into a 64-bit doubleword, which it returns to the memory controller.

Fast page mode DRAM, allowing consecutive accesses to the same row to be served directly from the row buffer

Extended data out DRAM, allows the individual CAS signals to be spaced closer together in time.

Synchronous DRAM, SDRAM can output the contents of its supercells at a faster rate than its asynchronous counterparts(FPM DRAM & EDO DRAM).

An enhancement of SDRAM that doubles the speed of the DRAM by using both clock edges as control signals. Different types of DDR SDRAMs are characterized by the size of a small prefetch buffer that increases the effective bandwidth: DDR (2 bits), DDR2 (4 bits), and DDR3 (8 bits).

Used in the frame buffers of graphics systems. VRAM is similar in spirit to FPM DRAM. Differences are: 1) VRAM output is produced by shifting the entire contents of the internal buffer in sequence 2) VRAM allows concurrent reads and writes to the memory.

• recording density: bits/inch
• track density: tracks/inch
• areal density: \(recording\times track\)

\[Capacity=\frac{\#\ bytes}{sector}\times\frac{average\ \#\ sectors}{track}\times\frac{\#\ track}{surface}\times\frac{\#\ surfaces}{platter}\times\frac{\#\ platters}{disk}\]

The access time for a sector has three main components

• seek time avg 3~9ms (seek track)
• rotational latency (seek sector)

\[T_{max}=\frac{1}{RPM}\ minutes\] \[T_{avg}=\frac{T_{max}}{2}\ minutes\]

• transfer time

\[T{avg}=\frac{1}{RPM}\times\frac{1}{avg\ \#\ sectors/track}\ minutes\]

• number of blocks is equal to number of sectors, numbered 0, 1, …, B-1
• A firmware device in the disk, called the disk controller,

maintains the mapping between logical block numbers and actual (physical) disk sectors.

Uses a technique called memory-mapped I/O. In a system with memory-mapped I/O, a block of addresses in the address space is reserved for communicating with I/O devices. Each of these addresses is known as an I/O port. Each device is mapped to one or more I/O ports when it is attached to the bus.

e.g. Reading from disk. Suppose that the disk controller is mapped to port 0xa0

1. sends a command word that tells the disk to initiate a read
2. indicates the logical block number that should be read
3. indicates the main memory address where the contents of the disk sector should be stored.

Disk controller finishes the direct memory access(DMA) transfer, then notify CPU the I/O is done.

Based on flash memory

• flash translation layer: plays the same role as a disk controller (translating blocks)
• B blocks
• Each block consists of P pages
• Data is read and written in units of pages

Randomly placed blocks are expensive to locate. Restricts a particular block at level k+1 to a small subset of the blocks at level k.

• random replacement policy
• least-recently used(LRU)

• cold miss(compulsory miss): miss on cold cache(empty cache)
• conflict miss: placement policy lead to conflict miss
• capacity miss: when the size of the working set exceeds the size of the cache

• write-through: immediately write w’s cache block to the next lower level
• write-back: updated block to the low level when it is evicted from the cache

by the replacement algorithm. Maintains an additional dirty(modify) bit for each cache line.

• write-allocate: loads the corresponding block from the lower level into the cache

and then updates the cache block

• not-write-allocate

• Miss rate: \(\frac{\#\ misses}{\#\ references}\)
• Hit rate: \(1-Miss\ rate\)
• Hit time: the time to deliver a word in the cache to the CPU
• Miss penaly: any additional time required because of a miss

• Cache size
• Block size: The larger blocks can help increase the hit rate by exploiting any spatial locality, but expensive
• Associativity(E): The larger E decreases the vulnerability of the cache to thrashing due to conflict misses

Describes the word size and byte ordering of the system that generated the file

The machine code of the compiled program.

Read-only data such as the format strings in printf statements, and jump tables for switch statements

Initialized global C variables.

Uninitialized global C variables.

A symbol table with information about functions and global variables that are defined and referenced in the program.

A list of locations in the .text section that will need to be modified when the linker combines this object file with others.

Relocation information for any global variables that are referenced or defined by the module.

A debugging symbol table with entries for local variables and typedefs defined in the program.

A mapping between line numbers in the original C source program and machine code instructions in the .text section.(-g only)

A string table for the symbol tables in the .symtab and .debug sections, and for the section names in the section headers.

The ELF header describes the overall format of the file. It also includes the program’s entry point

.init section defines a small function, called _init, that will be called by the program’s initialization code.

Map contiguous chunks of the executable file to contiguous memory segments. See Program Header displayed by objdump

• off: file offset
• vaddr\/paddr: vitual\/physical address
• align: segment alignment
• filesz: segment size in the object file
• memsz: segment size in memory
• flags: run-time permissions

Some local linker symbols correspond to C functions and global variables that are defined with the static attribute. These symbols are visible anywhere within module m, but cannot be referenced by other modules.

Compile with -I. to search current directory first

gcc -W1,--wrap,func1 -o prog xxx.o xxx.o

-W1,--wrap,func1: gcc transform --wrap malloc to linker

Uses LD_PRELOAD environment variable

LD_PRELOAD="./wrapper.so" ./prog

• R_X86_64_PC32: Relocate a reference that uses a 32-bit PC-relative address
• R_X86_64_32: Relocate a reference that uses a 32-bit absolute address

Defers the binding of procedure addresses until the first time the procedure is called.

If an object module calls any functions that are defined in shared libraries, then it has its own GOT and PLT. The PLT is part of the .text section

• child gets an identical (but separate) copy of the parent’s user-level virtual

address space, including the text, data, and bss segments, heap, user stack, and identical copies of any of the parent’s open file descriptors.

• Call once, return twice. Return child pid in parent process, return 0 in child process.

suspends execution of the calling process until a child process in its wait set terminates.(default)

Arguments:

• pid=-1: the wait set consists of all of the parent’s child processes.

The execve function loads and runs a new program in the context of the current process. It overwrites the address space of the current process, it does not create a new process. The new program still has the same PID, and it inherits all of the file descriptors that were open at the time of the call to the execve function.

The setjmp function saves the current calling environment in the env buffer, for later use by longjmp, and returns a 0.

The longjmp function restores the calling environment from the env buffer and then triggers a return from the most recent setjmp call that initialized env. The setjmp then returns with the nonzero return value retval.

The pthread_once function is useful whenever you need to dynamically initialize global variables that are shared by multiple threads.

• Only the first call to pthread_once invokes init_routine

• implicitly terminates when its top-level thread routine returns
• call pthread_exit function
• calls the Unix exit function, which terminates the process

and all threads associated with the process.

• another thread calls pthread_cancel to terminate current thread

Threads wait for other threads to terminate by calling the pthread_join function. The once_control variable is a global or static variable that is always initialized to PTHREAD_ONCE_INIT.

At any point in time, a thread is joinable or detached. A detached thread cannot be reaped or killed by other threads. A joinable thread's memory resources are not freed until it is reaped by another thread or detached by a call to the pthread_detach function

If s is nonzero, then P decrements s and returns immediately(atomic). If s is zero, then suspend the thread until s becomes nonzero and the process is restarted by a V operation. After restarting, the P operation decrements s and returns control to the caller.

The V operation increments s by 1(atomic). If there are any threads blocked at a P operation waiting for s to become nonzero, then the V operation restarts exactly one of these threads, which then completes its P operation by decrementing s.

#include <semaphore.h>

int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */

• pshared: be shared between the threads, or between processes