Понятия задачи (task), потока (thread) и процесса (process) в Linux

Task, thread и process – это, в принципе, достаточно близкие по смыслу понятия, но надо всё-таки разобраться, что каждое из них значит.

Когда вы запускаете приложение, в системе создаётся процесс (process), которому выделяется память на хранение исполняемого кода и других данных. В рамках этого процесса создаётся минимум один поток (thread). Именно среди потоков планировщики Linux и распределяют время процессора, а также решают, в какой очерёдности они будут выполняться. Задачей (task) можно назвать уже непосредственно сами инструкции, которые процессор получает и выполняет.

Важно также знать, что у процессов есть поле state, которое, как понятно по названию, показывает, в каком состоянии сейчас находится процесс. Состояний может быть несколько:

Running или Runnable (R) – процесс в состоянии running прямо сейчас использует процессорное время, в свою очередь runnable процесс только ожидает его.

Uninterruptible Sleep (D) – процесс ждёт результата операции ввода-вывода. Например, ждёт данные от диска. Такой процесс никак нельзя убить.

Interruptible Sleep (S) – процесс ждёт какое-то событие и не потребляет процессорного времени. Пример: ввод из командной строки.

Stopped (T) – процесс получил сигнал SIGSTOP или SIGTSTP и остановил свою работу. В этом состоянии процессу можно послать сигнал SIGCONT и запустить его снова.

Zombie (Z) – процесс, который получил сигналы на завершение работы, и полностью её завершил – он больше не потребляет ресурсов системы, только PID идентификатор. Он ждет, когда его родительский процесс выполнит системный вызов wait, после этого Zombie исчезнет. Иногда этого может не происходить, в таком случае приходится дебажить родителя.

Всю информации о процессе можно достать из папки /proc/<PID>, где <PID> – это идентификатор процесса. Если вам нужно получить информацию в более “user friendly” виде, то воспользуйтесь утилитами top, htop, ps и тд.

Генератор случайных чисел Лемера

Очень быстрый генератор случайных чисел. Подробнее можно почитать здесь.

Алгоритм Lehmer64 — это быстрый генератор псевдослучайных чисел (ГПСЧ), основанный на мультипликативном линейном конгруэнтном методе. Он использует 128-битное состояние для генерации 64-битных случайных чисел, обеспечивая высокую производительность и достаточную статистическую случайность для большинства некриптографических задач.

> Мультипликативный линейный конгруэнтный метод (мультипликативный конгруэнтный метод) — это алгоритм для генерации псевдослучайных чисел, основанный на линейной рекуррентной формуле. Простыми словами, метод создаёт последовательность чисел, где каждое последующее число зависит от предыдущего, но при этом существует цикл, повторяющийся бесконечное число раз (период).

Принцип работы
Основная формула метода: Xn+1 = (a ⋅ Xn + c) mod m, где:

+ Xn+1 — следующее псевдослучайное число;
+ Xn — текущее псевдослучайное число;
+ a — мультипликативный множитель;
+ c — приращение;
+ m — модуль;
+ X0 — начальное значение (seed).

И вот его простейшая реализация на C:

static __uint128_t g_lehmer64_state;

uint64_t lehmer64(void) {
    g_lehmer64_state *= 0xda942042e4dd58b5ULL;
    return g_lehmer64_state >> 64;
}

Каждый раз, когда нужно новое число, мы умножаем состояние на константу 0xda942042e4dd58b5ULL (высчитанная экспериментальным путем). g_lehmer64_state - это состояние размером 128 бит, на старте в котором хранится нечетный сид. После этого берем старшие 64 бита и возвращаем их, младшие остаются.

Всех с наступающим новым годом!

В этот год наш канал вырос в разы, достиг 350+ подписчиков, мы узнали много нового.

В этот день хочется поблагодарить каждого из вас, за участие в нашем канале Дальше - больше!

Желаем вам счастья, радостей, исполнения желаний и планов, чтобы код писался без багов, чтобы девопсы не спали когда падают сервера. А также желаем повышения грейда, улучшения денежного довольствия и личного уровня счастья!

С наступающим новым годом!

Мы вместе спускались в кроличью нору, и каждый раз казалось, что вот оно — дно, но неожиданно со дна стучались. Си — невероятно простой и сложный язык одновременно.

