CSC 112: Module 1 - Operating Systems and Problem Solving Principles

Operating System Fundamentals

Definition of Operating System (OS): An operating system is defined as a set of computer programs designed to manage the hardware and software resources of a computer. It serves as the primary mechanism for maintaining a proper balance between software and hardware components.
Infrastructure Software Component: The OS is often referred to as the infrastructure software component because it is responsible for the management and coordination of activities, as well as the sharing of the computer's limited resources.
Host Functionality: The OS acts as a host for applications. By handling the low-level details of hardware operations, it relieves application programs from managing these complexities, thereby making it easier to write software.
Dual Perspectives on OS: * Resource Manager Point of View: The OS manages various parts of the system efficiently. * Extended Machines Point of View: The OS provides a virtual machine to the user that is more convenient to use than the raw hardware.
Basic Tasks: Key foundational tasks include: * Controlling and allocating memory. * Prioritizing system requests. * Controlling input and output devices. * Facilitating networking. * Managing file systems.
Popular Examples: Windows, Linux, and Mac OS represent some of the most widely used operating systems.

Objectives of Operating Systems

Modern operating systems are designed with three primary goals:

Goal 1: Hiding Hardware Details through Abstraction: * Abstraction Definition: This occurs when software hides lower-level details to provide a set of higher-level functions. The OS transforms physical devices, instructions, and memory into a virtual world of abstractions. * Reasons for Abstraction: 1. Device Control: Code for peripheral devices is not standardized. The OS provides subroutines called "device drivers" to perform I/O operations for programs. 2. New Functions: It introduces abstractions like "files" so programs do not have to deal with the specific physical mechanics of disks. 3. Virtualization: It transforms hardware into multiple virtual computers for different programs. Each running program is called a "process." 4. Security: Abstraction allows the OS to enforce security protocols.
Goal 2: Resource Allocation (Management): The OS acts as a controller that dictates how "processes" (active agents) access "resources" (passive entities).
Goal 3: User Interface Provisioning: The OS must provide a pleasant and effective interface. Users are primarily concerned with the "look and feel." * Core UI Components: Command interpreter, file system, on-line help, and application integration. * Current Trend: There is an increasing shift toward integrated graphical user interfaces (GUIs) that manage processes across networked computers.

Operating System Execution and Booting Process

Initial Power-On: When a computer is turned on, it runs a set of instructions stored in the Read-Only Memory (ROM).
Power-On Self Test (POST): This code checks the CPU, memory, and Basic Input-Output System (BIOS) for errors. Results are stored in a special memory location.
Activation: Once POST is complete, the software in ROM (BIOS or firmware) activates the disk drives.
The Bootstrap Loader: Found on the hard disk, the bootstrap loader is a small program that performs one function: loading the operating system into memory to begin operation. * It sets up small driver programs for hardware subsystems. * It defines divisions of memory for the OS, user info, and applications. * It establishes data structures for signals, flags, and semaphores used for inter-subsystem communication. * It eventually transfers control of the computer to the OS.

Classification of Operating Systems by Computer Type and Application

Real-Time Operating Systems (RTOS): Used to control machinery, scientific instruments, and industrial systems. * User Interface: Typically has very little UI capability and no end-user utilities; delivered as a "sealed box." * Time Consistency: Manages resources so specific operations execute in the exact same amount of time every time. * Catastrophic Failure: In complex machines, a part moving too quickly because resources are free can be as disastrous as not moving at all because the system is busy. * Hard RTOS: Guarantees critical tasks are performed on time. * Soft RTOS: Less restrictive; critical tasks get priority until completion.
Single-User, Single-Tasking OS: Designed for one user to do one thing at a time. Example: Palm OS for handheld computers.
Single-User, Multi-Tasking OS: The standard for modern desktops and laptops. It allows one user to run several programs simultaneously. Examples: Windows 98, Mac OS.
Multi-User OS: Allows many users to use computer resources simultaneously. * Requires balancing requirements so one user's problem does not affect others. * Examples: Unix, VMS, and Mainframe OS such as MVS. * Distinction: Systems like Windows 2000 or Novell Netware support thousands of networked users but are technically single-user systems where the administrator is the primary user, and remote logins are treated as programs run by the admin.

Classification of Operating Systems by Interaction Nature

Batch Processing OS: Users submit jobs to a central location where they are collected into a "batch" and placed in a queue. There is no user interaction during processing. Response time is defined as "turnaround time."
Time-Sharing OS: Provides services to many users concurrently on-line. Users share the CPU, memory, and resources under OS monitoring. There is full interaction with the program during execution, with response times typically within a few seconds.
Real-Time OS: Designed for applications where response time is critical to prevent error, misrepresentation, or disaster (e.g., airline reservations, nuclear power stations). These systems are designed to be interrupted by external signals requiring immediate attention.
Hybrid Systems: Many modern systems are hybrids, often running a background batch system alongside one of the other types.

System and Environment Based Definitions

