Real Time Systems, Distributed Systems, Cloud Computing

1

A real-time system's correctness depends not only on the logical correctness of a computation's result but also on the time at which that result is produced — results delivered too late are considered wrong.

2

Typical real-time applications include digital control (e.g. aircraft autopilot), high-level industrial process control, and signal processing (e.g. radar, audio/video processing).

3

Release time is when a task becomes ready to execute; the deadline is the time by which it must complete; together with other requirements these form a task's timing constraints.

4

Hard real-time systems treat a missed deadline as a catastrophic failure (e.g. flight control, pacemaker systems) and require guaranteed worst-case timing analysis, whereas soft real-time systems (e.g. video streaming, online transaction processing) only degrade in quality when a deadline is missed, and statistical/average-case timing is often acceptable.

5

The reference model for real-time systems covers processors and resources (CPUs, memory, I/O, network) that execute and support real-time tasks.

6

Temporal parameters of a real-time workload include release time, deadline, execution time, and (for repeating tasks) the period.

7

The periodic task model models tasks that repeat at fixed intervals (periods), each instance having its own release time and deadline; precedence constraints require some tasks to execute in a specific order due to data dependency between them.

8

Clock-driven (time-driven) scheduling makes decisions at predetermined time points, following a static schedule usually computed offline.

9

Weighted Round-Robin is a round-robin variant that allocates more CPU time slices to tasks with higher assigned weights.

10

Priority-driven scheduling makes decisions whenever a scheduling event occurs (task arrival/completion), based on priorities that may be fixed or dynamic; static systems have all scheduling information known in advance with schedules computed offline, while dynamic systems decide at run time using currently available information.

11

EDF (Earliest-Deadline-First) is a dynamic-priority algorithm that gives the highest priority to the task with the nearest absolute deadline; it is optimal among all scheduling algorithms for uniprocessor preemptive scheduling, able to achieve up to 100% CPU utilization.

12

LST (Least-Slack-Time-first) is dynamic, prioritizing the task with the least slack (deadline − remaining execution time − current time); it is also optimal but has higher run-time overhead than EDF since remaining execution time must be tracked.

13

Rate Monotonic (RM) uses fixed priority, giving shorter-period tasks higher priority; it is optimal among fixed-priority algorithms for periodic tasks.

14

Offline scheduling computes the complete schedule in advance and stores it (table-driven); online scheduling decides at run time as tasks arrive. Aperiodic jobs arrive unpredictably with typically no hard deadline; sporadic jobs arrive unpredictably but have both a hard deadline and a minimum inter-arrival time; special mechanisms (background, polling, deferrable servers) accommodate them.

1

Resource contention arises when multiple tasks compete for the same shared resource; a lower-priority task holding a resource can block a higher-priority task, causing priority inversion.

2

Resource Access Control (RAC) protocols govern how tasks access shared resources, aiming to bound blocking time and avoid deadlock.

3

Non-preemptive critical sections are the simplest RAC approach: once a task enters a critical section it cannot be preempted until it exits — simple, but can cause excessive blocking of high-priority tasks.

4

The Basic Priority-Inheritance Protocol: when a higher-priority task is blocked waiting for a resource held by a lower-priority task, the lower-priority task temporarily inherits the higher priority, reducing blocking time.

5

The Priority-Ceiling Protocol (PCP) assigns each resource a ceiling priority (the highest priority of any task that may lock it); a task can enter a new critical section only if its priority exceeds the ceilings of all currently locked resources — this prevents deadlock and bounds blocking to at most one critical section.

6

The Stack-Based Priority-Ceiling Protocol is a variant of PCP suited to fixed-priority systems using a single shared run-time stack, simplifying implementation.

7

PCP has adaptations for dynamic-priority systems (e.g. a Dynamic Priority-Ceiling Protocol) for systems scheduled with EDF or LST rather than fixed priorities.

8

The Preemption Ceiling Protocol generalizes the ceiling concept using preemption thresholds to bound priority inversion across various scheduling contexts.

9

Access control in multiple-module resources extends RAC protocols to resources made up of several independently accessible modules/segments; controlling concurrent access to data objects uses locks/semaphores together with RAC protocols to keep shared data consistent.

10

Real-time communication transmits data across a network within specified timing constraints — essential in distributed real-time systems such as sensor and control networks.

11

Hard real-time communication guarantees message delivery within a deadline, while soft real-time communication offers only best-effort delivery with statistical guarantees.

12

