Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 55 ยท Practice and Review

Practice: OS, Networks and Security (with Solutions)

Twelve exercises on scheduling, deadlock, paging, paths, permissions, subnets, DNS, HTTP and hashing, each with a runnable stand-in and a worked solution.

The second half of the course covers software and the outside world: operating systems, file systems, networks and security. This page gives you twelve exercises that make those ideas concrete. Each has a task, an editor with starter code, and a solution to open after you have tried.

The real systems (a kernel, a router, a DNS server) cannot run inside a web page. Every editor here is therefore a stand-in: a small program that follows the same rules so you can practice the reasoning. Ten use JavaScript in your browser; the two hashing exercises run Node.js on our server, because they need the crypto module. Where an exercise quotes typical numbers, they are round figures for teaching, not measurements of any product.

flowchart TD
  OS["Operating system<br/>exercises 1-6"] --> NET["Network<br/>exercises 7-10"]
  NET --> SEC["Security<br/>exercises 11-12"]

The exercises follow the order of the course: OS, then networks, then security.

Operating systems

These practice Processes, Threads and Scheduling, Memory Management and File Systems.

1. Round-robin scheduling

Three processes need CPU time: A needs 5 time units, B needs 3 and C needs 2. A round-robin scheduler gives each process at most 2 units per turn, in the order A, B, C, A, B, ... Write the simulation, print the order of turns and the time each process finishes.

JS Exercise 1: Round-robin scheduling

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
const jobs = [
  { name: "A", left: 5 },
  { name: "B", left: 3 },
  { name: "C", left: 2 },
];
const quantum = 2;

let clock = 0;
const queue = [...jobs];
const order = [];

while (queue.length > 0) {
  const job = queue.shift();
  const slice = Math.min(quantum, job.left);
  clock += slice;
  job.left -= slice;
  order.push(job.name);
  if (job.left > 0) {
    queue.push(job);
  } else {
    console.log(job.name, "finished at time", clock);
  }
}
console.log("turn order:", order.join(" "));

The turn order is A B C A B A. C finishes at time 6, B at 9 and A at 10. Total work is 10 units, so the CPU is never idle. Note that the shortest job (C) is not first to be served, but nobody waits forever: that is the fairness round-robin buys.

2. Spot the deadlock

A deadlock happens when processes wait for each other in a circle. Represent "who waits for whom" as an object and write hasCycle(graph) that detects a cycle with a depth-first search.

JS Exercise 2: Spot the deadlock

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
const safe = { P1: ["P2"], P2: ["P3"], P3: [] };
const stuck = { P1: ["P2"], P2: ["P3"], P3: ["P1"] };

function hasCycle(graph) {
  const done = new Set();
  const path = new Set();

  function visit(node) {
    if (path.has(node)) return true;   // we came back to a node on our own path
    if (done.has(node)) return false;
    path.add(node);
    for (const next of graph[node]) {
      if (visit(next)) return true;
    }
    path.delete(node);
    done.add(node);
    return false;
  }

  return Object.keys(graph).some(visit);
}

console.log(hasCycle(safe));  // false
console.log(hasCycle(stuck)); // true

In the second graph P1 waits for P2, P2 for P3 and P3 for P1: nobody can move. Real systems prevent this with rules such as always acquiring locks in the same order.

3. Paging and Belady's surprise

With FIFO page replacement, the oldest page in memory is evicted first. Count the page faults for the reference string 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames and then with 4 frames. Expect a surprise.

JS Exercise 3: FIFO page faults

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
const refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];

function fifoFaults(refs, frames) {
  const memory = [];
  let faults = 0;
  for (const page of refs) {
    if (memory.includes(page)) continue;   // hit
    faults++;
    if (memory.length === frames) memory.shift(); // evict the oldest
    memory.push(page);
  }
  return faults;
}

console.log("3 frames:", fifoFaults(refs, 3)); // 9
console.log("4 frames:", fifoFaults(refs, 4)); // 10

More memory produced more faults. This is known as Belady's anomaly and it affects FIFO. Policies such as LRU (least recently used) never behave this way, which is one reason operating systems prefer approximations of LRU.

4. Clean up a path

Write normalize(path) that resolves . (stay), .. (go up) and repeated slashes in an absolute path.

JS Exercise 4: Clean up a path

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
function normalize(path) {
  const stack = [];
  for (const part of path.split("/")) {
    if (part === "" || part === ".") continue;
    if (part === "..") {
      stack.pop();              // going above the root stays at the root
    } else {
      stack.push(part);
    }
  }
  return "/" + stack.join("/");
}

console.log(normalize("/home/ana/../bob/./docs//file.txt")); // /home/bob/docs/file.txt
console.log(normalize("/a/b/../../.."));                     // /

A stack models walking through directories: a name goes down one level, .. goes back up. At the root, .. has nowhere to go, so popping an empty stack is harmless.