Наши первые 5 статей показали, что математика и низкоуровневые оптимизации могут быть не только полезными, но и по‑настоящему увлекательными.

Но на этом наша история не заканчивается. Впереди нас ждут структуры данных, алгоритмы сжатия, ГПСЧ и настолько бесполезные трюки, что их полезность становится философским вопросом.


https://habr.com/ru/companies/timeweb/articles/977208/

Хабр лёг! #хабр_не_торт

Полезные алиасы для GIT

Алиасы для git можно делать как стандартным внешним путём через конфиг вашего шелла:

alias gga="git add"
alias ggc="git commit"
alias ggcm="git commit -m"
alias ggs="git status"
alias ggl="git log"
alias gglo="git log --oneline"
alias ggd="git diff"
alias ggds="git diff --staged"
alias ggr="git restore"

Так и через конфигурирование файла ~/.gitconfig:

[alias]
    st = status -b
    c = commit
    co = checkout
    br = branch
    slog = log --pretty=format:"%C(auto)%h%C(auto)%d\\ %C(auto,reset)%s\\ \\ [%C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)]"
    glog = log --graph --pretty=format:"%C(auto,yellow)%h%C(auto)%d\\ %C(auto,reset)%s\\ \\ [%C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)]"
    wlog = log --pretty=format:"%C(auto,yellow)%h%C(auto)%d%C(auto,reset)\\ by\\ %C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)%n\\ %s%n" --stat
    gr = log --graph --abbrev-commit --decorate --format=format:'%C(bold blue)%h%C(reset) - %C(bold green)(%ar)%C(reset) %C(white)%s%C(reset) %C(dim white)- %an%C(reset)%C(bold yellow)%d%C(reset)' --all
    wt = worktree

Я достаточно часто пользуюсь этими алиасами для быстрой работы с репозиториями, получения логов и графов веток и коммитов.

Давайте попробуем импортозаместить стандартный pow нашим алгоритмом, а точнее — бинарным возведением в степень. Сложность — O(log n).

Широко известный алгоритм для возведения любого числа в целую степень с абсолютной точностью. Принцип действия прост: есть целая степень e, чтобы получить число b в этой степени нужно возвести это число во все степени 1, 2, 4, … 2n (в коде этому соответствует b *= b), каждый раз сдвигая биты e вправо (e >>= 1) пока оно не равно 0 и тогда, когда последний бит e не равен нулю ((e & 1) != 0), домножать результат v на полученное b. Этот метод позволяет возвести число в целую степень за логарифмическое время, что особенно важно при работе с большими числами.

Возьмём 2⁵. Вместо 2×2×2×2×2 мы представляем 5 в двоичном виде (101) и идем по битам справа налево. Первый бит (1) равен 2, второй бит (0) равен 2 в квадрате, и в последнем третьем биту (1) результат (2) умножаем на текущее значение (4²=16) → 32.

Технически, при каждом проходе цикла, мы проверяем младший бит степени e. Если этот бит равен 1 (e & 1 != 0), мы умножаем текущий результат v на основание b. После этого мы умножаем b на само себя (квадрат), что соответствует следующей степени двоичного представления. Уменьшая e с помощью побитового сдвига вправо, мы продолжаем цикл, пока e не достигает нуля, в результате чего получаем финальный результат.

double binary_pow(double b, unsigned long long e) {
    double v = 1.0;
    while(e != 0) {
            if((e & 1) != 0) {
                    v *= b;
            }
            b *= b;
            e >>= 1;
    }
    return v;
}

И при выполнении мы можем получить 10.00 ^ 2.00 = 100.00, 10.50 ^ 2.00 = 110.25. Но если экспонента не целое число, то данный способ не подойдет (10.50^2.50 вычисляется как 110.25). Так что важно отметить, что этот алгоритм применим только к целым числам.

Согласно википедии, Код Мортона (называемый также Z-порядок, кривая Мортона, кривая Лебега) - это функция, которая отоброжает многомерные данные в одномерные. Идея — чередовать биты координатных значений.

Bit Interleaving (перемежение битов, интерливинг) — процесс изменения порядка следования битов в передаваемой последовательности. Цель — разнести ошибки так, чтобы они влияли на разбросанные биты, а не на последовательные.

