Processes and Two's complement Arithmetic

Class: CSCE-313

Notes:

Two's Complement (8-bit Arithmetic)

Consider 2's complement representation of 8-bit numbers ranging from -128 ... +127. Answer the following questions:

Question 1

Given a positive number $0<u<128$, what is the decimal value of the unsigned number that represents $-u$.

Options:

• $255-u$
• $2^u-1$
• $256-u$ (correct)
• $128-u$

Overall explanation:

• We're working with 8-bit two's complement, since the range 0 < u < 128 fits nicely there.
  • In 8-bit arithmetic, values wrap modulo $2^8=256$
• In an 8-bit unsigned system, the possible values range from 0 to 255. When we represent negative numbers using Two's Complement, the bit pattern for $-u$ is mathematically equivalent to $2^n-u$, where $n$ is the number of bits.
  • To represent $-u$ as an unsigend number:
    • $-u\equiv 256-u(\mathrm{mod}256)$
• So the unsigned decimal value that corresponds to $-u$ is: $256-u$.

Tags: Bits and Bytes#Mapping Signed <-> Unsigned

Question 2

Show that $-(-u)=u$ in 2's complement arithmetic.

Answer:
The two's complement of a number $u$ for an $n$-bit system is defined as:

To get to $-(-u)$ we need to negate again:

Pushing the negative inside and simplifying:

Question 3

What is the negation of -128 in 8-bit 2's complement? Write a valid number in 8-bit 2's complement.

Let's apply the "invert and add 1" rule to -128:

1. Binary for -128: 1000 0000
2. Invert the bits: 0111 1111
3. Add 1: 1000 0000

The result is exactly what you started with: 1000 0000, which represents -128. This is known as an integer overflow.

Since the range is $[-128,127]$, any integer within that inclusive span is a valid number. Here are a few examples in both decimal and binary:

−128 is the only number in two’s complement whose negation equals itself due to overflow.

Answer: 100000

Question 4

Which operation is used to compute the two’s complement of a number?

Options:

• Flip all bits and add 1
• Flip all bits
• Shift left by one bit
• Add 1

Overall explanation:

• In two’s complement arithmetic, negating a number means:
  1. Flip (invert) all bits (one’s complement)
  2. Add 1
• That combination produces the two’s complement, which represents the negative of the original number.

Tags: Bits and Bytes

Two’s Complement Conversion

Convert the following decimal numbers to 8-bit 2's complement representation

Question 5

+42 =

1. Binary for +42: 0010 1010
   • For converting to binary: ${42}_{10}=32+8+2$
   • Since it's positive, no change needed.
   • Answer: 0010 1010

Question 6

-17 =

1. Binary for -17: 0001 0001
   • Note: ${17}_{10}=16+1$
2. Invert the bits: 1110 1110
3. Add 1: 1110 1111
   • Answer: 1110 1111

Overflow Conditions in Two’s Complement Addition

An overflow in 2's complement arithmetic means that the true result cannot be represented in the precision of the arithmetic. Note that this is not the same as carry resulting from the arithmetic. Although I didn't cover overflow in signed arithmetic in class, this is an opportunity to read up on it and understand the difference between overflow and carry in 2's complement arithmetic. Consider the 8-bit wheel in your class slides that shows all signed numbers representable in 8 bits.

Question 7

In 2's complement arithmetic, if you add two positive numbers and get a negative result, has overflow definitely occurred?

Options:

• No
• Yes

Overall explanation:

• In Two's complement arithmetic, overflow occurs when the result of an addition or subtraction falls outside the range of values that can be represented with the given number of bits.
  • Adding two positive numbers should always produce a positive result if no overflow occurs.
  • If the result comes out negative, the sign bit has flipped incorrectly.
• This can only happen due to overflow.

The Rules of Overflow
You can detect overflow easily by looking at the sign bits of the operands and the result:

Note: Overflow can never occur when adding a positive number and a negative number, because the sum will always be somewhere between the two original values, staying within the representable range.

Tags: Bits and Bytes

Question 8

If you add two negative numbers and get a positive result, has overflow definitely occurred.

Options:

• Yes
• No

Overall explanation:

• Just like adding two positive numbers and getting a negative result, adding two negative numbers and getting a positive result is a definitive sign of signed overflow.

Tags: Bits and Bytes

