ক্যাপস্টোন — নিজের shell, scheduler আর memory allocator

#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/wait.h>
static void child(char **av, int in, int out) {          /* runs in the child */
    for (int i = 0; av[i]; i++)                          /* "< file", "> file" */
        if (!strcmp(av[i], "<") || !strcmp(av[i], ">")) {
            if (av[i][0] == '<') in = open(av[i + 1], O_RDONLY);
            else out = open(av[i + 1], O_WRONLY | O_CREAT | O_TRUNC, 0644);
            if (in < 0 || out < 0) { perror(av[i + 1]); _exit(1); }
            av[i] = NULL;
        }
    if (in != 0)  { dup2(in, 0);  close(in); }           /* wire stdin  */
    if (out != 1) { dup2(out, 1); close(out); }          /* wire stdout */
    execvp(av[0], av); perror(av[0]); _exit(127);        /* only on failure */
}
int main(void) {
    char line[256], *cmd[2][16];  dup2(1, 2);     /* stderr -> same output */
    while (fgets(line, sizeof line, stdin)) {
        printf("$ %s", line); fflush(stdout);    /* flush BEFORE fork */
        int n[2] = {0, 0}, k = 0, fd[2] = {0, 1}, st = 0;
        for (char *t = strtok(line, " \n"); t; t = strtok(NULL, " \n"))
            if (!strcmp(t, "|")) k = 1; else if (n[k] < 15) cmd[k][n[k]++] = t;
        cmd[0][n[0]] = cmd[1][n[1]] = NULL;
        if (n[0] == 0 || (k && n[1] == 0)) continue;
        if (!strcmp(cmd[0][0], "exit")) break;               /* a builtin */
        if (k && pipe(fd) < 0) { perror("pipe"); continue; }
        pid_t a = fork(), b = -1;
        if (a == 0) { if (k) close(fd[0]); child(cmd[0], 0, k ? fd[1] : 1); }
        if (k && (b = fork()) == 0) { close(fd[1]); child(cmd[1], fd[0], 1); }
        if (k) { close(fd[0]); close(fd[1]); }   /* parent keeps NO pipe end */
        waitpid(a, &st, 0); if (k) waitpid(b, &st, 0);   /* status = last cmd */
        printf("[exit %d]\n", WIFEXITED(st) ? WEXITSTATUS(st) : 128 + WTERMSIG(st));
    }
}

#include <stdio.h>
#define N 5
const char *name[N] = {"P1", "P2", "P3", "P4", "P5"};      /* sorted by arrival */
int at[N] = {0, 1, 2, 3, 4}, bt[N] = {5, 3, 1, 2, 3};
int left[N], start[N], ct[N], q[64], head, tail, next, t;
static void admit(void) {                 /* every arrival with at <= t joins */
    while (next < N && at[next] <= t) q[tail++] = next++;
}
static int pick_next(void) { return q[head++]; }      /* RR: front of FIFO */
int main(void) {
    const int Q = 2;
    for (int i = 0; i < N; i++) { left[i] = bt[i]; start[i] = -1; }
    admit();
    printf("Gantt:");
    while (head < tail || next < N) {
        if (head == tail) { t = at[next]; admit(); continue; }  /* CPU idle */
        int i = pick_next();
        if (start[i] < 0) start[i] = t;
        int run = left[i] < Q ? left[i] : Q;     /* next event: done or expiry */
        printf(" %s %d-%d |", name[i], t, t + run);
        t += run; left[i] -= run;
        admit();                       /* tie rule: NEW arrivals enter first, */
        if (left[i] > 0) q[tail++] = i;          /* then the expired process */
        else ct[i] = t;
    }
    int tat = 0, wt = 0, rt = 0;
    printf("\nproc AT BT  CT TAT WT RT\n");
    for (int i = 0; i < N; i++) {
        int a = ct[i] - at[i], w = a - bt[i], r = start[i] - at[i];
        tat += a; wt += w; rt += r;
        printf("%-4s %2d %2d %3d %3d %2d %2d\n", name[i], at[i], bt[i], ct[i], a, w, r);
    }
    printf("avg TAT = %.2f, WT = %.2f, RT = %.2f\n", tat / 5.0, wt / 5.0, rt / 5.0);
    return 0;
}