static uint32_t split_bits(uint16_t x) {
    x = (x | (x << 8)) & 0x00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F;
    x = (x | (x << 2)) & 0x33333333;
    x = (x | (x << 1)) & 0x55555555;
    return x;
}

uint32_t morton_encode(uint16_t x, uint16_t y) {
    return split_bits(x) | (split_bits(y) << 1);
}

void morton_decode(uint32_t code, uint16_t *x, uint16_t *y) {
    uint32_t x_code = code & 0x55555555;
    uint32_t y_code = code & 0xAAAAAAAA;

    x_code = (x_code | (x_code >> 1)) & 0x33333333;
    x_code = (x_code | (x_code >> 2)) & 0x0F0F0F0F;
    x_code = (x_code | (x_code >> 4)) & 0x00FF00FF;
    x_code = (x_code | (x_code >> 8)) & 0x0000FFFF;

    y_code = (y_code | (y_code >> 1)) & 0x33333333;
    y_code = (y_code | (y_code >> 2)) & 0x0F0F0F0F;
    y_code = (y_code | (y_code >> 4)) & 0x00FF00FF;
    y_code = (y_code | (y_code >> 8)) & 0x0000FFFF;

    *x = (uint16_t)x_code;
    *y = (uint16_t)(y_code >> 1);
}

Битовый интерливинг перемешивает биты двух чисел. Для координат x и y мы берем их бинарные представления и создаем некое новое число, куда поочередно будем записывать биты из x и y. К примеру, если x = 10 (1010) и y=12 (1100), то процесс будет таким: возьмем младшие биты x (0) и y (0), соединив их получаем 00. Затем следующий бит y (0) и следующий бит x (1), получаем 01. Затем бит y (1) и бит x (0), получаем 10. Наконец, старший бит y (1) и старший бит x (1), получаем 11. Итоговый код Мортона: 11 10 01 00 = 11100100₂ = 228.

Функция split_bits выполняет ключевую операцию - она раздвигает биты числа, вставляя между ними нули. Для 4-битного числа 1010 после split_bits получается 01000100 в бинарном виде.

Функция morton_encode вызывает функцию split_bits для x и y, после сдвигает результат для y на один бит влево и объедяняет XOR'ом.

Функция morton_decode выполняет обратную операцию. Сначала она разделяет код на биты, принадлежащие x (нечетные позиции) и y (четные позиции), используя маски 0x55555555 и 0xAAAAAAAA. Затем сжимает биты обратно в 16-битные числа, выполняя операции, обратные split_bits.

Основное преимущество кода Мортона - сохранение пространственной локальности. Точки, близкие в двумерном пространстве, обычно имеют близкие значения кодов Мортона. Это свойство используется в пространственных индексах, квадродеревьях, компьютерной графике и GIS системах для эффективной организации данных.

Давайте попробуем запустить и проверить алгоритм:

int main() {
    uint16_t x = 10;
    uint16_t y = 13;

    uint32_t code = morton_encode(x, y);
    printf("x=%u, y=%u\n", x, y);
    printf("Morton code: %u (0x%08X)\n", code, code);

    uint16_t decoded_x, decoded_y;
    morton_decode(code, &decoded_x, &decoded_y);
    printf("Decoded: x=%u, y=%u\n", decoded_x, decoded_y);

    return 0;
}

При запуске получаем:

x=10, y=12
Morton code: 228 (0x000000E4)
Decoded: x=10, y=6

Сам код мортона благодаря тому что упаковывает 2D/3D координаты в 1D число, используется в ГИС, базах данных, играх и прочих системах где нужна упаковка координат.

Бьюсь об заклад, что вы крайне редко видели код на GNU-стандартах. В качестве примера я хочу показать пример рабочей программы с устаревшими и специфичными вещами.

??=include <stdio.h>

int $func(int array[static 10]) <%
    int sum = 0;
    for (int i = 9; i --> 0;) <%
        sum += array<:i:>;
    %>
    return sum;
%>

int $print_func(int array[static 10]) <%
    for (int i = 9; i >= 0; --i) <%
        printf("Value %i with index %i\n", array[i], i);
    %>
    return 0;
%>