Question 9

You cannot have an overflow when you add a positive number to a negative number.

Options:

• True
• False

Overall explanation:

• Overflow occurs when the result of an operation is too large (either too positive or too negative) to fit into the allocated number of bits. When you add a positive number and a negative number, the two values effectively "cancel each other out" to some degree.
  1. If you add a positive number to a negative number, the sum will always be closer to zero than at least one of the original numbers.
  2. Since both original numbers were already within the representable range (e.g., $-128$ to $+127$ for 8-bit), a result that is "between" them or closer to zero is mathematically guaranteed to stay within that same range.
• Result always stays within the existing bounds.

Tags: Bits and Bytes

Processes & Interrupts

A process is an instance of a running program

• Started by system call `exec

Question 10

A user-level library implements each system call by executing a “transition to kernel mode” instruction followed by a procedure call to an appropriate system call handler in the kernel. To make this work, the user-level library must be built with access to a symbol table that contains the kernel addresses of each system call.

Options:

• True
• False

Overall explanation:

• The Interface (System Call Numbers): Instead of using memory addresses, the library uses a system call number. For example, on Linux, read might be 0 and write might be 1. The library places this number into a specific CPU register (like %eax or %rax) before triggering the transition.
• The Trap Table: When the "transition" instruction (like syscall, int 0x80, or sysenter) is executed, the CPU jumps to a fixed location in the kernel called the System Call Dispatcher or Trap Table. This table is set up by the kernel during boot.
• Kernel Isolation: For security and stability, user-level code is strictly prohibited from knowing or accessing kernel memory addresses. If a user library could jump directly to a kernel address, it would bypass the security checks that the hardware enforces during a proper mode switch.
  • User programs cannot directly call kernel procedures or know their addresses.

How the Process Actually Works

Tags: 02 - Architectural Support for Operating Systems#System calls example

Question 11

Describe what happens when an external hardware driven interrupt occurs?

1. The Interrupt Signal
   • The hardware device sends an electrical signal to a specialized chip called the Interrupt Controller (e.g., the APIC in modern systems). If the interrupt is not "masked" (ignored), the controller signals the CPU's interrupt pin.
2. Immediate Hardware Response
   • The CPU finishes the execution of the current instruction. Before starting the next one, it checks for pending interrupts. If one exists:
     • Mode Switch: The CPU automatically switches from User Mode to Kernel Mode.
     • State Saving: The hardware saves the current Program Counter (PC) and the Processor Status Word (PSW) onto the kernel stack so the CPU can eventually return to exactly where it left off.
3. The Interrupt Vector Table (IVT)
   • The CPU uses an Interrupt Vector (an index number) provided by the hardware to look up an address in the Interrupt Vector Table (or Interrupt Descriptor Table). This table contains the memory addresses of the various Interrupt Service Routines (ISRs).
4. Executing the ISR (The Handler)
   • The CPU jumps to the address found in the table and begins executing the Interrupt Service Routine.
     • Software State Saving: The ISR usually saves the rest of the registers (like %rax, %rbx, etc.) that the hardware didn't automatically save.
     • Servicing: The code interacts with the hardware device (e.g., moving data from the keyboard buffer into memory).
5. Resuming the Interrupted Process
   • Once the handler is finished:
     1. The ISR restores the saved registers from the stack.
     2. It executes a special instruction (like iret or "Interrupt Return").
     3. Restoration: This instruction pops the saved PSW and Program Counter back into the CPU registers.
     4. Mode Switch: The CPU switches back to User Mode and continues the original program as if nothing had happened.

Answer:
An external hardware interrupt occurs when a device signals the interrupt controller, which supplies an interrupt vector to the CPU. The CPU completes the current instruction, switches to kernel mode, saves its state, looks up the handler address in the interrupt vector table, and executes the corresponding interrupt service routine. After servicing the interrupt, the CPU restores its state and resumes execution.

Steps:

• A hardware device raises an interrupt signal
• The interrupt controller sends an interrupt number to the CPU
• The CPU finishes the current instruction
• The CPU switches to kernel mode and saves its state (pushes state onto the kernel stack)
• The CPU uses the interrupt number to find the handler in the interrupt vector table
• The CPU jumps to and executes the interrupt handler
• The handler finishes and returns from the interrupt
• The CPU restores state and resumes execution (pops saved CPU state)

Question 12

Which of the following best characterizes a process?

Options:

• A thread running inside a kernel
• A single function invocation
• A compiled binary stored on disk
• An executing program with its own address space and CPU state

Overall explanation:

• Executing Program: A process is "active." While a program is just a collection of instructions (code), a process is that code actually being run by the CPU.
• Address Space: Each process has its own private section of memory. This contains the code, global variables, the Heap (for dynamic memory), and the Stack (for local variables and function calls). One process generally cannot peek into the memory of another.
• CPU State: This includes the current values in the CPU registers and the Program Counter, which tracks which instruction is being executed next.

Tags: 02 - Architectural Support for Operating Systems

Question 13

Briefly explain why a single-core CPU can appear to run many processes simultaneously.

A single-core CPU creates the illusion of simultaneity through a technique called Context Switching (often referred to as Time Slicing).

Even though a single core can only execute one instruction at a time, it operates at incredibly high speeds—billions of cycles per second. The Operating System (OS) leverages this speed to manage multiple processes using the following mechanism:

• Time Slicing: The OS divides CPU time into tiny units called "quanta" (typically only a few milliseconds long). It allows Process A to run for one quantum, then forcibly pauses it.
• Context Switching: When a process is paused, the OS saves its "context"—the current values of the CPU registers, the Program Counter (where it left off in the code), and stack pointers—into a data structure called the Process Control Block (PCB).
• Rapid Rotation: The OS then loads the saved context of Process B and lets it run for the next quantum.
• The Illusion: Because these switches happen hundreds of times every second, they occur much faster than human perception can detect. To us, it appears as though the music player, the web browser, and the code editor are all running at the exact same moment.

This management is handled by the Scheduler, which is a core component of the OS kernel responsible for deciding which process gets the CPU next.

Answer:
A single-core CPU can look like it's running many processes at once because the OS quickly switches between them, this is called context switching and enables each process to get a small time slice on the CPU. The CPU is running and switching between processes so fast that, to any user, it appears that the computer is running all the programs simultaneously.

Tags: 01 - OS, Process, Multitasking, and Virtual Memory#Multitasking

Question 14

Each process has its own virtual address space. Which of the following statement(s) is/are true?

Options:

• Each process has its own page table mapping virtual to physical addresses
• Virtual addresses are identical to physical addresses on modern CPUs
• Two processes using the same virtual address must refer to the same physical memory
• Virtual memory prevents the kernel from accessing user memory

Overall explanation:

• To maintain isolation, the Operating System creates a unique Page Table for every process. This table acts as a "map." When Process A asks for memory at virtual address 0x4000, the CPU looks at Process A's table to find the physical location. When Process B asks for 0x4000, the CPU looks at Process B's table, which points to a completely different spot in the RAM.
• Why the other statements are False:
  • Virtual addresses are identical to physical addresses: On modern CPUs, this is almost never true. We use Virtual Addressing specifically to allow the OS to move data around in physical RAM without the program knowing. The only time they might be identical is in very simple embedded systems or during the very early stages of the computer's boot process.
  • Two processes using the same virtual address must refer to the same physical memory: This is the opposite of how it works. Because each process has its own map (Page Table), the virtual address 0x1234 in Process A and 0x1234 in Process B almost always point to different physical locations. This is why you can run two instances of the same program simultaneously without them overwriting each other's data.
  • Virtual memory prevents the kernel from accessing user memory: Actually, the kernel has "superpowers." While virtual memory prevents User Process A from accessing User Process B, the kernel usually has a mapping of all physical memory. The kernel must be able to access user memory to perform tasks like reading data from a disk into a user's buffer.

Tags: 01 - OS, Process, Multitasking, and Virtual Memory#Virtual Memory

x86-64 Privilege Levels and Protection

The x86-64 architecture supports multiple privilege levels (rings).

Question 15

Which ring is used for user programs?

Options:

• User programs run in Ring 0 so they can directly access hardware.
• All programs run in the same ring, and the OS enforces protection in software.
• User programs run in Ring 3, while the kernel runs in Ring 0 to enforce protection.
• Privilege levels exist only to improve performance, not security.

Overall explanation:

• The Ring Architecture
  • Ring 0 (Kernel Mode): This is the most privileged level. The Operating System kernel resides here. It has unrestricted access to the CPU's instruction set, all of physical memory, and direct control over hardware devices (like the disk, network card, and GPU).
  • Ring 1 & 2: Historically intended for device drivers or OS services, these are rarely used in modern operating systems like Windows, Linux, or macOS.
  • Ring 3 (User Mode): This is the least privileged level. Applications (web browsers, games, code editors) run here. They are restricted from executing "privileged instructions" (like shutting down the CPU) and cannot directly access hardware or memory outside their own virtual address space.
• Performance vs. Security: While privilege checks do have a minor performance cost, their primary purpose is strictly Security and Stability.

Tags: 02 - Architectural Support for Operating Systems#1. Privilege levels differentiate instruction sets

Question 16

Why are privileged instructions restricted to the kernel?

Options:

• To prevent user programs from directly controlling hardware and critical system state
• To allow user programs to execute faster
• To reduce the number of CPU rings used by the system
• To simplify compiler and linker design

Overall explanation:

• Privileged instructions are the "superpowers" of a CPU. If any program could execute them, the operating system would lose its ability to act as a manager and protector of the system.
• The Purpose of Restriction
  • If a user-level program (like a web browser) could execute privileged instructions, several critical safeguards would vanish:
    • System Stability: A program could accidentally (or intentionally) execute a HLT (halt) instruction, shutting down the entire CPU and crashing the computer for all users.
    • Memory Protection: A program could rewrite the Page Tables or the Interrupt Descriptor Table, allowing it to read your saved passwords in another process or intercept keystrokes.
    • Hardware Chaos: Multiple programs might try to send conflicting commands to the hard drive or network card simultaneously, leading to data corruption.
• How User Programs Get Work Done
  • Since they can't use these instructions, user programs use System Calls. This is like a citizen asking a government official to perform a task: the user program requests an action (like "write to file"), the CPU switches to the kernel (Ring 0), the kernel validates that the request is safe, performs the privileged instruction, and then returns control to the user.

Tags: 02 - Architectural Support for Operating Systems

Question 17

When a user program executes a system call on x86-64 Linux: Which of the following sequences is correct? On x86-64 with the syscall instruction, the processor does a fast transition into the kernel.

On entry (syscall), user places:

• syscall # in %rax and arguments in %rdi, %rsi, %rdx, %r10, %r8, %r9
• CPU saves user %rip in %rcx and %rflags in %r11

On return (sysret), kernel sets:

• %rip from %rcx
• %rflags from %r11

Options:

• User code → kernel jumps directly to device driver → returns
• User code → syscall → kernel handler → return via sysret
• User code → interrupt vector → BIOS → kernel
• User code → fork → kernel

Overall explanation:

• On x86-64 Linux, the syscall and sysret instructions were specifically designed to replace the older, slower interrupt-based methods (like int 0x80) with a "flat" and fast transition.
• How the Sequence Works
  1. User Code → syscall: The user-level library (like glibc) sets up the registers. As noted in the question, the system call number goes in %rax, and arguments go in the specified registers. When the syscall instruction is executed, the CPU immediately jumps to a predefined entry point in the kernel.
  2. State Saving: The CPU is "fast" because it doesn't push everything to the stack. Instead, it tucks the return address (%rip) into %rcx and the CPU flags (%rflags) into %r11.
  3. Kernel Handler: The kernel's entry point code (the "dispatcher") looks at %rax to see which function you want (e.g., read, write, open), checks your permissions, and executes the kernel-side code.
  4. Return via sysret: Once finished, the kernel places the result in %rax and executes sysret. This instruction automatically restores the instruction pointer from %rcx and flags from %r11, dropping the CPU back into Ring 3 (User Mode) to continue your program.
• Why the other options are incorrect:
  • Jumps directly to device driver: This would be a massive security hole. The kernel must first intercept the call, validate the arguments, and check permissions before ever talking to a device driver.
  • Interrupt vector → BIOS: The BIOS is involved in the very early stages of booting the computer. Once Linux is running, it handles its own system calls and interrupts; it does not hand control back to the BIOS for standard operations.
  • User code → fork → kernel: While fork() is a system call, it is just one specific example of a system call. It doesn't describe the general architectural sequence of how any system call moves from user space to kernel space.

Summary:

Tags: 02 - Architectural Support for Operating Systems#System calls an example in assembly