5. Reading permission bits

Unix-style permissions are three octal digits for owner, group and others. Each digit adds 4 (read), 2 (write) and 1 (execute). Write toSymbolic(mode) so that 754 becomes rwxr-xr--.

JS Exercise 5: Permission bits

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
function toSymbolic(mode) {
  let out = "";
  for (const ch of mode) {
    const d = Number(ch);
    out += d & 4 ? "r" : "-";
    out += d & 2 ? "w" : "-";
    out += d & 1 ? "x" : "-";
  }
  return out;
}

console.log(toSymbolic("754")); // rwxr-xr--
console.log(toSymbolic("600")); // rw-------

7 is 4+2+1 (everything), 5 is 4+1 (read and execute), 4 is read only. Mode 600 is a common choice for private files: only the owner can read or write.

6. Blocks and wasted space

A file system stores files in blocks of 4,096 bytes. A file of 10,000 bytes occupies whole blocks. How many blocks does it use, how many bytes are allocated and how many are wasted at the end? This waste is called internal fragmentation.

JS Exercise 6: Blocks and wasted space

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
function allocation(fileBytes, blockBytes) {
  const blocks = Math.ceil(fileBytes / blockBytes);
  const allocated = blocks * blockBytes;
  return { blocks, allocated, wasted: allocated - fileBytes };
}

console.log(allocation(10000, 4096)); // { blocks: 3, allocated: 12288, wasted: 2288 }
console.log(allocation(1, 4096));     // { blocks: 1, allocated: 4096, wasted: 4095 }
console.log(allocation(8192, 4096));  // { blocks: 2, allocated: 8192, wasted: 0 }

This is why a folder with thousands of tiny files can use far more disk space than the sum of their sizes.

Networks and the web

These practice Networking Basics, The Internet, IP Addresses and DNS and How the Web Works.

7. Is this address in my subnet?

A network is written 192.168.10.64/26: the first 26 bits identify the network, the remaining 6 bits identify hosts. How many usable host addresses does it have (the all-zero and all-one host values are reserved)? Is 192.168.10.77 inside it? Is 192.168.10.130?

JS Exercise 7: Subnet membership

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
function ipToInt(ip) {
  return ip.split(".").reduce((n, part) => n * 256 + Number(part), 0);
}

function inSubnet(ip, network, prefix) {
  const mask = prefix === 0 ? 0 : (0xffffffff << (32 - prefix)) >>> 0;
  return ((ipToInt(ip) & mask) >>> 0) === ((ipToInt(network) & mask) >>> 0);
}

console.log(2 ** (32 - 26) - 2);                                  // 62
console.log(inSubnet("192.168.10.77", "192.168.10.64", 26));      // true
console.log(inSubnet("192.168.10.130", "192.168.10.64", 26));     // false

A /26 leaves 6 host bits: 64 addresses, 62 usable. The range runs from 192.168.10.64 to 192.168.10.127, so .77 is inside and .130 is not. The >>> 0 converts JavaScript's signed 32-bit result back to an unsigned number.

8. A DNS resolver with a cache

A resolver asks a root server, then a .com server, then the server for example.com. Count how many queries it sends for a first lookup and for a repeated one that is answered from the cache.

JS Exercise 8: DNS resolver with a cache

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
const servers = {
  root: { "com": "tld-com" },
  "tld-com": { "example.com": "ns-example" },
  "ns-example": { "www.example.com": "93.184.216.34" },
};

const cache = new Map();
let queries = 0;

function ask(server, key) {
  queries++;
  return servers[server][key];
}

function resolve(name) {
  if (cache.has(name)) return cache.get(name);
  const labels = name.split(".");
  const tld = ask("root", labels.at(-1));
  const ns = ask(tld, labels.slice(-2).join("."));
  const address = ask(ns, name);
  cache.set(name, address);
  return address;
}

console.log(resolve("www.example.com"), "queries so far:", queries); // 93.184.216.34 ... 3
console.log(resolve("www.example.com"), "queries so far:", queries); // 93.184.216.34 ... 3

The first lookup walks the chain with three queries; the second is served from the cache with none. Real resolvers also respect a time-to-live on each cached answer, and the address shown is an example value from the stand-in, not a live lookup.

9. Take a URL apart

Use the built-in URL class to print the scheme, host, port, path, query parameters and fragment of a web address. Then list the query parameters as key-value pairs.

JS Exercise 9: Anatomy of a URL

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
const address = "https://shop.example.com:8443/items/42?color=red&size=m#reviews";
const url = new URL(address);

console.log("scheme:  ", url.protocol);   // https:
console.log("host:    ", url.hostname);   // shop.example.com
console.log("port:    ", url.port);       // 8443
console.log("path:    ", url.pathname);   // /items/42
console.log("fragment:", url.hash);       // #reviews
for (const [key, value] of url.searchParams) {
  console.log("param:   ", key, "=", value);
}