/* schedsim.c — event-driven CPU-scheduling simulator.
 *   usage: ./schedsim fcfs|sjf|srtf|prio|npprio|rr Q|mlfq [Q0 Q1]  < table.txt
 *   table: one process per line: NAME ARRIVAL BURST [PRIORITY]  (smaller = higher)
 * Tie rules (documented, and the same as the hand-worked lessons):
 *   1. equal key -> the running process keeps the CPU (preemptive policies);
 *   2. then earlier arrival, then earlier line in the table;
 *   3. RR / MLFQ: arrivals at time t join the queue BEFORE a process whose
 *      quantum expired at t; a process preempted by a higher MLFQ level stays
 *      at the head of its own level with the rest of its quantum.            */
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXP 64
typedef struct {
    char name[16];
    int at, bt, pr;              /* input                                     */
    int left, start, ct;         /* simulation state; start = first dispatch  */
    int level, used;             /* MLFQ level, time used of current quantum  */
    long stamp;                  /* FIFO order inside a queue (smaller = older) */
    int ready;                   /* arrived and not finished                  */
} Proc;

typedef enum { FCFS, SJF, SRTF, PRIO, NPPRIO, RR, MLFQ } Policy;
static Proc p[MAXP];
static int np, quantum[3] = { 0, 0, INT_MAX };
static long clock_stamp;

static int preemptive(Policy pol) { return pol == SRTF || pol == PRIO || pol == RR || pol == MLFQ; }

/* key of a ready process — smaller wins. This is the ONLY place a policy lives. */
static long key(Policy pol, const Proc *x) {
    switch (pol) {
    case FCFS:   return x->at;
    case SJF:    return x->bt;
    case SRTF:   return x->left;
    case PRIO: case NPPRIO: return x->pr;
    case RR:     return x->stamp;
    case MLFQ:   return (long)x->level * 1000000000L + x->stamp;
    }
    return 0;
}

/* pick_next(): the scheduler's whole decision, given who is running now */
static int pick_next(Policy pol, int running) {
    if (running >= 0 && !preemptive(pol)) return running;      /* never interrupt */
    int best = -1;
    for (int i = 0; i < np; i++) {
        if (!p[i].ready) continue;
        if (best < 0) { best = i; continue; }
        long a = key(pol, &p[i]), b = key(pol, &p[best]);
        if (a < b || (a == b && (i == running ||
            (best != running && p[i].at < p[best].at)))) best = i;   /* tie rules 1-2 */
    }
    return best;
}

static int next_arrival(int t) {                       /* earliest arrival > t */
    int na = INT_MAX;
    for (int i = 0; i < np; i++) if (p[i].at > t && p[i].at < na) na = p[i].at;
    return na;
}

static void admit(int t) {                             /* arrivals at time t   */
    for (int i = 0; i < np; i++)
        if (p[i].at == t) { p[i].ready = 1; p[i].stamp = ++clock_stamp; }
}

