CS

[OS] Synchronization Tools

critical-section problem(CSP)과 그 해결법을 공부했다. Peterson's Solution은 가장 완전한 해결법이지만, 소프트웨어적 접근이기 때문에 결국 기계어에서 발생하는 문제들을 완전히 해결할 수 없었다. 따라서 atomic instruction과 atomic variable와 같은 하드웨어적 지원이 필요했다. mutex, semaphore, monitor, liveness 이 4가지는 Peterson's Solution과 atomic instruction & variable을 이용하여 만든 CSP를 해결하기 위한 higher-level software tool이다. [ Mutex Locks ] mutex: mutual exclusion, 즉 상호배제를 구현한 것이다. 프로세스..

[OS] Synchronization

[ Background ] 프로세스는 다른 프로세스와 상호작용할 수 있으며, 이 과정에서 logical address space를 공유하거나 shared data가 생길 수 있다.(address space를 공유하는 경우는 멀티 스레딩에서, shared data가 생기는 경우는 프로세스끼리 통신할 때 발생한다) 공유 데이터에 여러 프로세스/스레드가 동시에 접근하여 값을 변경하게 되면 의도한 바와 다른 결과가 나타날 수 있다. 이를 data intetegrity(데이터 무결성)이 깨졌다, data inconsistency(데이터 불일치)가 발생했다고 표현한다. 데이터 무결성이란 데이터가 처리되는 모든 과정동안 데이터의 완전성, 정확성, 일치성이 보장됨을 의미한다. 데이터 무결성을 유지하기 위해서는 공유 데..

[OS] CPU Scheduling

[ Basic Concept ] OS는 CPU의 사용 효율을 늘리기 위해 여러 개의 프로세스를 한 번에 실행시키는 멀티프로그래밍을 한다. 하나의 CPU 코어에서 여러 개의 프로세스를 동시에 실행시키기 위해서는 time sharing(시분할)을 해야하는데, 이때 언제 어떤 프로세스에게 CPU를 할당할 것인지 정해야 한다. OS가 어떤 프로세스를 CPU에 할당할 것인지 정하는 과정을 CPU Scheduling(CPU 스케줄링) 이라고 한다. 프로세스가 CPU를 점유하고 있는 시간(running state)을 CPU burst라고 하며, I/O event를 대기하고 있는 시간(waiting or ready state)을 I/O burst라고 한다. CPU burst가 많은 프로세스를 CPU-bounded pr..

[OS] Thread

[ Overview ] 지금까지는 프로세스가 single thread of control로 실행하는 것을 전제로 하였다. 즉, 프로세스가 한 번에 하나의 작업만을 수행할 수 있는 것이다. 하지만 프로세스는 multiple therads of control, 즉 하나의 프로세스가 여러 작업을 수행하는 것이 가능하다. 이를 가능하게 하는 것이 바로 thread 이다. Thread is ... lightweight of process (LWP) basic unit of CPU utilization comprises a therad ID(TID), a program counter, a register set, and a stack 여러 개의 프로세스로 여러 작업을 동시에 수행하는 멀티프로세싱(multiproce..

[OS] Process

[ Process Concept ] Process is ... is a program in executation is the unit of work in an OS 프로세스는 실행중인 프로그램, 즉 하드디스크에 있던 프로그램이 메모리에 로드된 것을 의미한다. 프로세스는 OS 관점에서 봤을 때, 작업의 단위이며, 프로세스를 관리하는 것이 OS의 가장 기본적인 일이다. Memory Layout 메모리에 로드된 프로세스는 다음으로 구성되어 있다. text section : executable code data section : global variables heap section : memory that is dynamically allocated during program run time stack sect..

[OS] 운영체제의 개념과 구조

[ What OS Do ] Operating System is a sorftware that operates a computer system is a program running at all times on the computer provides system service to application program manages proecess, resources, UI, ... 컴퓨터는 크게 4개의 구성으로 나눌 수 있다. Hardware, OS, Application Programs, User. 사용자는 어플리케이션 프로그램을 사용하는데 이 프로그램을 실행시키는 과정에서 하드웨어 자원이 필요하게 되면 컴퓨터의 하드웨어에 직접적으로 접근하는 것이 아니라 OS를 통해 접근한다. OS는 어플리케이션 프로그램..

[OS] signal

signal 시그널은 프로세스에 어떤 event가 발생했을을 알리는 간단한 메시지를 비동기적으로 보내는 것이다. 이 메시지는 어떤 event가 발생했는지를 표시하는 상수 형태이다. 시그널이 발생했을 때 실행되는 동작을 시그널 핸들러라고 하는데, 각각의 시그널은 시그널 핸들러가 미리 정의되어 있으며, 시그널을 받는 프로세스 내에서 시그널 핸들러를 정의할 수도 있다. 프로세스가 실행되고 있는 도중에 [CTRL + C] 키가 입력되면 프로세스가 중단되는데, 이러한 경우가 시그널의 사용한 예이다. [CTRL + C] 키가 입력되면 SIGINT라는 시그널이 발생되는데, SIGINT에 매칭되어 있는 시그널 핸들러가 프로세스를 중단시키는 것이기 때문에 프로세스는 SIGINT가 발생한 즉시 프로세스를 중단시킨다. 시그..

[Algo] LIS (최장 증가 부분 수열)

LIS란? 최장 증가 부분 수열을 의미한다. 어떠한 수열이 주어졌을 때, 그 중 몇 개의 수를 골라내서 만든 수열을 '부분 수열'이라고 한며, 그 몇 개의 수가 오름차순으로 증가하는 형태일 때 이를 '증가하는 부분 수열'이라고 한다. 증가하는 부분 수열 중 길이가 가장 긴 부분수열이 '최장 증가 부분 수열'이다. 예를 들어, [10 20 10 30 40 50]수열이 있을 때, [10 20 10], [20 30] [20 10 40 50] 등 여러 부분 수열을 만들 수 있다. 그 중 최장 증가 부분 수열은 [10 20 30 40 50] 이다. Solving LIS problem - LIS 길이 구하기 수열의 첫 번째 숫자부터 순회하면서, 이 숫자를 포함했을 때 오름차순 형태를 유지할 수 있는지, 다시 말해 ..