Multiprogramming OS: Allows more than one active user program (or part of one) to be stored in main memory simultaneously. Note: A time-sharing system is a multiprogramming system, but the reverse is not always true.
Multiprocessing: A hardware configuration with more than one independent processing unit, typically used in major scientific or commercial complex environments.
Network Operating System: A collection of interconnected physical computers. The OS includes provisions for communication and data transfer between machines. Users are aware of multiple computers and can log in remotely. The essential structure is similar to single-processor systems but includes network interface controllers and remote access programs.
Distributed Operating System: Multiple connected computers managed to automatically share job loads. To the user, it appears as a traditional "uniprocessor" system. Users should not be aware of where programs are run or where files are located; the OS handles this automatically.

Functions and Vulnerabilities of Operating Systems

Major Functions: * Processor Management: Assigning the processor to different tasks. * Memory Management: Allocating main memory and storage to system/user programs. * Input/Output Management: Coordinating and assigning I/O devices during execution. * File Management: Storing and modifying files across various storage devices.
Secondary Functions: * Establishing priority systems for job execution. * Automatic transition between jobs. * Command and instruction interpretation. * Coordinating compilers, assemblers, and utility programs. * Facilitating human-computer communication and ensuring data security/integrity.
OS Flaws: OS code is written by humans and contains errors (bugs): * System Crashes/Instability: The system freezes or becomes unresponsive, requiring a reboot. * Security Flaws: Errors that allow unauthorized intruders to gain illegal access. These require "patching." * Peripheral Errors: Failures in communicating with devices like printers.

Foundations of Problem Solving

Definition of Problem: A gap between the current state and the desired state. Problem-solving is "knowing what to do when you don't know what to do."
Problem-Solving Strategy: A plan used to find a solution or overcome a challenge, such as "trial and error."
Problem Categories: * Ill-defined Problems: Issues without clear goals, solution paths, or expected outcomes. * Well-defined Problems: Issues with specific goals, clearly defined solutions, and clear expected outcomes.
Problem Identification Steps: 1. Recognize: Notice the gap between current and desired states. 2. Define: Articulate the nature and impact of the problem. 3. Gather Information: Collect relevant data. 4. Analyze: Break the problem into parts to find root causes. 5. Problem Statement: Create a concise description.

The 7-Step Problem-Solving Process

Acknowledge the Problem: Stop and think when motivation drops or a challenge arises.
Identify the Root and Define: Identify essential elements. "A problem well-stated is a problem half-solved."
Transform into a Goal: Select relevant information to solve the problem.
Generate and Evaluate Solutions: Use brainstorming rules: * Think of many ideas. * Use imagination. * Write everything down without criticism. * Improve on others' ideas.
Prioritize Solutions: Consider constraints like time, money, and policy.
Implement the Solution: Create a step-by-step plan.
Assess and Evaluate: Re-evaluate if the problem was solved; if not, determine why and what to do differently.

Routine vs. Non-Routine Problem Solving

Routine Problems: Repetitive issues with known solutions and established procedures (SOPs). * Examples: Fixing a paper jam, processing payroll, customer inquiries. * Arithmetic Context: Often involves the four operations or ratio. Success depends on knowing what arithmetic to do, not just doing calculation. * Research Anecdote: A boy solved routine problems by subtracting if two numbers were big, and dividing if one was large and one small. While he was successful in school, this showed a lack of conceptual understanding. * Fermi Problems: Special routine problems requiring estimation of unknown/unknowable values. Example: "How many cars are there in Manitoba?" Success is measured by the justification and the reasoning of the estimate.
Non-Routine Problems: Unique, unfamiliar issues without predefined solution paths. They foster mathematical reasoning and creativity. * Heuristics: Strategies used to discover solutions (e.g., "I tried this and that, then eureka!"). * Stubborn Numbers Example: Pairing numbers like $35$ and $41$ , where digits reappear in the product ( $35 \times 41 = 1435$ ). There are 6 such pairs in all. * Non-Routine Strategies: * Look for a pattern. * Guess and check. * Make/solve a simpler problem. * Work backwards. * Act it out/make a model. * Break the problem into smaller parts.

Computing Problem-Solving: Algorithms vs. Heuristics

Algorithm: A precise set of rules or step-by-step instructions (a formula) used to achieve a desired outcome. They guarantee a correct answer and do not rely on guesses.
Heuristics: Problem-solving techniques used when classical approaches are too time-consuming. They rely on exploration, intuition, and educated guesses. * Trade-off: Precision vs. Speed. Heuristics yield acceptable solutions quickly but not necessarily the best ones. * Conditions for Heuristic Use: Too much info, limited time, unimportant decision, very little info, or an intuitive thought occurs.
Applications of Heuristics: * Traveling Salesperson Problem (TSP): Approximating the shortest route visiting several cities. * Greedy Algorithms: Finding locally optimal choices to reach a global optimum. * Antivirus Software: Searching for code samples that resemble viruses to reduce file search volume.
Comparison Table:

Feature	Heuristic	Algorithm
Basis	Intuition, guesses, exploration	Finite set of instructions
Result	Usually sub-optimal	Guaranteed optimal
Proof	Cannot be proven mathematically	Can be mathematically proven
Consistency	Not reproducible (varies)	reproducible (same every time)

Solvable and Unsolvable Problems

Solvable Problems: A solution (algorithm or procedure) exists to find the answer in a finite amount of time, or it is mathematically proven that no solution exists. Examples: Sorting (QuickSort), Searching (Binary Search), and GCD calculations.
Unsolvable (Undecidable) Problems: Problems where no algorithm can provide a solution for all possible inputs. They occupy a "temporary status" where we are neither able to solve nor prove they cannot be solved. * The Halting Problem: Determining if a program will halt or run forever. * Entscheidungsproblem: Determining the universal validity of a statement in first-order logic.
Decidable vs. Undecidable: * Decidable: Includes both algorithms (known time) and procedures (step-by-step). * Undecidable: A procedure exists, but the complexity prevents predicting the approximate time for a solution.

Specialized Problem-Solving Techniques

Abstraction: Solving within a model before applying to reality.
Analogy: Using parallel solutions from similar past problems.
Brainstorming: Group-based idea generation without judgment.
Trial and Error: Ruling out options until one works.
Hypothesis Testing: Formulating assumptions and analyzing manipulated variables.
Reduction: Breaking complex problems into simpler sub-problems.
Literal Thinking: Focusing on exact meanings without abstract interpretation.
Means-End Analysis: Reducing the difference between current and goal states using small steps. * Tower of Hanoi Paradigm: Moving a stack of disks between rods with specific rules. Minimal moves formula: $2^n - 1$ . For 14 disks, moves = $2^{14} - 1 = 16,383$ .
Method of Focal Object: Combining non-matching characteristics to innovate.
Morphological Analysis: Systematically varying parameters across a whole system.
Research: Gathering existing knowledge from various sources.
Root Cause Analysis (5 Whys): Identifying the underlying cause rather than symptoms.
Proof: Using logical reasoning or mathematical induction to show a solution is correct or that a problem is unsolvable.
Divide and Conquer: Splitting a problem into independent parts (e.g., Merge Sort).

Algorithm Development: Flowcharts vs. Pseudocode

Computational Model Example: Calculating average grades. * Input: Grades (numeric or letter). * Process: Summation and division. * Output: Monitor, printer, or storage.
Formulating the Model: * Numeric format: $Average_1 = \frac{x_1 + x_2 + \dots + x_n}{n}$ . * Letter format: Requires a mapping (e.g., $A+ = 12$ , $F = 0$ ). $Average_2 = \frac{y_1 + y_2 + \dots + y_n}{n}$ .
Algorithm Representation: * Flowchart: Visually mapping steps with geometric shapes. * Pseudocode: A concise sequence of English-like instructions. * Sequence: Step-by-step numbering. * Condition: "If… then… else" structures. * Repetition: "Repeat… until" or "Repeat X times." * Storage: Assigning values to variables (e.g., $x \leftarrow \text{a new bulb}$ ). * Transfer of Control: Using "goto" statements.

Program Implementation and Debugging

Coding: Transforming an algorithm into instructions the computer understands.
Compiling: Converting code into computer-readable instructions. Errors at this stage are "compile-time errors."
Bugs: Errors that cause a program to stop working or produce incorrect results.
Testing: Running the program with a "test suite" (multiple test cases) to ensure accuracy across all situations.
Debugging: The time-consuming process of finding and fixing errors in code.

Python Programming Language Overview

Characteristics: High-level, interpreted, interactive, object-oriented, open-source, and cross-platform.
Design Philosophy (Zen of Python): Emphasizes simplicity, readability, and unambiguity. Key aphorisms include "Beautiful is better than ugly" and "Simple is better than complex."
Pythonic Style: Code that is clean, simple, beautiful, explicit, and readable.
Applications: Web development, data science, AI, ML, automation, and games.
Major Versions: * 0.9.0 (1991): First version; included classes, inheritance, and exception handling. * 1.0 (1994): Functional programming tools and complex number support. * 2.0 (2000): Garbage collection and Unicode support. Dominant for a decade. * 3.0 (2008): Complete revamp to remove discrepancies. Improved integer division and syntax. * 3.11 (Current Stable): Up to 60% faster than previous versions; better exception messaging.
Variables and Operators: * Assignment Operator (=): Assigns the value on the right to the name on the left. * Case Sensitivity: greeting is different from Greeting. * Naming Rules: Must contain A-Z, 0-9, or underscores; cannot start with a digit. * Naming Conventions (PEP 8): Python uses lower_case_with_underscores for variables (vs. mixedCase used in other languages).
Comments: * Block Comments: Start with # on a new line. * Inline Comments: Appear on the same line as code after #. * Commenting Out: Temporarily disabling code during testing using #.