int main(int argc, char **argv) {
    const char *names[] = { "fcfs", "sjf", "srtf", "prio", "npprio", "rr", "mlfq" };
    Policy pol = (Policy)-1;
    for (int i = 0; argc > 1 && i < 7; i++) if (!strcmp(argv[1], names[i])) pol = (Policy)i;
    if ((int)pol < 0 || (pol == RR && (argc < 3 || atoi(argv[2]) <= 0))) {
        fprintf(stderr, "usage: %s fcfs|sjf|srtf|prio|npprio|rr Q|mlfq [Q0 Q1] < table\n", argv[0]);
        return 2;
    }
    if (pol == RR) quantum[0] = atoi(argv[2]);
    if (pol == MLFQ) { quantum[0] = argc > 2 ? atoi(argv[2]) : 8; quantum[1] = argc > 3 ? atoi(argv[3]) : 16; }

    char line[128];
    while (np < MAXP && fgets(line, sizeof line, stdin)) {
        Proc *x = &p[np];
        x->pr = 0;
        if (sscanf(line, "%15s %d %d %d", x->name, &x->at, &x->bt, &x->pr) < 3 || x->bt <= 0) continue;
        x->left = x->bt; x->start = -1; np++;
    }

    int t = 0, cur = -1, done = 0, dispatches = 0, nseg = 0;
    static char seg[512][24]; static int seg_s[512], seg_e[512];
    admit(0);
    while (done < np) {                     /* one iteration = one event */
        int nxt = pick_next(pol, cur);
        char label[24];
        int run;
        if (nxt < 0) {                                        /* CPU idle */
            run = next_arrival(t) - t;
            strcpy(label, "idle");
        } else {
            if (nxt != cur) dispatches++;
            cur = nxt;
            Proc *x = &p[cur];
            if (x->start < 0) x->start = t;
            if (pol == MLFQ) snprintf(label, sizeof label, "%s@Q%d", x->name, x->level);
            else snprintf(label, sizeof label, "%s", x->name);
            /* next event = completion, quantum expiry or next arrival */
            int q = (pol == RR) ? quantum[0] : (pol == MLFQ) ? quantum[x->level] : INT_MAX;
            run = x->left;
            if (q != INT_MAX && q - x->used < run) run = q - x->used;
            int na = next_arrival(t);
            if (na != INT_MAX && na - t < run) run = na - t;
            x->left -= run; x->used += run;
        }
        if (nseg && !strcmp(seg[nseg - 1], label) && seg_e[nseg - 1] == t) seg_e[nseg - 1] = t + run;
        else if (nseg < 512) { strcpy(seg[nseg], label); seg_s[nseg] = t; seg_e[nseg++] = t + run; }
        t += run;
        admit(t);                                   /* tie rule 3: arrivals first */
        if (cur < 0) continue;
        Proc *x = &p[cur];
        int q = (pol == RR) ? quantum[0] : (pol == MLFQ) ? quantum[x->level] : INT_MAX;
        if (x->left == 0) {
            x->ct = t; x->ready = 0; done++; cur = -1;
        } else if (q != INT_MAX && x->used == q) {  /* quantum expired */
            x->used = 0;
            if (pol == MLFQ && x->level < 2) x->level++;
            x->stamp = ++clock_stamp;               /* to the tail of its queue */
            cur = -1;
        }
    }
    printf("Gantt:");
    for (int i = 0; i < nseg; i++) printf(" %s %d-%d |", seg[i], seg_s[i], seg_e[i]);
    printf("\n%-5s %3s %3s %3s %4s %4s %4s %4s\n", "proc", "AT", "BT", "PR", "CT", "TAT", "WT", "RT");
    double s_tat = 0, s_wt = 0, s_rt = 0;
    for (int i = 0; i < np; i++) {
        int tat = p[i].ct - p[i].at, wt = tat - p[i].bt, rt = p[i].start - p[i].at;
        s_tat += tat; s_wt += wt; s_rt += rt;
        printf("%-5s %3d %3d %3d %4d %4d %4d %4d\n", p[i].name, p[i].at, p[i].bt, p[i].pr,
               p[i].ct, tat, wt, rt);
    }
    printf("avg TAT %.2f  avg WT %.2f  avg RT %.2f  dispatches %d\n",
           s_tat / np, s_wt / np, s_rt / np, dispatches);
    return 0;
}

