운영체제 OS
[운영체제/OS] Deadlock Detection
Deadlock Detection 교착상태 탐지 Detection Algorithm 시스템이 deadlock state인지 detect하는 알고리즘 1. Work = Available Allocation[i]가 0이 아니면, Finish[i] = false. (안전한지 detection 검사) 그 외는 Finish[i] = true 2. (a) Finish[i] == false (b) Request[i] 오늘날은 사실상 불가능.. -process termination(프로세스 종료): 모두 중지: 구현은 쉽지만 오버헤드와 비용이 크다. 제거될 때까지 하나씩 중지: n^2의 복잡도 -resource preemption(자원 선점): deadlock으로 인해 멈춘 프로세스들로부터 자원을 뺏어옴. 자원 선점의..
[운영체제/OS] Deadlocks 데드락
요청(request): 만약 요청이 즉시 승인되기 힘드면, 요청 프로세스는 자원 획득까지 대기해야한다. 사용(use): 프로세스는 자원을 이용한다. 방출(release): 프로세스는 자원을 놓아준다. Deadlock Characterization 데드락 발생 (가능한) 조건 _ 반드시 4가지 모두! 발생한 경우 -Mutual exclusion: 동시에 하나의 프로세스만 독점적으로 자원을 사용할 수 있다. -Hold and wait: 한 프로세스가 하나의 자원을 갖고있으면서 다른 프로세스의 자원을 또 요청하려고 기다림. -No preemption(선점 허용x): 점유하던 프로세스가 자발적으로 release해야지만 자원이 release된다. (프로세스가 본인작업 완료 후) -Circular wait: 위 세..
[운영체제/OS] POSIX Semaphore 동기화
POSIX Semaphore -Named semaphore 여러 프로세스에서 공유할 수 있다. #include sem_t *sem; /*create the semaphore and initialize it to 1*/ sem = sem_open("SEM", O_CREAT, 0666, 1); /*acquire the semaphore*/ sem_wait(sem); /*critical section*/ /*release the semaphore*/ sem_post(sem); -Unnamed semaphore #include sem_t sem; /*create the semaphore and initialize it to 1*/ sem_init(&sem, 0, 1); /*acquire the semaphore..
[운영체제/OS] Mutex Locks, Semaphore, Conditional Variable
Mutex Locks 임계구역문제 해결을 위해서 운영체제 디자이너들이 만들었다. 임계구역문제에 대해서 알고싶다면 지난 게시글을 참고해주세요~ [운영체제 OS] - [운영체제/OS] Synchronization_동기화, 임계 구역 문제 [운영체제/OS] Synchronization_동기화, 임계 구역 문제 동기화(Synchronization) Producer (=master): 데이터 생성 while(TRUE) { //produce an item and put into the buffer while(counter==BUFFER_SIZE) //is buffer full? ; //do nothing //busy waiting. spin lock.. hidemasa.tistory.com 임계구역을 처음에 acq..
[운영체제/OS] Synchronization_동기화, 임계 구역 문제
동기화(Synchronization) Producer (=master): 데이터 생성 while(TRUE) { //produce an item and put into the buffer while(counter==BUFFER_SIZE) //is buffer full? ; //do nothing //busy waiting. spin lock buffer[in] = nextProduced;//write연산 (차있지 x경우) in = (in+1) % BUFFER_SIZE; counter++; } Consumer while(TRUE) { while(counter == 0) //is buffer empty? ; //do nothing nextConsumed = buffer[out]; out = (out+1) % ..
[운영체제/OS] 멀티스레드에서의 fork()와 exec(), Signal Handling
fork(), exec() 시스템콜 멀티 스레드 프로그램에서 프로세스를 복제/생성하는 fork() 시스템콜을 실행한다면 어떻게 될까?? 메인의 하나만 복제해야할까, 아니면 모두 각각 복제해야할까? 몇몇 유닉스 시스템은 두가지 버전을 모두 지원한다. exec()의 경우에는 기존 스레드들을 모두 무시하고, 새로운 프로그램으로 대체된다. fork()이후 exec()를 호출하면, 모든 스레드를 복제할 이유가 없다. fork() 이후 exec()가 호출되지 않는다면, 모든 스레드의 복제가 의미가 있다. Signal Handling(시그널 처리) Signal의 두 가지 유형: -Synchronous signal: 어떤 사건을 처리하기 위해 발생 ex)불법적인 메모리 접근, 0으로 나누기 -Asynchronous s..
[운영체제/OS] User 스레드와 Kernel 스레드, Implicit Threading
User Threads and Kernel Threads 유저 스레드- user-level 스레드 라이브러리에서 관리. 주요 라이브러리는: POXIS Pthreads, Windows threads, Java threads 커널 스레드- 커널의 지원. Windows, Solaris, Linux, Max OS X와 같은 운영체제들 유저 스레드와 커널 스레드 사이의 멀티스레드 모델: Many-to-One, One-to-One, Many-to-Many Many-to-One Model many user 스레드가 single kernel 스레드와 연결 하나의 스레드 blocking은 모두 block된다. One-to-One Model user 스레드를 생성하면 kernel 스레드가 생성된다. many-to-one에..
[운영체제/OS] User 스레드와 Kernel 스레드, Implicit Threading
User Threads and Kernel Threads 유저 스레드- user-level 스레드 라이브러리에서 관리. 주요 라이브러리는: POXIS Pthreads, Windows threads, Java threads 커널 스레드- 커널의 지원. Windows, Solaris, Linux, Max OS X와 같은 운영체제들 유저 스레드와 커널 스레드 사이의 멀티스레드 모델: Many-to-One, One-to-One, Many-to-Many Many-to-One Model many user 스레드가 single kernel 스레드와 연결 하나의 스레드 blocking은 모두 block된다. One-to-One Model user 스레드를 생성하면 kernel 스레드가 생성된다. many-to-one에..
[운영체제/OS] Threads & Concurrency
멀티스레드 자료구조 멀티스레드의 장점: 병렬적으로 여러 스레드를 한번에 동시에 동작할 수 있다. Responsiveness Resource Sharing: 자원 공유 비용 감소 Economy: 스레드 생성이 프로세스 생성보다 비용 감소. 스레드 스위칭 오버헤드가 컨텍스트 스위칭보다 낮음. Scalability: 프로세스는 멀티프로세서 자료구조의 이점을 받는다. Multicore (Multiprocessor) Programming 개발자가 multicore나 multiprocessor 시스템을 구현할 때는 Task dividing activities Load balancing Data splitting Minimizing data dependency Testing and debugging Paralleli..
[운영체제/OS] Threads & Synchronization 스레드&동기화_Mutex Lock, Semaphore
프로세스 내의 제어 흐름은 단일 스레드 프로세스가 있고 멀티 스레드 프로세스가 있습니다. 멀티에서는 하나의 프로세스 내에 여러 제어(control)이 존재합니다. 스레드는 CPU 이용의 기본 단위로서 프로세스와의 차이는 프로세스는 독립적 주소 공간을 가지지만 스레드는 주소공간을 공유하고 명령어만 다르게 합니다. 따라서 동일 프로세스의 여러 스레드는 코드 영역, 데이터 영역, 운영체제 자원 등을 공유합니다. 그리고 각자 flow는 병렬적으로 제어되는 것입니다. 그 덕에 동시에 하나 이상의 작업을 실행할 수 있습니다. 스레드 풀(Thread Pool) 작업을 기다리는 스레드들의 집합 프로세스는 시작할 때 일정 수의 스레드를 생성하여 스레드 풀에 놓는다. 요청 받으면, 풀로부터 서버가 스레드를 깨워 요청 전달..
[운영체제/OS] Frames Allocation Algorithm, Kernel Memory Allocation
동시에 동작하는 여러 프로세스에게 제한된 가용 메모리를 효과적으로 할당해야 합니다. 그래서 각 프로세스에게 할당되는 메모리 프레임 수를 정해야 합니다. (독점이나 starvation 등의 문제 방지) -프로세스당 최소한의 프레임 수 프로세스에 할당되는 프레임 수가 감소하면 page fault 발생 확률이 늘어나 성능 감소. 명령어 실행 완료 전에 page fault가 발생하면 그 명령어 재실행 필요. -프로세스당 최대한의 프레임 수 물리 메모리에 의해 결정된다.(답이 없고 OS가 프로세스에 무리없도록 알아서 할당) Allocation Algorithm -Equal Allocation(동등 할당) : 100 frames을 5 프로세스에게... 각 프로세스에게 20 프레임 할당 나눗셈으로 남는 애들은 buf..
[운영체제/OS] Copy-on-Write와 Page Replacement
Copy-on-Write (COW)는 부모와 자식 프로세스가 메모리의 같은 페이지를 공유할 수 있게 해줍니다. 프로세스 생성을 훨씬 효율적으로 하게 해줍니다. 최적화 기술 중 하나로 쓰입니다. Resourse를 공유하다가 Resource를 수정하는 경우, 이전의 Resource 복사본을 쓰게끔 하는 것입니다. 그 후에 각각 프로세서의 포인터를 변경만 해주면 됩니다. 원래는 zero-fill-on-demand 페이지들의 pool로부터 할당됩니다. 0으로 채워서 reset하는 것이죠. Page Replacement Free Frame이 만약에 없다면 어떻게 하는가? Page replacement - 새 page 위해 기존 page(잘 안 쓰이는 애, 가급적 수정 안 된 애)를 내쫓는다. (최대한 overhe..
[운영체제/OS] Page Fault와 Demand Paging
Page Fault 페이지를 참조하는데, 그 페이지에 대한 첫 참조에서 OS가 막혀버린다면(trap, 즉 software interrupt 발생), page fault가 발생된겁니다. OS가 보았을 때 1. (1) invalid 참조라면 abort를 하고, (2) 그냥 메모리에 없는 경우- 두 가지 중 하나로 판단 2. free frame을 찾음 3. 페이지를 disk로부터 frame에 swap해줌. 4. page table을 유효한 값으로 validation bit을 v로 변경해줌. 5. page fault를 발생시켰던 명령어를 다시 실행. (stop->ready 단계로) Demand Paging 프로세스에서 페이지를 프로세스 생성 시에 모두 할당하는 게 아니라, 필요할 때마다 동적으로 할당하는 기법입..
[운영체제/OS] Main Memory 메모리 관리 2/2
이전에 다루었던 메모리관리 편을 먼저 읽고 오시는 걸 추천해드릴게요 [운영체제 OS] - [운영체제/ OS] Main Memory 메모리 관리_ Address Binding, Segmentation, Paging, Memory Protection [운영체제/ OS] Main Memory 메모리 관리_ Address Binding, Segmentation, Paging, Memory Protection 명령어가 실행되는 절차는 메인 메모리에서 명령어를 읽어와서 실행하고 결과를 다시 메모리에 저장해요. 하지만 메모리에 접근하는 과정은 단순하지 않고 cycle을 거쳐야 하고 stall(대기)상태에 hidemasa.tistory.com Paging을 위한 메모리의 구조는 너무 크다는 단점을 가집니다. 메모리 비..
[운영체제/ OS] Main Memory 메모리 관리1/2_ Address Binding, Segmentation, Paging, Memory Protection
명령어가 실행되는 절차는 메인 메모리에서 명령어를 읽어와서 실행하고 결과를 다시 메모리에 저장해요. 하지만 메모리에 접근하는 과정은 단순하지 않고 cycle을 거쳐야 하고 stall(대기)상태에 자주 걸립니다. CPU는 메인 메모리와 (CPU의)레지스터에 직접적으로 접근할 수 있어요. 레지스터는 접근이 작은 대신 빠르고 메모리는 크기가 크고 접근이 느려요. CPU가 메모리를 오갈때 stall상태에 자주 안 걸리고 속도를 향상하기 위해 cache(캐쉬)를 CPU와 메모리 사이에 놓습니다. 속도와 protection 이 두 가지가 중요한 요소입니다. protection을 위해서 base 레지스터와 limit 레지스터가 있습니다. base(기준) 레지스터는 가장 작은 물리 메모리 주소(=시작주소)를 가지고, ..
[운영체제/OS] CPU Scheduling_ Multilevel Queue, Multilevel Feedback Queue 스케줄링
[운영체제 OS] - [운영체제/OS] CPU Scheduling_비선점, 선점, FCFS, SJF, Priority, RR 스케줄링 [운영체제/OS] CPU Scheduling_비선점, 선점, FCFS, SJF, Priority, RR 스케줄링 이전 글에서 간단하게 프로세스 스케줄링을 알아보았어요. [운영체제 OS] - [OS/운영체제] Process Scheduling 프로세스 스케줄링 [OS/운영체제] Process Scheduling 프로세스 스케줄링 프로세스- 프로그램이 � hidemasa.tistory.com 앞서서 CPU 스케줄링 네 가지 알고리즘들을 알아보았어요. 라운드로빈(RR)과 선입선처리(FCFS) 스케줄링을 알아야 이번 게시글을 이해하기 편하므로 먼저 이전 게시글을 보고 오시는 걸 ..
[운영체제/OS] CPU Scheduling_비선점, 선점, FCFS, SJF, Priority, RR 스케줄링
이전 글에서 간단하게 프로세스 스케줄링을 알아보았어요. [운영체제 OS] - [OS/운영체제] Process Scheduling 프로세스 스케줄링 [OS/운영체제] Process Scheduling 프로세스 스케줄링 프로세스- 프로그램이 실행된 것 (효율적 관리가 필요) 프로그램은 디스크에 있는 수동적인 성격, 프로세스는 능동적인 성격을 가집니다. 즉, 프로그램은 executable file이 메모리에 load되면(올라오 hidemasa.tistory.com CPU burst 와 I/O burst CPU 활용은 multiprogramming을 통해 성능을 향상시킬 수 있어요. CPU burst는 CPU명령을 수행하는 것을 의미하고 I/O burst는 I/O를 요청한 후 기다리는 시간을 의미해요. 프로세스..
[운영체제/OS] Interprocess Communication (IPC)란?
프로세스들은 independent독립적일 수도 있고 cooperating상호협조적일 수도 있습니다. cooperating한 프로세스들은 공유data를 포함해 프로세스들끼리 영향을 줘요. 정보공유, 속도향상, 모듈화의 목적을 가지고 있습니다. 이를 위해 Interprocess Communication (IPC)를 필요로 하는데요 IPC는 두 가지 모델, Shared memory와 Message Passing이 있습니다. Shared Memory 모델 프로세스들이 공유하고 싶은 메모리의 영역이 있을거에요. communication 에 대한 컨트롤은 OS가 아닌 user 프로세스들이 가지고 있습니다. 가장 중요한 점은 shared memory 에 대해 user 프로세스들이 synchronize(동기화)를 허용..
[운영체제/OS] 운영체제 Operating System는 무엇이고 하는 일은 무엇인가?
운영체제 Operating System이란? 컴퓨터(사용자)와 컴퓨터 하드웨어의 중간자 역할을 하는 프로그램 운영체제의 목적 환경 제공(environment management) 프로세스 제어 관리(process management) 자원 관리(resource management) (자원의 예: 스토리지, 메모리, I/O) 우리가 사용하는 컴퓨터의 작동방식을 하드웨어와 연결지어 생각하면 이해하기 더 쉬울거에요. Computer System Operation Memory는 CPU, disk controller, USB contorller, grapthic adapter로 구성되어 있어요. I/O device와 CPU는 동시에 실행이 가능해요. CPU는 data를 main memory로/로부터 local b..
[OS/운영체제] Process Scheduling 프로세스 스케줄링
프로세스- 프로그램이 실행된 것 (효율적 관리가 필요) 프로그램은 디스크에 있는 수동적인 성격, 프로세스는 능동적인 성격을 가집니다. 즉, 프로그램은 executable file이 메모리에 load되면(올라오는순간!) 프로세스가 됩니다. 프로세스 상태 Process State new: 프로세스가 created(생성) 되었음 running: Instructions가 executed(실행)중임 waiting: 프로세스가 어떤 event(이벤트) 발생을 대기중 ready: 프로세스가 processor(프로세서)에게 일을 할당 받기를 대기중 terminated: 프로세스가 execution(실행)을 마무리함 CPU switch from Process to Process Process Scheduling 프로세스..