The fragment (#reviews) never travels to the server; the browser uses it to scroll. Without an explicit port, port is an empty string because the scheme implies the default (443 for HTTPS).

10. Sort the status codes

Write describeStatus(code) that returns the class of an HTTP status code (informational, success, redirect, client error, server error) and apply it to a list of codes.

JS Exercise 10: HTTP status classes

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Show solution
JavaScript
function describeStatus(code) {
  switch (Math.floor(code / 100)) {
    case 1: return "informational";
    case 2: return "success";
    case 3: return "redirect";
    case 4: return "client error (your request is wrong)";
    case 5: return "server error (their side failed)";
    default: return "unknown";
  }
}

for (const code of [101, 200, 301, 404, 429, 500, 503]) {
  console.log(code, describeStatus(code));
}

The first digit carries the meaning. 404 means the client asked for something that is not there; 503 means the server is temporarily unable to answer. 429 means too many requests, which is the server asking the client to slow down.

Security

These practice Passwords, Hashing and Encryption. Both editors run Node.js on our server (a real crypto module), so they use the node fence.

11. Hashing: same input, same output

Compute the SHA-256 hash of "hello" and of "hello!". Print both in hex. What do you notice about the two results, and about their length?

Node.js Exercise 11: Hashing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Show solution
NODE
import { createHash } from "node:crypto";

function sha256(text) {
  return createHash("sha256").update(text).digest("hex");
}

const a = sha256("hello");
const b = sha256("hello!");
console.log(a);
console.log(b);
console.log("length:", a.length, b.length);
console.log("same hash for same input:", sha256("hello") === a);

Both hashes are 64 hex characters (256 bits) regardless of the input length, the two results look completely unrelated even though the inputs differ by one character, and the same input always gives the same output. Those properties make hashes good for checking integrity. A hash cannot be "decrypted" back to the input.

12. Salted password storage and brute force

Store passwords as a salted hash. Show that the same password gives different stored values for two users when each has a random salt, and that a check with the right salt succeeds. Then compute how long an attacker needs for all 8-letter lowercase passwords at one billion guesses per second.

Node.js Exercise 12: Salted hashes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Show solution
NODE
import { randomBytes, scryptSync, timingSafeEqual } from "node:crypto";

function hashPassword(password) {
  const salt = randomBytes(16);
  const hash = scryptSync(password, salt, 32);
  return { salt: salt.toString("hex"), hash: hash.toString("hex") };
}

function verify(password, record) {
  const salt = Buffer.from(record.salt, "hex");
  const expected = Buffer.from(record.hash, "hex");
  const actual = scryptSync(password, salt, 32);
  return timingSafeEqual(actual, expected);
}

const alice = hashPassword("correct horse");
const bob = hashPassword("correct horse");
console.log("same stored hash for two users:", alice.hash === bob.hash);
console.log("right password:", verify("correct horse", alice));
console.log("wrong password:", verify("wrong horse", alice));

const combos = 26 ** 8;
console.log("8 lowercase letters:", combos, "combinations");
console.log("seconds at 1e9 guesses/s:", (combos / 1e9).toFixed(1));

Different salts make identical passwords look different, so one stolen table cannot be attacked with a shared lookup list. scrypt is deliberately slow, which is the second defence. The search space for eight lowercase letters is 208,827,064,576, about 209 seconds at a billion fast guesses per second, which is why short simple passwords are weak against fast hashes. A deliberately slow hash and longer passwords change that arithmetic completely.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In round-robin scheduling with a quantum of 2, a process needs 5 units. How many turns does it get?

    It runs 2, 2 and finally 1 unit, so it gets three turns, with other processes running between them.
  2. 2. How many usable host addresses does a /26 IPv4 network have?

    32 - 26 = 6 host bits, so 64 addresses, minus the network and broadcast addresses gives 62.
  3. 3. Why do systems add a random salt before hashing a password?

    Salt makes each stored hash unique, which defeats precomputed lookup tables and hides that two users share a password.
  4. 4. A request returns status 503. Whose side has the problem?

    5xx codes are server-side errors; 503 means the service is temporarily unavailable.

Summary

  • Round-robin shares the CPU fairly in fixed slices; deadlock is a cycle of processes waiting for each other.
  • FIFO page replacement can fault more with more memory (Belady's anomaly); LRU does not.
  • Paths are resolved with a stack; permission digits add up read (4), write (2) and execute (1).
  • Files occupy whole blocks, so small files waste space.
  • A /n subnet leaves 32 - n host bits; DNS walks root, TLD and name servers and caches answers.
  • URL parts and status code classes tell you where to look first when something breaks.
  • Hashes are one-way and fixed length; salting and slow hashes protect stored passwords.

Continue with Computer Fundamentals Interview Questions.