int main() ??<
    int arr<:10:> = {[0]=1, [5]=5, [9]=9};

    $print_func(arr);

    int result = (<%
        int temp = $func(arr);
        printf("Sum: %d??/n", temp);
        temp;
    %>);

    void *ptr = ??< &&label ??>;
    goto *ptr;

    label:
    return result;
??>

Скомпилировав код выше через gcc gnustd_fun.c -o gnustd_fun -std=gnu11 -trigraphs, мы получим:

Value 9 with index 9
Value 0 with index 8
Value 0 with index 7
Value 0 with index 6
Value 5 with index 5
Value 0 with index 4
Value 0 with index 3
Value 0 with index 2
Value 0 with index 1
Value 1 with index 0
Sum: 6

Этот код использует такие вещи, как триграфы ??= вместо символа #, ??< для открывающей фигурной скобки и ??> для закрывающей. Триграфы и диграфы (<% и %> также заменяют фигурные скобки, а <: и :> служат заменой квадратных скобок) были созданы для замены возможных несуществующих на клавиатуре символов скобок в стародавние времена.

Имена функций func и print_func начинаются с символа $ (php-разработчики должны пустить слезу), что является допустимым расширением компилятора.

Цикл в функции $func записан в необычной форме: for (int i = 9; i --> 0;). Оператор --> на самом деле комбинация постфиксного декремента i-- и оператора сравнения >. В функции main массив инициализируется следующим образом: {[0]=1, [5]=5, [9]=9}, где явно задаются значения только для конкретных индексов.

Далее используется составное выражение в круглых скобках ({ ... }), которое является расширением GCC и называется statement expression. Оно выполняет блок кода, а значением всего выражения становится результат последнего оператора внутри блока, в данном случае temp;. Это позволяет совместить вычисление суммы, её вывод через printf и передачу значения в переменную result.

Наиболее экзотическая часть кода — это использование указателей на метки. Конструкция &&label берет адрес метки в памяти, сохраняя его в указатель void *ptr. Затем с помощью оператора косвенного перехода goto *ptr; выполняется прыжок по этому адресу. Это нестандартное расширение GCC. После перехода на метку label: функция main возвращает ранее вычисленную сумму.

Floyd's Tortoise and Hare

Алгоритм придуман Робертом Флойдом и используется для обнаружения циклов в последовательностях, чаще всего в связных списках, но идея применима и к другим структурам, где есть переход по индексам или указателям.

Суть алгоритма: Два указателя ("черепаха" и "заяц") движутся по последовательности с разной скоростью. Заяц делает два шага за итерацию, черепаха — один. Если в последовательности есть цикл, то заяц неизбежно "догонит" черепаху внутри цикла. Если цикла нет, заяц первым достигнет конца последовательности.

#include <stdio.h>

int findCycle(int nums[], int numsSize) {
    if (numsSize <= 1) return -1;

    int tortoise = nums[0];
    int hare = nums[0];

    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
        if (hare < 0 || hare >= numsSize) return -1;
    } while (tortoise != hare);

    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }

    return tortoise;
}

Код использует два указателя — медленный (черепаха) и быстрый (заяц). Оба стартуют с начала массива. Медленный движется на 1 шаг: tortoise = nums[tortoise]. Быстрый — на 2 шага: hare = nums[nums[hare]]. Если массив содержит цикл, быстрый рано или поздно догонит медленного внутри цикла. Это первая фаза — обнаружение факта цикла.

После встречи медленного возвращаем в начало массива. Теперь оба движутся синхронно, по 1 шагу. Точка их новой встречи будет точкой входа в цикл. Это вторая фаза — нахождение начала цикла.

Проверка hare < 0 || hare >= numsSize отлавливает выход за границы, что означает отсутствие цикла. Алгоритм работает за O(n) времени и O(1) памяти, не меняя исходные данные. В примере {1,3,4,2,2} последовательность индексов 0→1→3→2→4→2 зацикливается на значениях 2 и 4, а начало цикла — значение 2.

Давайте протестируем код:

int main() {
    int arr[] = {1, 3, 4, 2, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = findCycle(arr, size);

    if (result != -1) {
        printf("Cycle starts at value: %d\n", result);
    } else {
        printf("No cycle found\n");
    }

    return 0;
}

Как мы видим, массив становится цикличным на 2: Cycle starts at value: 2.

Если хотите больше контента по PostgreSQL и SQL, СУБД, ставьте реакции, тогда я пойму что тема интересна вам.

Каждый, кто проводит в терминале больше пяти минут, сталкивается с одним и тем же: одни и те же длинные команды приходится набирать снова и снова, а рутинные действия отнимают время и внимание. Сначала терпишь, потом — начинаешь оптимизировать.

Простейший алиас в .bashrc или .zshrc кажется небольшим открытием. Первый рабочий скрипт, сохранённый в ~/.local/bin, ощущается как прорыв. Это не просто про лень — это про эффективность, про оптимизацию работы.

Со временем такая «мелкая оптимизация» собирается в целый личный фреймворк или набор утилит для командной строки. Это уже не пара заплаток, а твоя собственная среда, отточенная под конкретные задачи. В этой статье я хочу показать свою коллекцию таких скриптов и алиасов — не как идеальный стандарт, а как пример живого подхода. Возможно, какие-то решения окажутся полезными и вам, а главное — побудят создать что-то своё, ещё более удобное.

https://habr.com/ru/companies/timeweb/articles/983418/

Всем привет! Небольшой отход от основной темы канала, я решил попробовать себя в перевод и перевел статью "Raspberry Pi Drag Race: Pi 1 to Pi 5 – Performance Comparison" с Hacker News.

Сегодня мы хотим рассмотреть на практике 13 летнюю историю разработки Raspberry Pi. У меня есть экземпляры каждого поколения Pi, от оригинальной модели из 2012 года, до Pi 5, которая вышла чуть больше года назад.

В этой статье мы изучим, что менялось от поколения к поколению, как менялись их производительность и энергопотребление, проведя несколько тестов.

Читать статью - https://habr.com/ru/articles/988770/

Буду рад фидбеку по качеству перевода и по заинтересованности в теме КПК.

Индексы в PostgreSQL — это специальные структуры данных, которые ускоряют поиск информации в таблицах, но требуют определённых затрат. Работают они, грубо говоря, как указатель в книге: вместо того чтобы листать все страницы (читать всю таблицу с диска), система быстро находит нужные строки по специальной карте — индексу.

Когда вы создаёте индекс, PostgreSQL строит по выбранному столбцу упорядоченную структуру (чаще всего B-дерево), которая связывает значение в столбце с физическим адресом строки в таблице. Это позволяет находить данные за логарифмическое время, даже в огромных таблицах. Например, поиск одного игрока в таблице из миллиона строк без индекса заставляет систему прочитать все строки (последовательное сканирование), что занимает сотни миллисекунд. С индексом — только несколько страниц и доли миллисекунд.

Однако индексы — не бесплатный способ ускорения. Во-первых, они занимают дополнительное место на диске (иногда даже больше самой таблицы). Во-вторых, при каждой вставке, обновлении или удалении строки, затрагивающей проиндексированные столбцы, системе приходится обновлять и индекс, что замедляет запись. В-третьих, слишком много индексов могут запутать планировщик запросов (который решает, как выполнить запрос оптимально) и увеличить время на само планирование. И наконец, индексы используют оперативную память, конкурируя с кэшированием данных таблицы.

PostgreSQL предлагает несколько типов индексов под разные задачи. B-tree — самый универсальный и часто используемый, подходит для сравнений и сортировок. Hash — компактный и быстрый для точного совпадения, но не для диапазонов. BRIN — очень компактный, идеален для больших упорядоченных данных (например, временных рядов), где значения коррелируют с их расположением на диске. GIN — специализируется на поиске внутри составных данных: текста, массивов, JSON. GiST и SP-GiST — это, скорее, frameworks для создания индексов под сложные типы данных, вроде геометрических объектов или полнотекстового поиска.

Важно помнить, что индекс помогает только если запрос обращается к проиндексированным столбцам, и если выбирается небольшая доля строк (обычно до 15-20%). Иначе планировщик может проигнорировать индекс и просканировать таблицу целиком. Также есть продвинутые техники: частичные индексы (индексирующие только часть строк по условию), многоколонные индексы (порядок столбцов в них критичен) и покрывающие индексы (которые содержат все данные для запроса, избавляя от обращений к таблице).

Читать подробнее оригинал на английском