A model of real-time communication characterizes message streams using parameters such as period, deadline, and message size — mirroring the periodic task model used for CPU scheduling.

13

Priority-based service and Weighted Round-Robin (WRR) service disciplines for switched networks either prioritize time-critical messages outright or fairly share bandwidth according to assigned weights.

14

Medium Access Control (MAC) protocols for broadcast networks (e.g. TDMA, CSMA/CD, token passing) govern how nodes share a common transmission medium, bounding access delay; RSVP (Resource Reservation Protocol) reserves bandwidth/resources along a network path to provide QoS guarantees for real-time traffic over IP networks.

1

A distributed system is a collection of independent computers that appears to its users as a single coherent system, coordinating via message passing over a network.

2

Characteristics of distributed systems: resource sharing, concurrency, scalability, fault tolerance, and various forms of transparency (access, location, concurrency, replication transparency); there is also typically no global clock.

3

Advantages of distributed systems: resource sharing, scalability, improved reliability/fault tolerance, cost-effectiveness (commodity hardware), and better performance through parallelism.

4

Disadvantages of distributed systems: added complexity, dependency on the network (latency, failures), greater security challenges, and harder debugging/testing.

5

Models of distributed systems include the Client-Server model, the Peer-to-Peer (P2P) model, and three-tier/N-tier architectures.

6

Resource sharing and the web face challenges of heterogeneity (different hardware/software), openness, security, scalability, failure handling, concurrency, and transparency.

7

Grid Computing is loosely coupled and geographically distributed, often across multiple organizations, used for large-scale scientific/collaborative computation.

8

Cluster Computing is tightly coupled with homogeneous nodes in close proximity and a high-speed interconnect, used for high-performance computing within a single organization.

9

Cloud Computing provides on-demand, virtualized, elastically scalable resources, delivered as a metered service over the internet for general-purpose computing.

10

Cloud computing delivers computing resources (servers, storage, databases, networking, software) on demand over the internet, typically with pay-as-you-go pricing.

11

The roots of cloud computing lie in grid computing, utility computing, virtualization, and Service-Oriented Architecture (SOA).

12

Cloud computing's five desired features: on-demand self-service, broad network access, resource pooling, rapid elasticity, and measured service.

13

Cloud challenges & risks: security/privacy concerns, vendor lock-in, downtime/availability, compliance/legal issues, and data-transfer bottlenecks.

14

Cloud benefits include cost savings (no upfront infrastructure investment), scalability/elasticity, accessibility from anywhere, and automatic updates/maintenance — offset by disadvantages such as dependency on internet connectivity, limited control over underlying infrastructure, and potential vendor lock-in.

1

Objects located on different machines interact through method invocations that are transparently transmitted across the network.

2

Remote Procedure Call (RPC) is a protocol that lets a program execute a procedure on a remote machine as if it were a local call, hiding the underlying network communication details from the programmer.

3

Events and notifications provide a publish-subscribe style mechanism, letting distributed components be notified asynchronously when events of interest occur.

4

A Distributed File System (DFS) allows access to files stored on remote servers as if they were local, providing location transparency.

5

A typical File Service Architecture is layered into a Flat File Service (operations on file contents using unique file identifiers), a Directory Service (mapping human-readable names to file identifiers), and a Client Module (integrating both to provide the file API applications actually use).

6

Sun Network File System (NFS) is a widely used DFS protocol enabling transparent remote file access using RPC; classic versions (NFSv2/v3) follow a stateless server design.

7

A Name Service maps human-readable names to resources/addresses; DNS (Domain Name System) is the internet's hierarchical, distributed name service mapping domain names to IP addresses.

8

Directory services (e.g. LDAP) store and organize information about network resources; discovery services let clients dynamically locate available services on a network.

9

A comparison of different DFS implementations (e.g. NFS vs AFS — the Andrew File System) typically looks at differences in caching strategy, consistency model, and scalability.

10

Heterogeneity in distributed systems refers to differences in hardware, operating systems, networks, and programming languages among a system's components.

11

Middleware is a software layer sitting between the OS/network and applications, providing common services (communication, naming, security) that abstract away this heterogeneity and simplify building distributed applications.

12

Objects in distributed systems extend OOP concepts across the network, encapsulating both data and behavior into objects that can be accessed remotely.

13

CORBA (Common Object Request Broker Architecture) is a middleware standard, defined by the OMG, that lets objects written in different languages and running on different platforms communicate through an Object Request Broker (ORB), using an Interface Definition Language (IDL) to describe object interfaces independent of any specific programming language.