#include <stdio.h>
#define ARENA 256                     /* bytes we manage; header = footer = 8 */
static _Alignas(16) unsigned char heap[8 + ARENA];
static unsigned char *const lo = heap + 8, *const hi = heap + 8 + ARENA;
#define TAG(p) (*(size_t *)(p))                        /* size | used-bit */
#define SIZE(b) (TAG(b) & ~(size_t)15)
static void mark(unsigned char *b, size_t sz, int used) { TAG(b) = TAG(b + sz - 8) = sz | used; }
static void *my_malloc(size_t n) {
    size_t need = (n + 16 + 15) & ~(size_t)15;   /* + tags, round up to 16 */
    for (unsigned char *b = lo; b < hi; b += SIZE(b))            /* first fit */
        if (!(TAG(b) & 1) && SIZE(b) >= need) {
            size_t rest = SIZE(b) - need;              /* split if >= 32 left */
            if (rest < 32) need = SIZE(b); else mark(b + need, rest, 0);
            mark(b, need, 1); return b + 8;            /* payload after header */
        }
    return NULL;
}
static void my_free(void *p) {
    unsigned char *b = (unsigned char *)p - 8; size_t sz = SIZE(b);
    if (b + sz < hi && !(TAG(b + sz) & 1)) sz += SIZE(b + sz);   /* next free? */
    if (b > lo && !(TAG(b - 8) & 1)) { b -= SIZE(b - 8); sz += SIZE(b); } /* prev */
    mark(b, sz, 0);                              /* one big free block */
}
static void show(const char *op) {              /* block list + invariants */
    size_t total = 0; int ok = 1, prev_free = 0; printf("%-18s", op);
    for (unsigned char *b = lo; b < hi; b += SIZE(b)) {
        int used = TAG(b) & 1; total += SIZE(b);
        printf(" [%3d %3zu %c]", (int)(b - lo), SIZE(b), used ? 'U' : 'F');
        ok &= TAG(b + SIZE(b) - 8) == TAG(b) && !(prev_free && !used)  /* tags, coalesced */
              && (size_t)(b + 8) % 16 == 0;  prev_free = !used;  /* aligned */
    }
    printf("  %s\n", ok && total == ARENA ? "OK" : "BROKEN");
}
#define DO(op) do { op; show(#op); } while (0)
int main(void) {
    char *a, *b, *c; mark(lo, ARENA, 0); show("init");
    DO(a = my_malloc(20)); DO(b = my_malloc(40)); DO(c = my_malloc(10));
    DO(my_free(b)); DO(my_free(a)); DO(a = my_malloc(60)); DO(my_free(c));
}

/* myalloc.c — malloc/free over a fixed arena: explicit (doubly linked) free list,
 * first fit, splitting, coalescing with boundary tags, 16-byte alignment,
 * a heap checker and a randomised test with a fixed seed.
 * Build: gcc -Wall -Wextra -O2 -o myalloc myalloc.c
 *
 * Block layout (sizes are multiples of 16, minimum 32):
 *   [ header: size|used ][ payload ...                          ][ footer: size|used ]
 *   a FREE block keeps two pointers at the start of its payload: next, prev   */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARENA   (64 * 1024)
#define TAGSZ   8
#define MINBLK  32
static _Alignas(16) unsigned char heap[TAGSZ + ARENA];   /* +8: payloads land on 16 */
static unsigned char *const lo = heap + TAGSZ, *const hi = heap + TAGSZ + ARENA;

typedef struct Free { struct Free *next, *prev; } Free;
static Free *free_head;                                   /* LIFO explicit list */

static size_t tag(const unsigned char *b)      { size_t v; memcpy(&v, b, sizeof v); return v; }
static void   set_tag(unsigned char *b, size_t v) { memcpy(b, &v, sizeof v); }
static size_t bsize(const unsigned char *b)    { return tag(b) & ~(size_t)15; }
static int    used(const unsigned char *b)     { return (int)(tag(b) & 1); }
static void   mark(unsigned char *b, size_t sz, int u) { set_tag(b, sz | (size_t)u); set_tag(b + sz - TAGSZ, sz | (size_t)u); }
static Free  *node(unsigned char *b)           { return (Free *)(void *)(b + TAGSZ); }
static unsigned char *blk(Free *f)             { return (unsigned char *)f - TAGSZ; }

static void list_push(unsigned char *b) {
    Free *f = node(b);
    f->prev = NULL; f->next = free_head;
    if (free_head) free_head->prev = f;
    free_head = f;
}
static void list_remove(unsigned char *b) {
    Free *f = node(b);
    if (f->prev) f->prev->next = f->next; else free_head = f->next;
    if (f->next) f->next->prev = f->prev;
}

void my_init(void) { mark(lo, ARENA, 0); free_head = NULL; list_push(lo); }

void *my_malloc(size_t n) {
    if (n == 0 || n > ARENA) return NULL;
    size_t need = (n + 2 * TAGSZ + 15) & ~(size_t)15;
    if (need < MINBLK) need = MINBLK;
    for (Free *f = free_head; f; f = f->next) {             /* first fit on the list */
        unsigned char *b = blk(f);
        size_t sz = bsize(b);
        if (sz < need) continue;
        list_remove(b);
        if (sz - need >= MINBLK) {                          /* split: tail stays free */
            mark(b + need, sz - need, 0);
            list_push(b + need);
            sz = need;
        }
        mark(b, sz, 1);
        return b + TAGSZ;
    }
    return NULL;                                            /* out of memory */
}

void my_free(void *p) {
    if (!p) return;
    unsigned char *b = (unsigned char *)p - TAGSZ;
    if (b < lo || b >= hi || ((uintptr_t)p & 15) || !used(b)) {
        fprintf(stderr, "my_free: invalid or double free %p\n", p);
        abort();
    }
    size_t sz = bsize(b);
    unsigned char *next = b + sz;
    if (next < hi && !used(next)) { list_remove(next); sz += bsize(next); }        /* case 2 */
    if (b > lo && !used(b - TAGSZ)) {                                               /* case 3 */
        unsigned char *prev = b - bsize(b - TAGSZ);
        list_remove(prev); sz += bsize(prev); b = prev;
    }
    mark(b, sz, 0);                                         /* case 1/4: one block */
    list_push(b);
}

/* invariants: tags agree, sizes sane, aligned, used + free = arena,
 * no two adjacent free blocks, the free list holds exactly the free blocks  */
int heap_check(size_t *used_bytes, size_t *free_bytes, size_t *largest) {
    size_t u = 0, fr = 0, big = 0; int nfree = 0, prev_free = 0;
    for (unsigned char *b = lo; b < hi; b += bsize(b)) {
        size_t sz = bsize(b);
        if (sz < MINBLK || sz % 16 || b + sz > hi || tag(b + sz - TAGSZ) != tag(b)) return 0;
        if ((uintptr_t)(b + TAGSZ) % 16) return 0;
        if (!used(b) && prev_free) return 0;               /* missed coalescing */
        prev_free = !used(b);
        if (used(b)) u += sz; else { fr += sz; nfree++; if (sz > big) big = sz; }
    }
    if (u + fr != ARENA) return 0;
    int nlist = 0;
    for (Free *f = free_head; f; f = f->next, nlist++) {
        unsigned char *b = blk(f);
        if (b < lo || b >= hi || used(b) || (f->next && f->next->prev != f) || nlist > nfree) return 0;
    }
    if (nlist != nfree) return 0;
    *used_bytes = u; *free_bytes = fr; *largest = big;
    return 1;
}

/* ---------------- randomised test with a fixed seed ---------------- */
static uint32_t rng = 2026;
static uint32_t xorshift(void) { rng ^= rng << 13; rng ^= rng >> 17; rng ^= rng << 5; return rng; }