14

CORBA services are standard services layered on top of the ORB, such as the Naming Service, Event Service, Transaction Service, and Security Service.

1

Virtualization creates a virtual (rather than physical) version of a resource — a server, storage device, or network — allowing multiple virtual instances to share the same physical hardware.

2

Load balancing and virtualization work together: virtualization allows virtual machines to be migrated or scaled flexibly across physical hosts based on demand.

3

A hypervisor is the software layer that creates and manages virtual machines: Type 1 (bare-metal) hypervisors run directly on the hardware (e.g. VMware ESXi, Xen), while Type 2 (hosted) hypervisors run on top of a host operating system (e.g. VMware Workstation, VirtualBox).

4

Virtualization can be applied at multiple layers of the computing stack (often described as seven layers of virtualization), spanning from the hardware level up through access, application, processing, network, storage, and management layers, each addressing different needs.

5

Types of virtualization: Server Virtualization runs multiple independent virtual servers on a single physical server; Desktop Virtualization runs a desktop OS/environment remotely, typically accessed from a thin client; Application Virtualization runs an application in an isolated environment without installing it fully on the local OS.

6

Public Cloud offers services over the public internet on shared infrastructure, available to any customer; Private Cloud provides dedicated infrastructure serving a single organization, offering more control and security; Hybrid Cloud combines both, letting data/applications move between them.

7

IaaS (Infrastructure as a Service) provides virtualized computing resources such as servers, storage, and networking (e.g. Amazon EC2); PaaS (Platform as a Service) provides a platform for developing/deploying applications without managing underlying infrastructure (e.g. Google App Engine); SaaS (Software as a Service) delivers complete applications over the internet (e.g. Gmail, Office 365).

8

Architectural design challenges for cloud systems include availability, scalability, data lock-in, interoperability, and unpredictable performance.

9

Cloud storage stores data on remote servers accessed via the internet and managed by the cloud provider, typically offering redundancy and elastic scalability.

10

Inter-cloud resource management coordinates resources across multiple cloud providers to optimize cost, performance, and availability.

11

Resource provisioning methods: Static provisioning (fixed resources allocated in advance) versus Dynamic provisioning (resources allocated/released on demand based on actual usage).

12

Cloud security challenges include the shared responsibility model, multi-tenancy risks (multiple customers sharing the same underlying physical infrastructure), data breaches, insecure APIs, and account hijacking.

13

Data, application, and VM security protect data at rest/in transit, guard applications against vulnerabilities, and isolate/secure virtual machines from each other and from the hypervisor; cloud infrastructure security must be addressed at the network, host, and application levels.

14

Key privacy issues in the cloud: data ownership, data location/jurisdiction, unauthorized access, and data retention/deletion policies.

1

Distributed nodes each have their own local clock, which can drift; clock synchronization coordinates these clocks so the system can reason consistently about time and event ordering.

2

Logical clock synchronization does not rely on physical time: Lamport's logical clocks order events using logical timestamps and the 'happens-before' relation, while vector clocks capture causality between events more precisely.

3

Physical clock synchronization algorithms adjust actual clock time: Cristian's algorithm has a client poll a time server and adjust for round-trip delay; the Berkeley algorithm has a coordinator poll all nodes, compute an average time, and tell each node how to adjust.

4

Distributed mutual exclusion ensures only one process accesses a shared critical resource at a time, even though there is no shared memory to coordinate directly.

5

The Centralized approach uses a single coordinator process to grant permission to enter the critical section; simple, but creates a single point of failure/bottleneck.

6

The Distributed (non-token-based) approach has processes exchange request/reply messages and use logical timestamps to decide entry order, with no central coordinator (e.g. the Ricart-Agrawala algorithm).

7

The Token-based approach circulates a unique token among processes; only the process holding the token may enter the critical section (e.g. token ring, Suzuki-Kasami algorithm).

8

A fault-tolerant system is designed to continue operating correctly even when some components fail, typically achieved through redundancy.

9

Replication maintains multiple copies of data/services across nodes to improve availability and fault tolerance.

10

Active Replication: all replicas independently process every request in parallel, keeping their states in sync.

11

Passive Replication: a single primary replica processes requests and then propagates the resulting updates to backup replicas.

12

Quorum-Based Replication: an operation is considered successful only once acknowledged by a sufficient quorum (majority) of replicas.