int main(void) {
    enum { SLOTS = 400, OPS = 100000 };
    static unsigned char *ptr[SLOTS]; static size_t req[SLOTS];
    size_t live_req = 0, ok_allocs = 0, oom = 0;
    my_init();
    for (int op = 1; op <= OPS; op++) {
        int s = (int)(xorshift() % SLOTS);
        if (ptr[s]) {                                       /* free: check the pattern first */
            for (size_t i = 0; i < req[s]; i++)
                if (ptr[s][i] != (unsigned char)s) { printf("OVERLAP detected at op %d\n", op); return 1; }
            my_free(ptr[s]); ptr[s] = NULL; live_req -= req[s];
        } else {
            size_t n = 1 + xorshift() % (xorshift() % 8 == 0 ? 2048 : 128);   /* mostly small */
            if ((ptr[s] = my_malloc(n))) { memset(ptr[s], s, n); req[s] = n; live_req += n; ok_allocs++; }
            else oom++;
        }
        size_t u, f, big;
        if (!heap_check(&u, &f, &big)) { printf("INVARIANT broken at op %d\n", op); return 1; }
        if (op % 25000 == 0)
            printf("op %6d: used %5zu B (requested %5zu), free %5zu B, largest free %5zu, ext-frag %4.1f%%, internal %4.1f%%\n",
                   op, u, live_req, f, big, f ? 100.0 * (1.0 - (double)big / f) : 0.0,
                   u ? 100.0 * (double)(u - live_req) / u : 0.0);
    }
    for (int s = 0; s < SLOTS; s++) my_free(ptr[s]);     /* free everything */
    size_t u, f, big;
    int ok = heap_check(&u, &f, &big);
    printf("%zu successful mallocs, %zu out-of-memory; after freeing all: %s, one block of %zu B\n",
           ok_allocs, oom, ok ? "invariants OK" : "BROKEN", big);
    return 0;
}

// Randomised trace (fixed seed) on a 1024-byte arena: first / next / best fit.
// After EVERY operation the invariants are checked. Same trace for each policy.
function run(policy, show) {
  let seed = 2026, rover = 0, fails = 0, fragFails = 0, fragSum = 0, bad = 0;
  const rand = () => (seed = (seed * 16807) % 2147483647) / 2147483647;
  let blocks = [{ off: 0, size: 1024, used: false }]; const live = [];
  const freeSizes = () => blocks.filter(b => !b.used).map(b => b.size);
  for (let op = 1; op <= 3000; op++) {
    if (live.length && rand() < 0.45) {                       // free a random block
      live.splice(Math.floor(rand() * live.length), 1)[0].used = false;
      blocks = blocks.reduce((acc, x) => { const l = acc[acc.length - 1];   // coalesce
        if (l && !l.used && !x.used) l.size += x.size; else acc.push(x); return acc; }, []);
    } else {
      const need = 16 * Math.ceil((8 + rand() * 112 + 16) / 16);   // payload + tags
      const fit = blocks.filter(b => !b.used && b.size >= need);
      const b = policy === "best" ? fit.sort((x, y) => x.size - y.size)[0]
              : policy === "next" ? (fit.find(x => x.off >= rover) || fit[0]) : fit[0];
      if (!b) { fails++; if (freeSizes().reduce((s, x) => s + x, 0) >= need) fragFails++; }
      else { const rest = b.size - need;                       // split if >= 32 left
        if (rest >= 32) { blocks.splice(blocks.indexOf(b) + 1, 0, { off: b.off + need, size: rest, used: false }); b.size = need; }
        b.used = true; live.push(b); rover = b.off + b.size; }
    }
    let off = 0;                                               // invariants
    blocks.forEach((b, i) => { if (b.off !== off || (i && !b.used && !blocks[i - 1].used)) bad++; off += b.size; });
    if (off !== 1024) bad++;                                   // used + free = arena
    const free = freeSizes(), tot = free.reduce((s, x) => s + x, 0);
    fragSum += tot ? 1 - Math.max(...free) / tot : 0;           // external fragmentation
    if (show && op % 1000 === 0)
      console.log(String(op).padStart(4) + " " + blocks.map(b => (b.used ? "#" : ".").repeat(b.size / 16)).join(""));
  }
  console.log(`${policy.padEnd(5)} failed ${String(fails).padStart(3)} (enough total free: ${String(fragFails).padStart(3)})` +
              `  avg ext-frag ${(fragSum / 30).toFixed(1)}%  invariant violations ${bad}`);
}
console.log("first-fit map, one char = 16 bytes (# used, . free):");
run("first", true); run("next", false); run("best", false);